gg阳谷new grad新鲜昂赛

2月7号今天刚面完的！上来发个面经。在sunnyvale的google cloud面的，好像是做infra&tools的组吧，介绍自己都跟network和C++相关。

第一轮：一个大叔，设计一个数据结构实现输入法auto-complete，比如已经有[cat,cats]，输入"c"返回[cat,cats]，用了trie，follow up考虑其他语言，时间复杂度不太会答说了worst case O(n)。
第

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

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

的，随缘了，发个面经帖好好准备亚麻去了！


补充内容 (2019-2-8 11:13):
[2,3,4] 和 [2,2,3,4]

补充内容 (2019-2-20 08:40):
刚收到hr电话说hc挂了..move on！

杨超越 发表于 2019-2-8 11:04
第一题：trie
第二题可以naive的M*N 当然最好的方法就是楼主的binary search
第三题的问题是什么。。。。 ...

第三题输出是List<Integer>就是1，2，3，4
第四题是有一个register(int period, String word)和receiveNotification()在Timer这个类里，可以register很多word，然后每次receiveNotification就相当于过了一秒吧，到period的倍数时候打印这个word。比如register(2,"ABC") register(5,"DEF"), 第十次receiveNotification的时候就打印ABC和DEF 同理第2，4，6，8次打印ABC

杨超越 发表于 2019-2-8 11:23
第三题是要求输出这个环的值？

第四题懂了 那就是hash map存时间和这个时点要打印的list 到了时间 就 ...

嗯嗯对的，当时想到这个写出来基本没时间了..没考虑多个string的情况

wulaoshi250 发表于 2019-2-8 11:26
求个lz amazon vo面经！给您加米啦谢谢

没面呢。。

```
第二轮：中国小哥，类似skyline，给两个vector,[2,3,3]和[2,2,3,4]分别代表左视图和前视图最高的building高度，求这个3*4的block最大的building heights和，最后小哥提示下写出了先sort一个vector，然后遍历另一个vector去binary search第一个sorted vector然后累加。
```
这个题目楼主能再解释一下吗？3*4的block最大的building heights和是啥？还有前面那个输入是不是应该是[2,3,4]不是[2,3,3]?

hpplayer 发表于 2019-2-8 10:26
```
第二轮：中国小哥，类似skyline，给两个vector,[2,3,3]和[2,2,3,4]分别代表左视图和前视图最高的build ...

一个3*4的grid，从左视图看高度是[2,3,4] 前视图看高度是[2,2,3,4]
这样的话其实符合两个视图的最高和是
[ 2, 2, 2, 2
  2, 2, 3, 3
  2, 2, 3, 4] 这里面有几个grid[i][j]可以变小，求所有grid[i][j]的最大可能和。

补充内容 (2019-2-8 10:45):
grid【i】【j】

禁欲系是什么啦。。。。哈哈哈

第一题：trie
第二题可以naive的M*N 当然最好的方法就是楼主的binary search
第三题的问题是什么。。。。。。。。
第四题：是给了很多单词和周期吗？然后按照时间顺序打印？没太懂？

杨超越 发表于 2019-2-8 11:01
禁欲系是什么啦。。。。哈哈哈

进门握手之后直接开始讲题，不带闲聊的..

MacJordan 发表于 2019-2-8 11:18
第三题输出是List就是1，2，3，4
第四题是有一个register(int period, String word)和receiveNotificati ...

第三题是要求输出这个环的值？

第四题懂了 那就是hash map存时间和这个时点要打印的list 到了时间 就打印 但如果这个点需要打印k个string 其实时间复杂度并不是O(1) 因为你还需要对打印的每个string更新到下一个需要打印的时间？

第二题是lc807吧
第三题是找到环后backtrack的时候加到结果里？
第四题还是没懂。。。

求个lz amazon vo面经！给您加米啦谢谢