Palantir new OA flood map

have anyone done new oa for palantir called flood map

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

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

帖一下


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

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

1 Like

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

如何解呢?