脸书电面

say543 发表于 2017-9-2 15:01
面试官会不会期待的是memory overflow if by BFS?

可以解释下啥意思吗？谢谢

kevintong 发表于 2017-9-2 15:33
是的 字数补丁补丁

请教lz 什么是memory overflow if by bfs？可以举例子吗？

感觉bi-bfs共偏向于时间优化吧
这个题一人几千个好友的话4-5度可能就10e9-10e15了。。
要说优化的话 pre-allocate space，复用空间，再用set存每一层。。。只保留一层啥的。。。

再扯淡一点可以说根据六度理论bi-bfs往上下各搜八九层大概就可以停了。。。

nickdgu 发表于 2017-9-3 07:56
感觉bi-bfs共偏向于时间优化吧
这个题一人几千个好友的话4-5度可能就10e9-10e15了。。
要说优化的话 pre- ...

bi-bfs时间和bfs时间是一样的，差别就只有空间。

logicpku 发表于 2017-9-3 10:48
bi-bfs时间和bfs时间是一样的，差别就只有空间。

哦对。。。bi-dfs是时空都有优化。。。
bi-dfs 是 O（b^d/2) dfs是O(b^d)
可以看下这个图https://mhesham.wordpress.com/tag/bidirectional-search/

nickdgu 发表于 2017-9-4 00:32
哦对。。。bi-dfs是时空都有优化。。。
bi-dfs 是 O（b^d/2) dfs是O(b^d)
可以看下这个图https://mhesh ...

bfs starting point走一步算1
bi-bfs starting point 和ending point 分别走一步算1，你这算时间复杂度不公平啊

kevintong 发表于 2017-9-5 17:52
bfs starting point走一步算1
bi-bfs starting point 和ending point 分别走一步算1，你这算时间复杂度 ...

没啊 分别走一步是2嘛
总共是 2 * b^d/2 < b ^ d/2 * b ^ d/2

LZ 您有没有考虑detect cycle了吗 有没有考虑有环的情况？

补充内容 (2017-9-6 07:49):
还有一种情况就是space占用太多了，会发生memory leak，尤其在4度 5度左右的时候

你好，请问是只需要是几度好友就行了，还是需要把path打印出来？谢谢！

logicpku 发表于 2017-9-3 10:48
bi-bfs时间和bfs时间是一样的，差别就只有空间。

虽然big-o上复杂度是一样的，可是区别还是挺大的。假设系统用bfs只能支持到搜索朋友的朋友的话，那么同样的系统，bi-bfs就能支持a friend of a friend of a friend of a friend.