脸书电面

用户id是用整数型的，又一个api是可以获得该用户的所有朋友id，如何得

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

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

gt;B->C->D 就说明AD是3度好友

kevintong 发表于 2017-9-2 14:44
我是自己写的bfs，然后面试官就问我代码什么时候会crash，我说输入不valid时候会crash，然后他很失望，问 ...

我觉得面试官问什么时候会crash是想让楼主做下back of envelope calculation. 例如，假设用户可以有100个好友，用户a到用户b距离是d层的话, 那么running time 就是100 ^ d。 一般cpu的运算速度大概是10^8 operations per few secs => 1年有30M秒 =》 3 * 10^15 => d 大约 14 层 左右。用过用单向dfs的话，而且用户a 到用户b有14层，大概需要1年的时间处理。如果用双向做的话就只需要半年，所以说bi-dfs优化挺多的。

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/

楼主，这道题应该怎么答啊？谢谢。

请问一下楼主，什么叫做几度好友呢？

感觉这道题就应该按照楼主的思路来答啊 bfs和双向bfs来优化 请问fail的原因是什么呢？

应该就是bfs呀，或者双向bfs，为啥会fail呢？

summerlismile 发表于 2017-9-2 13:52
感觉这道题就应该按照楼主的思路来答啊 bfs和双向bfs来优化 请问fail的原因是什么呢？

我是自己写的bfs，然后面试官就问我代码什么时候会crash，我说输入不valid时候会crash，然后他很失望，问我空间复杂度，我跟他讲了，他没反应就在提醒一次说如何降低空间复杂度，我说双向bfs，然后让我coding，我写完了，然后就把我挂了。

kevintong 发表于 2017-9-2 14:44
我是自己写的bfs，然后面试官就问我代码什么时候会crash，我说输入不valid时候会crash，然后他很失望，问 ...

面试官会不会期待的是memory overflow if by BFS?

楼主请问几度好友是什么意思啊？

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

是的 字数补丁补丁

几度好友的意思就是