📣 独立日限时特惠: VIP通行证立减$68
楼主: kevintong
跳转到指定楼层
上一主题 下一主题
收起左侧

脸书电面

🔗
白丁117 2017-9-3 02:38:31 | 只看该作者
全局:
say543 发表于 2017-9-2 15:01
面试官会不会期待的是memory overflow if by BFS?

可以解释下啥意思吗?谢谢
回复

使用道具 举报

🔗
白丁117 2017-9-3 02:39:16 | 只看该作者
全局:
kevintong 发表于 2017-9-2 15:33
是的 字数补丁补丁

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

使用道具 举报

🔗
nickdgu 2017-9-3 07:56:33 | 只看该作者
全局:
感觉bi-bfs共偏向于时间优化吧
这个题一人几千个好友的话4-5度可能就10e9-10e15了。。
要说优化的话 pre-allocate space,复用空间,再用set存每一层。。。只保留一层啥的。。。

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

使用道具 举报

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

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

使用道具 举报

🔗
nickdgu 2017-9-4 00:32:21 | 只看该作者
全局:
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/
回复

使用道具 举报

🔗
 楼主| kevintong 2017-9-5 17:52:10 | 只看该作者
全局:
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,你这算时间复杂度不公平啊
回复

使用道具 举报

🔗
nickdgu 2017-9-6 04:29:25 | 只看该作者
全局:
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
回复

使用道具 举报

🔗
f1371342385 2017-9-6 07:48:59 | 只看该作者
全局:
LZ 您有没有考虑detect cycle了吗 有没有考虑有环的情况?

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

使用道具 举报

🔗
jigsaw_Becky 2017-9-6 09:58:35 | 只看该作者
全局:
你好,请问是只需要是几度好友就行了,还是需要把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.
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表