狗2轮实习面经

第一轮

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

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

第二轮

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

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

求加大米！！！！！！



补充内容 (2018-12-5 13:59):

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

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

补充内容 (2018-12-5 14:00):

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

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

lzx801 发表于 2018-12-16 00:05
额，请问第一轮第二题的BFS可以麻烦详细说一下吗？
如果是单纯的bfs的话，貌似是需要对于矩阵中的每一个1 ...

可以一开始就把所有的1的位置都加到同一个queue中，然后做level-order遍历。当第一次找到2时的遍历过的level数即为1和2之间可能的最短距离。

感谢楼主提供思路。先找出接触了上下边的雷达，然后找雷达之间的连接，根据edge做union find，若上下面连通就是通不过，不连通就是通的过。

想了一下才发现第一题的第二问原来是自行车...

lz 请问，关于第二题中，距离如何定义？以及车是否只能上下左右移动？（已加米

H4veFunC0din9 发表于 2018-12-5 04:37
lz 请问，关于第二题中，距离如何定义？以及车是否只能上下左右移动？（已加米

距离是euclidean distance吧。就是(x-xi)^2 + (y-yi)^2 = ri^2。
面试官没说，但是从题意，我感觉车是可以自由移动，没有限制。
我觉得比较简单的解法是从雷达角度出发，用union find。如果几个雷达覆盖了某一条垂直线（比如(a0, b2)到(a1, b2)）的话，那就说明汽车没办法从左走到右不被探测到。



补充内容 (2018-12-5 13:57):
我之前的那个allowable area图的坐标有点问题（x和y标反了），哈哈。参看更新部分
所以如果几个雷达覆盖了某一条垂直线（比如(a2, b0)到(a2, b1)）的话，那就说明汽车没办法从左走到右不被探测到。

mtspring 发表于 2018-12-5 13:53
距离是euclidean distance吧。就是(x-xi)^2 + (y-yi)^2 = ri^2。
面试官没说，但是从题意，我感觉车是可 ...

还是没太明白… lol

要是有两个雷达覆盖的是从a2,b0到a3,b1的斜线呢？（a0 < a2 < a3 < a1）

mtspring 发表于 2018-12-5 13:53
距离是euclidean distance吧。就是(x-xi)^2 + (y-yi)^2 = ri^2。
面试官没说，但是从题意，我感觉车是可 ...

诶，是不是根据雷达之间是否重叠，然后用union find来找所有雷达的连通子图，每个联通子图可以分开判断？

额，请问第一轮第二题的BFS可以麻烦详细说一下吗？
如果是单纯的bfs的话，貌似是需要对于矩阵中的每一个1都做一次bfs，才能得到最小距离？