Google onsite 面经

jkingxt 发表于 2015-11-10 15:22
我想问一下第四轮的题目。因为要o(n)，是map+double linkedlist的解法么？

you are right.

不知道第二轮怎么做。如果是O(n)的算法就不需要sorted array的假设了吧。可以对于每个元素二分搜索其范围，但是在worst case下也有O(n)的复杂度。

jkingxt 发表于 2015-11-10 15:22
我想问一下第四轮的题目。因为要o(n)，是map+double linkedlist的解法么？

第四轮：map + linkedList 的解法是怎么做的啊？还是不太明白。
我的疑问是 map 的插入操作不是logN复杂度么？在扫描一遍就是NlogN了呀？

lianlu 发表于 2015-11-11 12:02
不知道第二轮怎么做。如果是O(n)的算法就不需要sorted array的假设了吧。可以对于每个元素二分搜索其范围， ...

找n/4 n/2 3n/4 n这几个candidate，然后分别用二分搜索看长度满不满足

jkingxt 发表于 2015-11-10 15:22
我想问一下第四轮的题目。因为要o(n)，是map+double linkedlist的解法么？

map＋双向链表怎么做？能用额外空间那感觉这题没啥trick了啊。。

hj867955629 发表于 2015-11-16 13:27
找n/4 n/2 3n/4 n这几个candidate，然后分别用二分搜索看长度满不满足

你好~是说对于这4个candidate，分别进行用二分法来计算是不是most popularity嘛？

楼主好~想问一下第五题的思路哈~如何efficient啊~

yjfox 发表于 2015-11-10 13:46
谢谢lz分享 赞一个，必有offer。

请教下lz几个问题

第二轮当然是count > size/4 了，要死value的话直接看最后一个元素O（1）就有结果了没意义。array是sorted的

第二题只需要检查0, 1/4, 2/4, 3/4 4/4位置的元素看它们是不是就可以了，检查每一个数用二分搜索找左右boundary算个数，所以是(10 logn) = logn

guoqinlong 发表于 2015-11-16 20:44
你好~是说对于这4个candidate，分别进行用二分法来计算是不是most popularity嘛？

对的，因为most popularity如果出现的话只能是这四个数字中的某个或某几个