狗onsite

狗狗匹兹堡
1. perfect tree 以pair 的形式输出所有的edges，参数给定了这个树的height和branch。perfect tree是complete的，并且每个节点值是

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的server，0表示好的server.有一个机器人从房间的右下角进去，要求逐行修这些server,求最短路径。
   

1. def minstep(matrix):
   
2.     N = len(matrix[0])
   
3.     M = len(matrix)
   
4.     data = [[0,0] for x in xrange(M)]
   
5.     for index in xrange(M):
   
6.         #right
   
7.         data[index][1] = (N - matrix[index].index(1))*2 -1
   
8.         #left
   
9.         data[index][0] = (N - matrix[index][::-1].index(1))*2 - 1
   
10.         
    
11.     cache = {}
    
12.     def dfs(leftright,level):
    
13.         if level == 0:
    
14.             if leftright == 0:
    
15.                 return N
    
16.             else:
    
17.                 return data[level][1]
    
18.         if (leftright,level) not in cache:
    
19.             cache[(leftright,level)] = min(dfs(leftright,level-1) + data[level][leftright], dfs(1-leftright,level-1) + N)
    
20.         
    
21.         return cache[(leftright,level)]
    
22.    
    
23.     return min(dfs(0,M-1),dfs(1,M-1))
    
24. 
    

复制代码

写了下第三题 欢迎大家讨论 :)  思路就是dfs(leftright,level) 表示第level行进 从左或者从右出 然后memorization一下

yyyxxxccc 发表于 2018-4-25 09:51
是的必须逐行修，并且你没有办法从一行的中间直接进入下一行。必须从一行的最左边或者最右边进入下一行

如果必须是最左或左右，如果每行都有坏的，那岂不是就是左一行右一行就可以了？

markpen 发表于 2018-4-12 06:19
楼主，第三问是要求每一行修完之后再修下一行吗？

是的必须逐行修，并且你没有办法从一行的中间直接进入下一行。必须从一行的最左边或者最右边进入下一行

感谢楼主的分享，十分受益~

感谢楼主，只面了三道题啊？

楼主，第三问是要求每一行修完之后再修下一行吗？

第四题实在记不清楚了

bigdog 发表于 2018-4-12 05:18
感谢楼主，只面了三道题啊？

第四题实在想不起来

第二题能讲一下思路吗？

第二题  longest increasing path in DAG 感觉可以用terminal node做拓扑排序 类似于力扣 那道longest increasing path in matrix

第三题感觉是一道DP 状态跟上一行从左进 从右进 有关