狗狗 conversion interview

发个 狗家 conversion interview 面经攒人品。 地点 moutain view。

第一轮：
第一题， find next greater element。
第二题， find the longest mountain in an array. 跟蠡口不一样。 这里mountain的定义是  A[i:j+1] 是一个mountain 如果 for any i<k<j,  都有  A[k]>A[i], A[k]>A[j]。 楼主给了平方的解法。 面试官似乎满意。

第二轮：
拓扑排序的题。 给你一个dimension 代表一个squre， 给你一个number of elements，在给你一堆rule， 要把这些elements 排到这个square里根据rule。 rule是 像 “”0 left 1“”， 表示element 0 要在element 1 的左边，  “”1 above 3“” 就是一要在3 的上面。 输出是这些element的坐标， 如果有多个答案， 只需输出一个。 例子， dimension： 3， element 5， rule “”0 left 1“” “”1 left 2“”， “”2 left 3“” “”2 above 4“” return -1， 因为在dimension为3 的情况下放不下。 如果dimension改为4： 那答案就可以是 （0： （0， 0）， 1：（0， 1）， 2：（0,2）， 3：（0,3），  4：（1,1））。

. check 1point3acres for more.不设积分了， 攒人品。

感觉加了dimension要复杂很多啊

yulisa1 发表于 2020-1-17 06:44
感觉加了dimension要复杂很多啊

我当时是initial i, j, 为0， 0.  然后一行一行的按着topo的顺序堆（j++）, j 到头了 i +=1 来堆下一行的。 面试官没反对。

ycui11 发表于 2020-1-17 06:49
我当时是initial i, j, 为0， 0.  然后一行一行的按着topo的顺序堆（j++）, j 到头了 i +=1 来堆下一行的 ...

那你ts的时候怎么区别对待上面和左边的呢

第一轮第二题的山是zigzag的？

yulisa1 发表于 2020-1-17 10:50
那你ts的时候怎么区别对待上面和左边的呢

我是针对row 和column level 各做一次ts， output是 两个list of list， 分别代表row和columnlevel的topo sort。 针对同一个row level的element 尽量让他们在同一个row 根据column level定他们的column index， 如果不能放在同一个row了 就放在下一个row并且column还原为0.  这个row level的拍完了 拍下一个row的 并且row index+1.

wtcupup 发表于 2020-1-17 11:04
第一轮第二题的山是zigzag的？

对的。 只对两个end有要求。 中间可以zigzag