谷歌onsite面经

第一轮： lc739, 另一题是：给你一个word的idctionary, 在给你一个word, 问你word是否在dictionary里面， word最多可以修改一个字符。这题我给出了用hashset存的方法，和trie的方法，最后只让实现了hashset的方法。
第二轮： 给一个表达式字符串，比如“（1+2）*3”， 假设分为parsing team 和compute team, parsing team 可以把它parse成你想要的数据结构，然后我要做的就是实现compute(T t)并给出T的定义. 当时我定义t为一个表达式树，然后写了compute的code, 之后，又改了下表达式树，把c

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

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

ndex tree方法，最后让写了binary index tree 的code。的code。并要求处理了multithreading safe的问题。（用synchronized。。）

感觉第四轮hint有点多，然后code没有全部写完。。。 第三轮followup code也没写。

第四题我一开始也以为是二分图问题，但被面试官否认了，然后在hint下, 才反应过来是toposort，code没写完，但思路面试官说是正确的。

第四题是这样子的，就是首先，肯定有2n个人，然后对于一个pair(m, n), 表示m喜欢n，但n不一定喜欢m。并且，每一个人只会喜欢1个人， 所以m喜欢了n，就不存在m喜欢l。所以，如果把人作为node的话，就相当于，每个node出度<=1。因此，把喜欢这种关系建成一个图之后，每次都从入度为0的node出发（比如m喜欢n，但没人喜欢m，这样的话把<m, n>配在一起，同时把m,n从图中去掉), 这样一直做下去，直到最后要么剩下了环，也有可能剩下了几个单点）,就是toposort。

（假设不会存在强耦合环，即a->b, b->a，若存在的话，可以先preprocess, 让强耦合两两匹配，之后再跑toposort）

证明最优性：如果选了(m,n)这条边，就使得m和自己喜欢的人配到了一起，也就相当于给最终答案贡献了1，然而这种贡献并不会影响到全局最优，因为首先m入度为0，所以m只能配n，并且，n在最优解当中至多被一个人匹配，所以选择(m,n)这条边不会影响全局最优。（有点像贪心的意思）。

最后如果是单点，可以随意匹配其它单点，如果是环，可以选任意一边解环。

lz可以讲下第四题怎么用拓扑排序吗

umialpha 发表于 2019/04/02 14:42:07
第五轮这个要求高度最小楼主是怎么考虑的？貌似用union算法的话还挺麻烦？

我看有的面经说那题input和馏粑舞不一样给的是一个root，如果是这样的话BFS+set()就能秒了

感谢分享 很有用的信息。愿你H1B 抽签顺利！

除了第四问以外好像还可以，感谢楼主分享

第四题是人车匹配的follow up 。二分图的最大匹配。匈牙利算法。妈呀，看来又要去默写几遍了。

kaipeng21 发表于 2019/04/02 14:29:40
除了第四问以外好像还可以，感谢楼主分享

第四问是不是二分图的最大匹配，匈牙利算法？

umialpha 发表于 2019/04/02 14:29:45
第四题是人车匹配的follow up 。二分图的最大匹配。匈牙利算法。妈呀，看来又要去默写几遍了。

不说我还没看出来，我一直不想去读匈牙利啊，但好像不读不行了

第五轮这个要求高度最小楼主是怎么考虑的？貌似用union算法的话还挺麻烦？

kaipeng21 发表于 2019/04/02 14:52:49


我看有的面经说那题input和馏粑舞不一样给的是一个root，如果是这样的话BFS+set()就能秒了

嗯嗯，给了root的话一个层次遍历（或者bfs）就ok了，感谢

umialpha 发表于 2019-4-2 15:06
嗯嗯，给了root的话一个层次遍历（或者bfs）就ok了，感谢

请问下具体怎么做呢？谢谢