google 2018四月onsite面筋

分享一波4月10号Onsite 面筋，现在在team match 阶段

1.黑哥哥

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

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

2.白姐姐
用preorder和postorder建树，这道题出来时我说好像没有inorder是做不出来的，然后聚了个例子，面试管说那就假设总是有left subtree的，然后楼主用recursion写了。完了分析时间复杂度，问怎么优化（hashmap 存一边postorder里的val 对应的Index）

3. 白大哥
类似乐扣伞就无 但不一样的是这个api不能存query, 不负责接收query,不负责发送，只是会每1秒让n个isAllowed（） 返回true. 这题我当场有点懵，我就说了那就写一个count和clear, 然后每秒清零count。但这样做会造成每秒前10个可以，会形成每秒一个峰值。面试官问可不可以有一个更平均的分布，我说那就每1/n秒返回一个true, 然后清零... (我知道这样做很笨，但当场没有想到更好的方法。面试官一直强调说不能存任何和query有关的东西（除了计数），只负责yes or no然后保证这个rate的正确性)，写完码答了怎么unit test

4.  话很多的白姐姐
这个姐姐是我面得最开心的一轮，她整个人很活波，一直笑，让我放松了很多。

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

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

5. 话很少的白哥哥
乐扣巴以无
这题我面试前一天看过一眼，因为当时是乐扣最新的一道hard，（其实一点不难），但前一天只是想了一下，没有练习码。不过面试官说出考题的时候还是很激动的，感觉比较胸有成竹了吧。
做完后写了三个unit test, 白哥看了时间，还有10多分钟，他让我写了两个javascript里的call back function 给他看一下，问了一下我平时遇到bug怎么debug之类的就聊完了。

周二面完，周天收到hr说结果不错，现在正在team match.

谢谢大家，求大米哟。祝大家好运


补充内容 (2018-4-17 23:42):
第三轮是乐扣伞无就，，不好意思我之前写错了

为什么要通过email发送啊？

凯伦小龙虾 发表于 2018-4-17 22:44
就是说每次出来一个char，我都会从root开始找看有没有符合，如果符合的话，我就把当前这个trienode指针ap ...

这个题如果把词典的word逆序后建Trie树，再用一个vector存最近遇到的max_length_of_word_in_dict个char，每次来一个char就逆序构造string到Trie中查找，就可以避免存多个TrieNode*的情况
因为你存TrieNode*至多也要存max_length_of_word_in_dict个，所以空间复杂度没区别。

凯伦小龙虾 发表于 2018-4-18 03:17
是的。面试官当时只是说保证rate不被打破，而且不能存之前的信息，所以我当时就有点懵，不清楚怎么做可以 ...

看了最近的面经，我觉得面试官是想要设计一个类似Rate Limiter 的东西，true 表示接收， false 表示拒绝。这样想的话，楼主的做法似乎没有什么问题。

请问楼主第四题的字典树怎么做的，指针的意思是指每次拿到一个符合条件的char，把这些指针全部存下来？然后下次碰到以这个指针开头的char然后开始找？

zyy6799 发表于 2018-4-17 22:35
请问楼主第四题的字典树怎么做的，指针的意思是指每次拿到一个符合条件的char，把这些指针全部存下来？然后 ...

就是说每次出来一个char，我都会从root开始找看有没有符合，如果符合的话，我就把当前这个trienode指针append 到一个list里； 同时我会loop 整个list, 看我之前的那些指针所在的trienode能不能继续往下走，如果可以我update它们，如果不可以我就把它从list里remove
比如abc, bc,   然后我的char stream 出来是 a, b, c.
出来a的时候 我把a 存在list 里 [a],  
出来b的时候，我发现之前的a 也可以被update, 同时b 也是root 里的char, 就存[a ->b,  b]
出来c， 我同样update list 里的每一个 [a->b->c, b->c], 这样就可以打印了

女神，你已经工作了，都不用面System Design么？是在MTV site面的嘛？

idatascience 发表于 2018-4-17 23:18
女神，你已经工作了，都不用面System Design么？是在MTV site面的嘛？

我没有面system design, 我在纽约面的。

凯伦小龙虾 发表于 2018-4-17 22:44
就是说每次出来一个char，我都会从root开始找看有没有符合，如果符合的话，我就把当前这个trienode指针ap ...

挺好的做法，如果想节省空间的话还可以把反向存string到trie里面。

楼主， 所以第一题是一个api设计题？ 字典可以提前处理，然后查找api会被call很多次？ 第三轮乐扣伞就无是395？但是那道题有api query isAllowed吗？ 楼主答得真好！ 恭喜

凯伦小龙虾 发表于 2018-4-17 23:20
我没有面system design, 我在纽约面的。

恭喜~想请问一下你面试的时候人力就说了不面system design的么？女神，你是朋友内推的还是自己投的呀？

hyliu0000 发表于 2018-4-17 23:37
楼主， 所以第一题是一个api设计题？ 字典可以提前处理，然后查找api会被call很多次？ 第三轮乐扣伞就无是3 ...

那道题好像是三五久，不好意思，我写错了。。。。第一题可以想象成一个设计题吧，可以和面试官交流，因为优化的方法很多，可以自己提出很多假设哈

idatascience 发表于 2018-4-17 23:37
恭喜~想请问一下你面试的时候人力就说了不面system design的么？女神，你是朋友内推的还是自己投的呀？

对的，hr说只面算法，我是收到hr的邮件去面的，通过linkedin收到的hr站内信