liveRamp phone interview

刚面完，热乎乎的。。。
刚来就尼玛的抓住我问6-dgree。
我把BFS, bi dimensional BFS， DFS都讲了一遍

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

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

team5个人。之前是4个team，发现效率低然后分开了。
招14个实习，呵呵了。。

啥 6-degree？

houqingniao 发表于 2014-11-21 11:24
啥 6-degree？

http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon

收到拒信了。。。
感觉是挂在，他问我，能不能用DFS，用O(1)的空间找到最短路径。
我印象中好像答案是yes，但是我实在想不出来，我说要么Dijkstra，但是不可能O(1) space。
DFS都是闷头苍蝇瞎往下找，，怎么找出最短路径而且还O（1）space啊。求大神指导

rsun 发表于 2014-11-22 10:51
收到拒信了。。。
感觉是挂在，他问我，能不能用DFS，用O(1)的空间找到最短路径。
我印象中好像答案是yes ...

DFS recursive，不存visited，把所有6步之内的path全部试一遍？

补充内容 (2014-11-25 10:16):
call stack空间O(6)=O(1)

kongweihan 发表于 2014-11-25 10:15
DFS recursive，不存visited，把所有6步之内的path全部试一遍？

补充内容 (2014-11-25 10:16):

我的理解。
1.DFS找到的不一定是最短路径，所以不能找到一个就停下来，必须全走一遍。
2.如果你不存visit，而最短路径在前面，你怎么办？

rsun 发表于 2014-11-25 10:21
我的理解。
1.DFS找到的不一定是最短路径，所以不能找到一个就停下来，必须全走一遍。
2.如果你不存vis ...

1.恩对所以空间是O(1)，时间就长了
2.把已知的最短路径存下来，6步以内空间还是O(1)

当时他还问了我怎么空间O(1) iterative DFS。。

kongweihan 发表于 2014-11-25 13:55
1.恩对所以空间是O(1)，时间就长了
2.把已知的最短路径存下来，6步以内空间还是O(1)

但是我觉得如果dfs的话是不是就不止6步了， 因为6步是指两个人之间存在一条6步的路径，但是dfs在尝试一条路径的时候可能远远超出6步，所以不能简单的说空间是O(1)?

xanadulord 发表于 2014-12-1 12:32
但是我觉得如果dfs的话是不是就不止6步了， 因为6步是指两个人之间存在一条6步的路径，但是dfs在尝试一条 ...

嗯是假设都在6步之内的情况下的

kongweihan 发表于 2014-11-25 00:55
1.恩对所以空间是O(1)，时间就长了
2.把已知的最短路径存下来，6步以内空间还是O(1)

iterative DFS 是用stack来模拟吗

补充内容 (2015-1-16 03:31):
不对，面试官的意思应该就是你说的那个解的意思吧？迭代加深DFS，我猜