Palantir new OA flood map

Job Hunting Interview
, , , ,
1

have anyone done new oa for palantir called flood map

2

类似 https://leetcode.com/problems/flood-fill/ 吧

3

it is 4 question according to 1point3acres but not enough rice to see

4

帖一下

p家flood map⼀小时，三道题，每道题基于上⼀题提升难度。
然后具体说⼀下三道题：

第⼀道： ⼀个二维数组，把⾼于相邻8个⽅向的数mark 1 ，其他mark 0， 输出新数组。
第⼆道： 感觉已经有点难了，如果可以从最⾼点忘小于此点的位置流水，然后情况复合mark。
第三题：压根没做，看了一下，第⼀题是严格大于周围，第三题是可以等于周围，然后再复合mark数组

重新解释一下第二题，可能之前说的不太清楚，哈哈。 第一道题得出了标点为1的高点，第二题从高点出发，周围小于高点的地方可以理解为可以流水，以此为递归，得出一个可以覆盖范围的数组，几个高点综合复合，流‌水没有的地方为0，流过一次的地方为1，多次为2. 得出输出数组。

BTW， 输入数组的形式可见leetcode 733

来和大家分享一下我的帕兰提尔跪京吧。

首先，我是海投然后过了‌1-2星期收到的OA，给了7天的时间做OA，没有给我extension。
第二，拿到的题目是Flood Map，疯狂搜索了一圈没有任何这个题目的信息。猜是新题目，HR也没有给延的情况下，就知道我这样的**估计要跪了。憋到deadline前打算玩一玩。
第三，题⽬的内容。⼤致就是⼆维数组中，找出所有highlight的数。关于这个highlight的数的定义，就是要⽐它所有的邻居都大。是highlight的数就标做1，不是的话就标做0。关于邻居的定义是，前后左右+四个对角都算是邻居。所以，input给的是⼀个⼆维数组，output的要求是一个由0和1组成的存结果的⼆维数组。

  1. highpoints，给一个矩阵，找出所有比邻居（上下左右，对角也算，不考虑边界就是8个咯）都严格大的点，返回一个
    mask矩阵。
1 2 3    0 0 0
4 5 8 -> 0 0 1
9 7 0    1 0 0
  1. 找到highpoints后，我们说所有highpoint上都有水源。水会像附近的比它严格低的点流，会一直蔓延下去，相当于构成一
    个水域图。
    先用第一题的code找出highpoints
1 2 3    0 0 0
4 5 8 -> 0 0 1
9 7 0    1 0 0

这两个highpoint的水域图是
8这个highpoint可以流到除了9以外的所有区域
1 1 1
1 1 1
0 1 1
9这个highpoint可以覆盖整张图
1 1 1
1 1 1
1 1 1
要去把所有的水域图相加返回一个同样size的矩阵，那么这个例子就是
2 2 2
2 2 2
1 2 2
3. 找到所有的高原，高原的定义是一组连起来的等高的点，这些点都比它的邻居高，找出所有高原，返回一个mask矩阵

1 2 3 4    0 0 0 0
5 5 5 2    1 1 1 0
1 1 1 1 -> 0 0 0 0
0 0 0 9    0 0 0 1

例子不记得它原来的了，是我现编的。。
第一题是模拟，后两题用dfs都能过它给的test cases。
总之，时间有一小时还蛮充裕的，差不多20来分钟就能写完。

楼主第二个测试中，以8作为高原是不是也覆盖不了7，然后9作为高原是不是覆盖不了8和3呢

不是。highpoint一定是高原，高原不一定是highpoint

5

谢谢楼主分享。找了半天就看到你分享的最有用了

1 Like
6

请楼主澄清下第三题呢。 我的理解是： 第三题用第一题的解法就可以啦。只是第⼀题highpoint是严格大于周围，第三题高原是大于等于周围。没想明白为什么要用dfs呢。谢谢！

7

如何解呢？