Google onsite 面经

oneshot 发表于 2015-11-17 08:21
感谢楼主分享，第一道题，一个string里面有一个词放不下放到下一行，意思是这个词放到下一行吧？楼主当时是 ...

这到题如果想高效的写的话需要找到循环节

pyemma 发表于 2015-11-18 03:48
即使多于也不影响，留出预留空间放置意外

哪有你这样说的，多余了就是无意义地增加了计算量啊。

bless LZ！请问第四轮O(N)解法是什么呀？

面假空虚 发表于 2015-11-17 19:18
哪有你这样说的，多余了就是无意义地增加了计算量啊。

主要是有时候做除法down cut的时候可能会出个意外啥的

小小平民 发表于 2015-11-11 14:46
第四轮：map + linkedList 的解法是怎么做的啊？还是不太明白。
我的疑问是 map 的插入操作不是logN复杂 ...

可以用unordered_map吗？

不知道楼主现在有结果了吗 保佑
关于第四轮， 不明白为什么不直接用HashSet 加双指针， 一个fast pointer正常遍历array, 一个slow来收缩array, slow标记过的部分都是没有重复的。 举个栗子， [2 3 3 4 3],
fast [2 ]
slow[2 ]
set(2)

fast [2 3]
slow[2 3]
set(2 3)

fast [2 3 3]
slow[2 3]
set(2 3)

fast [2 3 3 4]
slow[2 3 4]
set(2 3 4)

fast [2 3 3 4 3]
slow[2 3 4]
set(2 3 4)

谁的时延 发表于 2015-11-10 10:04
第三题：
~  ~   ~   ~   ~   ~  ~
~  1   2   2   3  (5) *

请问楼主能够在解释清楚一点第三题吗？ 每一个点前进路径会有什么限制呢？  
第五题应该是字符串重排， 要求相同字符的间距>k的变种题. 使用Heap可以快速解决。 大概是HashMap统计词频， Entry<Character, Integer> 作为item 放进Max Heap, 以Integer重复数量作为排序因子。 然后每次从Heap取出k个元素append到StringBuffer, Integer分别-1之后再放回Heap. 再取出K个entry重复就好了

snail_914 发表于 2015-11-26 06:17
请问楼主能够在解释清楚一点第三题吗？ 每一个点前进路径会有什么限制呢？  
第五题应该是字符串重排，  ...

第四题，为何需要双指针？如果可以用hashtable的话，那么直接从左到右遍历，如果当前的数重复出现，那么跳过，如果是第一次出现，那么把它向左移动就行了，每移动一次，更新一下index。

第五题，我看不懂你说的Heap取出k个元素append到stringbuffer，如果直接取k个最大的，那么如果保证这新的k个和前面的自身间隔大于k？我觉得还是用bst维护好一些，bst按照出现频率维护，频率大的在后面。另外一个hashtable维护前面k个已经出现的数，想要继续插入，就是在bst里面找出现频率最大的数，并且这个数没有在前面k个里面出现，找到之后，更新hasthtable，更新bst。用bst好处是，每次查找新插入的string，不需要真正取出string，只需要在bst里面从后向前走就行了。

returning 发表于 2015-11-29 03:53
第四题，为何需要双指针？如果可以用hashtable的话，那么直接从左到右遍历，如果当前的数重复出现，那么 ...

第四题hashset就行了