Google onsite 面经

面试了很多家，google家的面试整体体验最好，每个环节都安排的特别合理，整个campus很大，很舒服。
看了很多面经，下面和大家分享下面试的大概题目回馈大家的帮助，也希望能够帮助到大家，希望大家跟我一起祈福，祝我能拿到offer。
我也有一个问题，我总共面试了5轮，第一轮，没答太好，答完时间到了，面试官说他不确定代码逻辑是否正确，这轮要

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

给一个String[] array, 和任意一个移动的window size k， 对array里的元素位置进行改变，使得window里的元素不重复. 要efficient的解法。

祝大家找工作顺利， good luck。

不知道楼主现在有结果了吗 保佑
关于第四轮， 不明白为什么不直接用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)

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

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

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里面从后向前走就行了。

谢谢LZ 分享， 祝LZ 早日拿到offer。 请问下第三题 flow water 是什么题目？ 还有第五题 window 里面的元素是 string 吗 还是char?

queeniejing 发表于 2015-11-10 09:55
谢谢LZ 分享， 祝LZ 早日拿到offer。 请问下第三题 flow water 是什么题目？ 还有第五题 window 里面的元素 ...

第三题：
~  ~   ~   ~   ~   ~  ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*  *   *   *   *   *  *

给定一个grid，判断是否有点技能到达~,也能到达*。就用图的DFS,BFS做。

第五题，其实比较难，考虑的情况很多，window就是在输入的string[] array里移动，windows里的元素可以是任何string。

请问楼主第二轮 O(logn) 复杂度的思路是什么呢？

谢谢分享！请问第五题的意思是不是重新排列array使得相同string的distance至少为k？

licheng2002 发表于 2015-11-10 12:50
谢谢分享！请问第五题的意思是不是重新排列array使得相同string的distance至少为k？

这可以是一种解法，有很多种可能性，输出其中一种就行了。

多谢分享。

marthew777 发表于 2015-11-10 13:26
多谢分享。

完了。。字数不够。。。我擦。。被警告了。。

谢谢lz分享 赞一个，必有offer。

请教下lz几个问题
第一轮： 每行 长度mod string长度剩下的值跟词长度match？         

第二轮：这个popular item是value 大于 size / 4 还是出现频率?如果是value的话是不是简单二分？

第五轮：感觉解法多种，比如类似greedy的统计所有string出现次数然后分配。不过这里为什么要用string[] array呢，普通char[] array也一个意思阿，难道别有用意？

谢谢lz！

我想问一下第四轮的题目。因为要o(n)，是map+double linkedlist的解法么？