狗2轮实习面经

Job Hunting Interview
, , , ,
#1

一共两道题
第一题：
给一个1D array of integers， 找里面1和2（或者2和1）之间的最短距离。

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

我的解法就是TWO POINTERS，比较简单
第二题是个扩展，变成2维矩阵。距离的定义是MAHANTTAN DISTANCE（就是X OFFSET +ＹOFFSET）。如果是对角线的话，距离算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。

#2

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

#3

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

#4

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

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

#5

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

#6

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

#7

一维那道？

参考下面这个

#8

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

#9

取决于1和2的数量吧

#10

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

#11

贴一个学生写的代码

mmexport1545857059045
mmexport1545857059045.jpg795×768 53 KB

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

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

#12

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

#13

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