斯内普店面+吐槽

来自APP · 2021-9-21 05:47:15

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

几周前的snap电面到现在都不出结果发邮件也不回比他后开始的面试连onsite都面完了 offer都拿到

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

每个节点的最长时间，然后再在每个节点的最长时间里取最大值。望大神纠错。

sfmnrmnv

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

sfmnrmnv

直接拓扑排序就行了吧，o(n)

来自APP · 2021-9-21 06:57:38

sfmnrmnv 发表于 2021-09-20 15:04:11
直接拓扑排序就行了吧，o(n)

我说的有歧义先是拓扑排序然后再利用顺序做一次dp 对于每个节点求出所有汇入该节点的路径的最长完成时间
复杂度是o（n），但是要遍历两次。
能具体说明一下只要一次遍历不用dp就能做出来的方法吗？

来自APP · 2021-9-21 13:39:31

sfmnrmnv 发表于 2021-09-20 16:06:25
你拓扑排序在释放每一个点的时候，同时更新该点所指向点的最大时间值（需要开一个O(n)的数组来记录每个点的最大时间值），同时用一个全局变量更新最大值，等所有点走完后这个全局变量的值就是result

赞👍 懂了

garyyang

topological sort不是唯一解，这里面求的是并行走完所有节点的最优解，不明白都上怎么做的，能否分享链接？

garyyang

应该是用dfs找到没有dependency的节点，然后通过它们bfs找出总layer数才是答案？

来自APP · 2021-9-22 08:13:34

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

zn88358800

应该就是topo order 每一层indegree为0的 node的最大值的和？

wwx_27

求个题号