谷歌onsite面经

jy_121 发表于 2019/04/04 02:20:49


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

层次遍历的时候如果发现遇到已访问的说明就是多余的边了。然后删除这条边。

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

二叉树多余一条边意思不是有至少一个节点有两个parent吗？删哪条边都不会影响树的高度啊

umialpha 发表于 2019-4-4 09:03
层次遍历的时候如果发现遇到已访问的说明就是多余的边了。然后删除这条边。

为什么这样remove后的tree就是高度最小的呢？

jy_121 发表于 2019-4-4 09:46
为什么这样remove后的tree就是高度最小的呢？

因为用层次遍历，每次访问新的节点就是新的一层，高度+1，如果你不去掉这一条边，而是去掉之前访问的那条边，那么高度肯定没有原来的小（最多是一样高）

mhsasd 发表于 2019-4-4 09:23
二叉树多余一条边意思不是有至少一个节点有两个parent吗？删哪条边都不会影响树的高度啊

我猜可能是这样， 1->2, 1->3, 2->4, 3->4如果你删除1->2，那么还是一个树，但是高度变成4了。如果input是按照node.left, node.right这样给的，就是你的意思了。

umialpha 发表于 2019-4-4 09:48
因为用层次遍历，每次访问新的节点就是新的一层，高度+1，如果你不去掉这一条边，而是去掉之前访问的那条 ...

明白了，谢谢

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

第四题是标准的 二分图最大匹配。匈牙利算法吧。

第四题我一开始也以为是二分图问题，但被面试官否认了，然后在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)这条边不会影响全局最优。（有点像贪心的意思）。

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

dragonlanding 发表于 2019-4-6 11:36
第四题我一开始也以为是二分图问题，但被面试官否认了，然后在hint下, 才反应过来是toposort，code没写完， ...

需要考虑

a -> e
b -> e
c -> e

这类情况吗，很多人喜欢一个人。

这种情况下不太好删吧，除非维护一个deleted的set