Google 2015-10-2 MTV 另求教

求问下中国人那题的解法， Question6。 我自己想到个解法不知道对不对。 比如Given a sorted input array, write an O(lgN) algorithm to find if there is a number has appears more than 1/2 times， 如果找1/2 的话， 我们把1/2 的这个区间在0到n 上面平移，那么不管怎么分布， 检测 0, 1/4,2/4,3/4,4/4. 这4个点的值， 如果其中有2个点相等的话，那么就存在 有个数出现超过1/2 次。 这样类推到找数超过1/4 就检测0，1/8,2/8 .....到8/8 。

第六道能不能这么做：取1/4，2/4，3/4，4/4这四个数，对每个数，分别找到第一个大于它的数的位置和最后一个小于这个数的位置，计算长度

用二分搜索，所以lgn

LawranceH 发表于 2015-10-3 12:24
求问下中国人那题的解法， Question6。 我自己想到个解法不知道对不对。 比如Given a sorted input array,  ...

找1/2majority的话，其实没必要移整个范围。可以先取得a[(size-1)/2] == midval的值，如果1/2majority存在，那么必定是midval。理由是，大于和小于midval的数最多也只有(size-1)/2个，所以除midval以外，其他数都不可能是1/2majority。然后在数组左半二分找midval开始的位置begin，在数组右半找midval结束的位置end。如果(end-begin + 1) > sizel/2, 那么midval就是1/2maj，否则就没有1/2maj。

这样的话，可以省掉一次检查4个点的麻烦。

kelvinzhong 发表于 2015-10-3 10:07
楼主怎么五轮面试？是因为不是new grad多加了一轮？ 我觉得这个..没法跟hr说吧。。

补充内容 (2015-10-3 1 ...

我不知道为什么

a341265353 发表于 2015-10-3 10:42
有过两个面试官也全程严肃，面的时候心惊肉跳。。。但是最后还是给了好的feedback。这个面试官至少给了提示 ...

我是全程都在讲话，连思考的时候也在讲。他并没有给我任何提示，而是见我一直没想出来，就直接告我算法了。如果他稍微提示一下，我是可以做出来的。其实这道题并不是特别难。

kelvinzhong 发表于 2015-10-3 10:56
层主是怎么知道哪个面试官给了什么样的feedback的呢？~我也想知道我得到什么样的feedback

你什么时候面的

sevensevens 发表于 2015-10-3 11:00
请问楼主 第二题的问题到底是啥呀 要写hasNext() 和next()么？那为啥会有那样的输入输出？谢谢！

是实现hasNext() 和next(). 结果是call next() 时的结果

nothingtrouble 发表于 2015-10-3 11:38
bless,不要太担心了，一面不好，还有其他的呢。lz你行的！

另外，中国人的那道题我觉得应该是用鸽笼原理 ...

谢谢安慰！也祝你早日拿到dream offer

flyaway25 发表于 2015-10-3 12:00
我当时去google面onsite的时候也遇到这种中国人，题目明显没有事前准备，出得很不清楚，跟他confirm的时候 ...

你跟HR报告了么？你结果怎么样？