小米暑期实习在线笔试2015-04-25

周五晚上参加了小米的全国在线笔试,使用的是百一测评,不得不说,这是我参加过的最不靠谱的在线笔试。
先来描述题目,再来吐槽,在线笔试就是三个必做题和两个附加题。
必做题是三个算法题,
第一题是判断两个十进制数的二进制表示中有多少位是不一样的,给的两个数据是1999, 2999, 答案是7
第二题是最多两次两次买卖的最大股票的最大收益问题
第三题是最近的公共父节点,对树中的每个节点编号,这个编号应该是根据深度遍历的规则来编号的,然后
通过邻接矩阵来表示节点之间的父子关系:
给出的数据是
0 1 0 1 1
1 0 1 0 0
0 1 0 0 0
1 0 0 0 0
1 0 0 0 0
节点indexA=1, indexB=2
答案结果1
我的思路:
二维动态规划,base[i][j],表示节点i和j的最近共同父节点,即根节点与所有节点的共同父节点都是根节点,
然后依次判断每个节点,对每个节点的额操作是先判断起父节点(只有一个,并且索引值比它小),它和其他
节点的公共父节点就是其父节点和其他节点的公共父节点,但是它和父节点的公共父节点是其父节点。
然后判断当前行是否是指定的indexA,如果是则返回bases[indexA][indexB]。

分割线==============================================吐槽开始

    首先提交第一题的时候,显示超时,当时我还是不是很意外,可能是时间复杂度比较高,因为我就是暴力求二进
制位然后比较,但是我惊奇的发现,我输入的两个测试数据是0,0,也超时,很震惊呀,然后注释掉了所有的功能
代码,直接return 0,奇迹出现了,还是超时,what ?我又点开其他两题,分别都是return 0,居然都是超时,我
已经无法理解了,但是我又点了几次,居然有一次是提示结果错误,这才是预期中的效果么,但是我又点了一次,
同样的代码,同样的数据,提示超时,这个完全没法进行了。
    不过还想想了了想,毕竟已经过去半个小时了,不管怎么说还是要继续往下做,后来我就在另一个电脑上开了编译
器,把代码输进去调试,通过后在输进页面里,问我问什么这样做?以为这个系统要求你不能离开它操作五次,我不小心
点了两次360加速球,就用掉了两次机会,我还敢在本机上使用IDE么。
    当时间过去了1个小时15分钟,突然发现系统变好了,可以正常提交了,赶紧测试下之前提交的两个问题的代码,还好
都通过了,然后开始做第三题,其实第三题一开始都没看明白,邻接矩阵不都是表示图的么,第一次见表示树,不过树也是
一种图了,也就不是很意外了,当我把代码什么都搞完后,提示还有5分钟,然后我就提交了,然后提示找不到硬件,再提交
提示找不到题目,然后被迫再次进入题目,提示已经结束,what?我看了下电脑,好像是已经结束了,难道我最后一题没有
提交,或者说,我都没提交题目。。。。。。我靠,我也是佩服我自己了,这是在搞什么。。。。。。
原文地址:https://www.cnblogs.com/chen310/p/4455584.html