狗2轮实习面经

一共两道题
第一题:
给一个1D array of integers, 找里面1和2(或者2和1)之间的最短距离。

       [ 1 5 9 7 3 2 4 1 ]
                   |---|
                     2

我的解法就是TWO POINTERS,比较简单
第二题是个扩展,变成2维矩阵。距离的定义是MAHANTTAN DISTANCE(就是X OFFSET +YOFFSET)。如果是对角线的话,距离算2。

比如这个
[
9 1 8 1
2 5 6 3
5 0 4 6
]

最短的就是(0,1)和(1,0)之间的距离2。
我的解法就是BFS。从1或者2开始都可以,存最小值就行。。。

INPUT:
1)给了N个雷达的坐标和探测距离,比如这样的(xi, yi), ri。xi yi是第i个雷达的位置,ri是它的探测距离。
2)给了一个RECTANGLE ALLOWABLE AREA,比如(a0, b0), (a0, b1), (a1, b1), (a1, b0)。
allowable area:

(a0, b0) --------------- (a0, b1)
    |                       |
    |                       |
(a1, b0) --------------- (a1, b1)

问题:一辆在那个ALLOAWABLE AREA的LEFT BOUNDARY (按上图,就是在(a0,b0)和(a1,b0)那条线上)的车能不能走到RIGHT BOUNDARY但不被任何一个雷达发现。
注意汽车最开始的位置没有固定,任何在LEFT BOUNDARY上面的点都可以当作起始位置
我的办法就是UNION FIND。

bfs 感觉也不太好写吧。需要加 memorization

有很多个1很多个2怎么办

一维的话用 word distance的思路可以做

二维的话我感觉bfs不是最优解啊

而且第二题理论上应该沿用第一题的思路,x和y各是一维的操作,然后把两个维度叠加

第一题先找1和2所有的位置,再找2个sorted array min diff,o(n),follow up也可这么做?不知道怎么存位置之后算min diff会比较快?

一维那道?

参考下面这个

说的是二维,一维确实是原题:grin:

取决于1和2的数量吧

感觉不需要。就是把雷达cover的地方标记出来,也就是不能走的,然后找路径

贴一个学生写的代码

这里是把所有的1作为起点做bfs

其实1和2在扫一遍的时候全部知道了,可以根据数量选择1或2

感觉第一题第二个小问双向bfs会不会好点?

这题其实解法有很多种,各有tradeoff。
比如先只从一个点做bfs,用了n步,那么接下来超过n 步就停。
还有就是把所有的1和2找出来以后两两组合算。
双向bfs涉及的问题还是要选1和2