狗家 匹村 现场面 面经

sfsttz 发表于 2018-9-22 06:24
第一题是列数显著小于行数码？

不是哦，刚开始给我的时候说这个修的机器可能是100*100台。我这里只是举例子。

lisheng1000 发表于 2018-9-22 06:41
楼主 第三题是要求实现areAllied(A,B) 和areAssociated(A,C)   方程嘛？

是的。实现这两个function

lisheng1000 发表于 2018-9-22 06:47
这句话没看懂 呀  什么事 多于10s内  如何输出Stdout print多于10s内间隔的String

距离上次打印“foo”的时间超过了10秒就System.out.println("foo"), 否则不print。

补充里面不能贴图，第一题的解释请看9楼，如果哪位大神有思路，求贴一下大家看看~感谢!

论坛匿名用户 发表于 2018-9-22 07:20
是我没讲清楚，因为technician被机器挡住，所以每次他要选择是原路返回，还是往前走，要么走到row的最右 ...

感谢解释，但是还有个问题不解。比如为什么0的位置不能直接走下去，被机器挡住不是应该只有x的位置吗？

deeper99 发表于 2018-9-22 13:36
感谢解释，但是还有个问题不解。比如为什么0的位置不能直接走下去，被机器挡住不是应该只有x的位置吗？

题目就是这样规定的，0是我自己画的，面试官没有画matrix，只画了一堆点，而且没坏掉的机器也存在，规定情境就是穿不过去的。我感觉是面试官是为了简化题目，如果是能直接往下走就是np hard的问题。

楼主第一题给大家提供一个思路吧，其实不是找最短路径。因为小人每次走到本行的最后一个坏掉的机器，都要开始做选择，是要走到这一行的最后往下，还是原路返回。所以其实matrix的cols是相关的，没有必要去建立这个matrix，可以用TreeMap存（k,v） k = 行数，v = 本行对应的所有的列。然后iterate整个map的key，每次记录上一次走到的最后一个位置currPos(列数），和下一行最大值最小值nextMax和nextMin，m * n的机器，每次看n - currPos +
n - nextMax >  nextMin + currPos。如果是，就reverse 下一列，加到结果里面，并记录最后一个位置的currPos，以一下次用。希望能对大家有帮助。

论坛匿名用户 发表于 2018-9-22 07:20
是我没讲清楚，因为technician被机器挡住，所以每次他要选择是原路返回，还是往前走，要么走到row的最右 ...

讲真，楼主你是不是把问题想复杂了，如果不考虑竖着走，直接row*col 边走边修不就好了，
我觉得面试官的意思是给你一个矩阵，里面0是可以走的，1是要修的机器，遇到
坏的机器就计数器加1，直到修完，就是dfs找最短路径

补充内容 (2018-9-23 01:09):

第三题是union find,第四题是里扣616

chuqianyiding 发表于 2018-9-23 00:33
讲真，楼主你是不是把问题想复杂了，如果不考虑竖着走，直接row*col 边走边修不就好了，
我觉得面试官的 ...

修机器的人每次修一列的时候，只能走到最右边再往下，或是原路返回从最左边往下，这个是面试官的要求，在一开始的时候这么跟我明确过了，不是楼主凭空说的哈~