Google电话面试

面试官应该是个美国人，上来直接进白板，说先热身，自己写了一个字符串，让我找出频率最高的字母，要求只说解法和复杂度，不写code。很快讲完Hashmap的方法，面试官说good, move forward.

第二题是类似于扫雷或者walsl and gates的一个矩阵游戏，标记一个空格子，如果邻居为空，就也标记出邻居格子。邻居不为空，就停下来。
我用

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

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

希望了，祝大家能有好表现！


补充内容 (2017-2-4 10:17):
昨天收到recruiter电话，说一面code写的不规范，和面试官沟通太少。需要再电话面一轮，让我做好准备。

我觉得第三题面试官是想让你用bit。SSN有9位，所以SSN总共的个数不会超过2^30。每一个SSN对应一个bit，那么我们用2^30个bit，即2^27个byte，差不多是135MB，就可以存下所有的SSN。找重只需要看相应的bit有没有被置1即可。

应该就是这个题目187. Repeated DNA Sequences
没办法用一个Integer表示一个，因为数字0-9将会用掉5个bit, 5乘以9就是45个bit. 只能用Long表示，
一个有10^9个ssn，每一个ssn一个long, 就是8byte,一起就是8 * 10 ^ 9 byte. 就是10g
用trie:
最多要9层。 每一个数字4个byte。一起 (10^9 + 10^8 + 10^7+10^6.. + 10^1)，也就是10^9，所以其实一样的空间
用trie和long表示都是一样的好

第三题，不知道面试官是不是希望用trie呢？

thuwm 发表于 2017-1-31 14:33
第三题，不知道面试官是不是希望用trie呢？

嗯，我后来查了，有一个用红黑树存储SSN的例子，也许是红黑树  Trie感觉也合理

LZ能详细讲下矩阵游戏的题目和解法么？没太看明白

请问楼主面的什么职位？

ldy5661 发表于 2017-2-4 07:43
请问楼主面的什么职位？

就是一般的SWE啊

cntototo 发表于 2017-2-4 08:20
我觉得第三题面试官是想让你用bit。SSN有9位，所以SSN总共的个数不会超过2^30。每一个SSN对应一个bit，那么 ...

有道理啊 我当初完全没有往bit考虑  赞！  学习了

新宿车站 发表于 2017-2-4 07:26
LZ能详细讲下矩阵游戏的题目和解法么？没太看明白

我事后想了一下，就是walls and gates 那个leetcode题，变了一种说法而已。主要就是把那个dfs前后左右移动写出来，就可以了。

新宿车站 发表于 2017-2-4 07:26
LZ能详细讲下矩阵游戏的题目和解法么？没太看明白

我事后想了一下，就是walls and gates 那个leetcode题，变了一种说法而已。主要就是把那个dfs前后左右移动写出来，就可以了。