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 | |