Google 实习两轮电面+加面

一直想发忘记发的面经……

一月初的两轮电面：
第一轮：
第一题 把一个linked list里面每隔一个node删掉一个 比如 1-2-3-4-5变成1-3-5这样 如果是1-2-3-4就返回1-3-4
第二题 地里传过的同义词的题目 很简单用hashmap

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

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

ht的定义就是该node的weight加上他的children的subweight之和。

上周说送了HC现在还没结果……虚得不行 求人品QwQ

请问LZ加面是用Union Find做的吗

gyf930424 发表于 2018-2-17 02:21
请问LZ加面是用Union Find做的吗

我用的topological sort做的

加面不是简单做个tree就好了吗？(类似于 max substree sum?)为什么会提到Union Find， toposort。。还是我理解错误？

看了一下原来是*章上过课的才能写的题。。不过写法外面有

https://yeqiuquan.blogspot.com/2017/03/lintcode-596-minimum-subtree_8.html
求lz看下是不是类似这么写的、不需要toposort和uf 还是我理解错题了

vtiaocao 发表于 2018-2-17 07:13
加面不是简单做个tree就好了吗？(类似于 max substree sum?)为什么会提到Union Find， toposort。。还是我 ...

我的理解topological sort就是很抽象地建一个tree……但是我觉得这个题目跟max subtree sum好像没什么关系诶

ws17 发表于 2018-2-18 14:22
我的理解topological sort就是很抽象地建一个tree……但是我觉得这个题目跟max subtree sum好像没什么关 ...

对，是和max 没啥关系。。但max那个会traverse所有的subtree sum，然后找出最大的。这题似乎就是返回所有的subtree sum就行。

我也扯远了。。。我应该这么说: 解法的重点应该大概就是这一行，对吧 - (换成multi-tree而不是binary-tree的版本)

        ResultType leftResult = helper(root.left);
        ResultType rightResult = helper(root.right);
        ResultType currResult = new ResultType(root,
                leftResult.sum + rightResult.sum + root.val);

补充内容 (2018-2-19 01:46):
在搭建出来一个tree(graph)之后

谢楼主分享, 祝楼主好运

vtiaocao 发表于 2018-2-19 01:46
对，是和max 没啥关系。。但max那个会traverse所有的subtree sum，然后找出最大的。这题似乎就是返回所有 ...

嗯 但是用topological sort做就省掉你建tree这一步了

ws17 发表于 2018-2-19 15:46
嗯 但是用topological sort做就省掉你建tree这一步了

是…
不过还是没懂这题怎么做toposort。还是说就是BFS一波走下去？
怎么做啊。。求教

vtiaocao 发表于 2018-2-20 08:21
是…
不过还是没懂这题怎么做toposort。还是说就是BFS一波走下去？
怎么做啊。。求教

就是比如a是b的parent那么就想象一个edge from b to a，然后对于整个graph做一个topological sort就能保证weights correctly accumulate了。我当时是class里面添加了一个field subweight。