国内+加拿大SDE Intern面试经历 Airbnb，微软，腾讯，字节，Amazon

nyc 发表于 2021-4-11 12:50
楼主可以详细说一下airbnb的第二题吗~ 超级感谢！！！

就字面意思。。。迷宫中有炸弹，要求找出从左上（0，0）出发到（m，n）的最短路径，如果有多种最短路径，要求返回的路径中任意一点到炸弹的距离最远，相较于其他最短路径。解法是bfs+二分，我用了bfs+memory面试官不满意。

cocowine 发表于 2021-04-10 22:35:00
就字面意思。。。迷宫中有炸弹，要求找出从左上（0，0）出发到（m，n）的最短路径，如果有多种最短路径，要求返回的路径中任意一点到炸弹的距离最远，相较于其他最短路径。解法是bfs+二分，我用了bfs+m

为啥二分是最优解？求说下思路

229868784 发表于 2021-4-11 16:20
为啥二分是最优解？求说下思路

面试官告诉我是二分，让我回去想，然而。。。我也没想出来

cocowine 发表于 2021-04-11 02:08:27
面试官告诉我是二分，让我回去想，然而。。。我也没想出来

多谢楼主 只有一个炸弹吗？ 需要打印路径坐标？ 怎么感觉应该是贪心

匿名者 发表于 2021-4-11 18:35
多谢楼主 只有一个炸弹吗？ 需要打印路径坐标？ 怎么感觉应该是贪心

可以有多个炸弹，不需要打印路径，返回的是该路径离炸弹的最短距离和路径长度

cocowine 发表于 2021-04-11 04:24:16
可以有多个炸弹，不需要打印路径，返回的是该路径离炸弹的最短距离和路径长度

这个路线到炸弹距离最短怎么去界定？求一点详细的描述

cocowine 发表于 2021-04-11 02:08:27
面试官告诉我是二分，让我回去想，然而。。。我也没想出来

第感觉是二分和炸弹的最小距离，距离内的格子全部当成墙

楼主面Airbnb 的时候做oa了么？

sakuya9t 发表于 2021-4-11 22:25
第感觉是二分和炸弹的最小距离，距离内的格子全部当成墙

求说一下思路？
这个matrix里是只有0和1？1代表炸弹，0代表可以通行的位置？

匿名者 发表于 2021-4-11 21:54
这个路线到炸弹距离最短怎么去界定？求一点详细的描述

路线任意一点到任意炸弹的最短距离就是整个路线到炸弹的最短距离