DoorDash OA2023

两道题，好像65分钟。

一道shortest route，图贴下面了。之前看见了有的贴

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

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

网妖灵耳久。贪心算法，蛮简单的。

求加米！攒个好运！

感觉第一题没有negative edge可以上dijkstra，有negative edge可以用bellman-ford。dijkstra停止条件为visit过中间点的第一个到达终点的path。bellman-ford往回走的时候需要注意path要经过中间点。

请问下第一题思路，刚做完这个不会写

ashibatian 发表于 2022-10-02 19:33:51
请问下第一题思路，刚做完这个不会写

我也不会…我就是建了个哈希表，每个节点是key，对应的value分别是 neibor，weight，neibor2， cost。。。然后后面我就写不出来了，我个人感觉是得bfs搜，。。。

楼主收到后续了吗

匿名用户 发表于 2022-10-03 14:46:26
楼主收到后续了吗

没呢 刚做完几天

请问是ng吗

予我挚风 发表于 2022-10-03 20:30:27
请问是ng吗

是intern哦

第一题我的思路是两次 Dijkstra
第一次做 a-》c，然后把最短路线记录下来
第二次做b -》c，然后如果遇到之前记录的最短路线，把距离算为0