Facebook SWE Intern 面经

邓轰 · 2018-12-18 09:20:48

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

x

两轮背靠背面试。
第一轮问了两个题，第一个题是check words order，第二个是有向无环图中从指定起始点到指定终点的最长路径长度。

第二轮第一题是蠡口散思，但问的是目

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

在写code前多交流，问清楚有哪些限制条件比较稳妥一些。希望两周后能有好的结果吧，也感谢地里大家之前提供的面经。

flygogogo · 2018-12-20 01:10:05

请问DAG中从指定起始点到指定终点的最长路径长度怎么做的? DFS遍历吗? 谢谢 !

邓轰 · 2018-12-20 09:12:18

flygogogo 发表于 2018-12-19 12:10
请问DAG中从指定起始点到指定终点的最长路径长度怎么做的? DFS遍历吗? 谢谢 !

我是用BFS写的，写完了讨论我说DFS应该更好，问这道题时没多少时间了，当时也没细问

77777ccccc

check words orders请问是利口哪题呢

Ronald4545

邓轰发表于 2018-12-20 09:12
我是用BFS写的，写完了讨论我说DFS应该更好，问这道题时没多少时间了，当时也没细问

toplogical sort 更好

yus252

如果是Absolute shortest path应该是 DFS 并且用Queue边sort边explore，如果更加追求效率(Faster Runtime）则是A* Algorithm。不过A* 也是DFS, 只不过是有Weight的DFS。