P****d
发帖数: 137 | 1 原帖地址
http://www.mitbbs.com/article_t/JobHunting/32595949.html
“You are in a social networking, and you want to share a picture to your
friends and your friends of friends. How can you find out your friends and
your friends and friends efficiently.
这个也是不需要写code。我只想到了最笨的breadth first search 的方法，O(n^2).然
后被问怎么能做到低于n^2。提示说是用friend relation的symmetry。我觉得即使用了
symmetry也还是O(n^2)啊。不懂，请大牛提示！“
friend relation symmetry是说找另外一个人同时做BFS，然后自己和那个人一起做BFS
做一层看有没有共同好友吗？如果有共同好友那个人就是我的Friend of Friend吗？这
样更慢吧
自己这里做两层BFS，可以保证找到所有的n^2个friend of friend (n假设为平均每个
人的好友个数），如果要用friend relation symmetry是的话，要对这个社区里所有的
用户都做一次一层的BFS，加入社区里的用户一共 有N个，那么就得做Nn 次，这比BFS
两层慢多了吧 |
A*********c
发帖数: 430 | 2 如果要找degree 2的所有朋友，怎么beat O(n^2)?
我有俩朋友，一个伊朗的一个北朝鲜的，这俩互相不认识。每人又认识俩，这四个
dgree 2的人，俩俩不认识。
怎么优化？
如果给出了某两个人，判定他俩是不是degree 2, 看friend list交集就行了。
BFS
【在 P****d 的大作中提到】
: 原帖地址
: http://www.mitbbs.com/article_t/JobHunting/32595949.html
: “You are in a social networking, and you want to share a picture to your
: friends and your friends of friends. How can you find out your friends and
: your friends and friends efficiently.
: 这个也是不需要写code。我只想到了最笨的breadth first search 的方法，O(n^2).然
: 后被问怎么能做到低于n^2。提示说是用friend relation的symmetry。我觉得即使用了
: symmetry也还是O(n^2)啊。不懂，请大牛提示！“
: friend relation symmetry是说找另外一个人同时做BFS，然后自己和那个人一起做BFS
: 做一层看有没有共同好友吗？如果有共同好友那个人就是我的Friend of Friend吗？这
|
P****d
发帖数: 137 | 3 我其实和你一个意思。。。觉得原帖里所谓的面试官提示其实是错的
【在 A*********c 的大作中提到】
: 如果要找degree 2的所有朋友，怎么beat O(n^2)?
: 我有俩朋友，一个伊朗的一个北朝鲜的，这俩互相不认识。每人又认识俩，这四个
: dgree 2的人，俩俩不认识。
: 怎么优化？
: 如果给出了某两个人，判定他俩是不是degree 2, 看friend list交集就行了。
:
: BFS
|
A*********c
发帖数: 430 | 4 嗯，理解。我其实也是自问自答，呵呵。
【在 P****d 的大作中提到】
: 我其实和你一个意思。。。觉得原帖里所谓的面试官提示其实是错的
|
z******g
发帖数: 271 | |
