Cruise新鲜电面

面试官是个很nice的印度小哥上来先聊了聊Cruise Product Team大概的划分和他的工作 聊了聊自己的工作

题目就一道 LZ好人不设限了
给一个类似这样的list of list
[
[1]
[2, 3],
[7,3,9]
]
把他想象成一个tree 求root到leaf的m

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

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

e
1的children是2 3
2的children是7 3
3的children是3 9
然后求从root到leaf的path sum minimum

应该是这题吧，https://leetcode.com/problems/triangle/

paihuai1 发表于 2019-1-29 06:50
谢谢楼主的回复，用BFS也可以做吧

我其实想了想没太懂BFS能怎么做
用dfs肯定OK 加个backtracking把长度从底部一路pass上来比较好
但无论怎么样recursive call的overhead其实很大 dp应该是需要的

graduate2018 发表于 2019-2-5 13:49
然后他的描述为什么感觉会有child有两个parent的情况？

如果当成树来解读，是会共享parent的，不过这题没关系，你不用当成树，就当成类似于pascal triangle那种题的layout就好

楼主能具体的解释一下题意么？

可能没说很清楚 想象成binary tree

paihuai1 发表于 2019-1-29 06:15
楼主能具体的解释一下题意么？

见补充啦

神尼玛 发表于 2019-1-29 06:31
见补充啦

谢谢楼主的回复，用BFS也可以做吧

没懂怎么想成tree
是如果在下面一行然后index是index，或者index+1 就是这个node的child吗？

graduate2018 发表于 2019-2-5 08:39
没懂怎么想成tree
是如果在下面一行然后index是index，或者index+1 就是这个node的child吗？

感觉lz的意思是每行的元素个数增加一个。叠起来就像一个三角形一样。

aaddis 发表于 2019-2-5 09:06
感觉lz的意思是每行的元素个数增加一个。叠起来就像一个三角形一样。

然后他的描述为什么感觉会有child有两个parent的情况？