脸书电面跪经

codyman 发表于 2020-1-12 16:26
这题好像脸书tag里没有？是新题吗

我也没印象，看上去像是带权重的有向图遍历，indegree乘上权重来算。

为什么会有最小值，答案不是唯一的吗

看题目感觉是典型的Dijkstra最短路径问题。第一个完成所有任务的路径即为答案。

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

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

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

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

啊，我明白了
用BFS + indegree 拓扑排序，queue中存indegree为0的点，由于顶点带权重，那么用priority_queue每次pop出最大权重，即这一层完成所有indegree为0任务所需最大时间，弹出所有任务，更新邻近顶点indegree，为0的再加入queue
这样对吧？

第一题没看懂，楼主能不能详细解释下

第一题是determinde的吧，要完成某个任务，必须完成他的所有子任务，然后子任务又必须要完成它自己的子任务；如此类推，直到某个任务不需要子任务。用一个Set，记录所有的任务并去重，最后把任务时间加一下。

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

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

lsm128 发表于 2020-1-14 11:47
看大家的讨论又仔细想了下，这道题应该是是求一个AOE网（边活动网，一种有向带权图）的关键路径（关键路径 ...

有可能是我描述不明确，让大家想多了。但是直到完事了我也没想明白。甚至都不确定我是否真的理解了题意。但是我已经把面试官给我的信息都放上去了。