非死不可电面

非死不可电面， 45分钟， 面试官是美国人， 说话巨快。

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

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

用dfs算树的depth = max(left, right) + 1, 同时更新longest = max(longest, left + right - 1)

bamboochan 发表于 2019-9-20 14:31
楼主有消息了吗 我今天刚面的

今天收到回复了， onsite了， 希望大家都能拿到offer。 ^-^

codyman 发表于 2019-9-23 17:16
这题有LeetCode原题吗

leetcode 543.  原题计算有多少条边，这里计算当中有多少个点。

第二道题是不是先拿到child-to-parent map,然后再做bfs?

楼主有消息了吗 我今天刚面的

梅亮 发表于 2019-9-20 09:01
第二道题是不是先拿到child-to-parent map,然后再做bfs?

我用DFS， BFS也需要全部便利一遍，还需要额外空间

derekz2001 发表于 2019-9-20 21:29
我用DFS， BFS也需要全部便利一遍，还需要额外空间

lz的思路是先找到最低公共祖先，然后再从公共祖先出发找那两个节点 （这一步dfs的话是不是也需要用stack额外空间）？

shpittsaustin 发表于 2019-9-22 08:08
lz的思路是先找到最低公共祖先，然后再从公共祖先出发找那两个节点 （这一步dfs的话是不是也需要用stack ...

stack确实需要额外空间， 但是空间是O(h) ，h是树的高度， 理论是更少空间， 而且一般空间是不是只算你定义的变量

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

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

zjlvmiao 发表于 2019-9-22 10:31
用dfs算树的depth = max(left, right) + 1, 同时更新longest = max(longest, left + right - 1)

这题有LeetCode原题吗