Google Onsite 跪经

11.11onsite面的google
第一轮，国产女生。给一个数，非负整数，判断其顺时针旋转180°后是否等于原数。
比如181,16091都是，171就不是
follow up，给一个长度n，找出长度从1到n所有旋转后等于原数的数

第二轮，白人小哥。比如A：B C这种形式代表A和B，C是近义词，那么当然B和C也是近义词
输入如下
A：B C
B：C D
C：A E H

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

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

来了，还算顺利，当时googler们表示也满意，但是两周后电话通知被拒。。。


补充内容 (2016-12-5 03:14):
不好意思打错了，第三轮是leetcode 57

waikai 发表于 2016-12-5 01:25
Lz的第四轮和我同学估计是一个面试官。不过这是leecode原题啊，我同学答完后面试官又追加了一个经典的最大 ...

唉我一开始没领会他意图啊，他开始让我写输出，我说那就bruteforce把所有都读出来重新排序呗，他说可以，我就写了一白板，结果写完他才告诉我其实更想要一个新结构可以按顺序读，坑爹

aifer 发表于 2016-12-4 17:37
unionfind，预处理把图建起来的同时做双向union，可以用个boolean matrix来存是否两个词是近义词，查的时 ...

第二轮那个题想想细节貌似细节还挺多的...如果词长一点没想到O(1)的, 我想到每次查询能有O(|S1|+|S2|)
如果用并查集预处理的话, 全部到根以后只考虑查询, 不用矩阵直接找根也可以O(1)查

aifer 发表于 2016-12-4 14:29
最后一题楼主怎么打的？我的解法是用个Queue，外层iterator读一个之后放到Queue里，然后读下一个，以次类推 ...

嗯差不多，我是用arraylist在第一轮的时候按index存下所有的外层interator，这样循环就可以了

最后一题楼主怎么打的？我的解法是用个Queue，外层iterator读一个之后放到Queue里，然后读下一个，以次类推。

第二轮 咋搞

楼主请问第二轮O(1)怎么做啊

神罗天征 发表于 2016-12-4 16:21
楼主请问第二轮O(1)怎么做啊

unionfind，预处理把图建起来的同时做双向union，可以用个boolean matrix来存是否两个词是近义词，查的时候直接从这个matrix里面找就好了。O（1）复杂度。

aifer 发表于 2016-12-4 17:37
unionfind，预处理把图建起来的同时做双向union，可以用个boolean matrix来存是否两个词是近义词，查的时 ...

嗯就是这样，只不过当时讨论了好多，正解~

cstdlib 发表于 2016-12-4 19:56
第二轮那个题想想细节貌似细节还挺多的...如果词长一点没想到O(1)的, 我想到每次查询能有O(|S1|+|S2|)
...

单词长度可以忽略吧，再长的单词也没多长吧，哈哈

Lz的第四轮和我同学估计是一个面试官。不过这是leecode原题啊，我同学答完后面试官又追加了一个经典的最大假期问题。所以感觉lz可能因为不够快速而评分不够了。Anyway，好事多磨，lz加油