问一道GOOGLE有点像设计题的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道GOOGLE有点像设计题的题

问一道GOOGLE有点像设计题的题# JobHunting - 待字闺中

P*d2014-01-03 08:01

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*c2014-01-03 08:01

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*d2014-01-03 08:01

3 楼

我其实和你一个意思。。。觉得原帖里所谓的面试官提示其实是错的

【在 A*********c 的大作中提到】

: 如果要找degree 2的所有朋友，怎么beat O(n^2)?
: 我有俩朋友，一个伊朗的一个北朝鲜的，这俩互相不认识。每人又认识俩，这四个
: dgree 2的人，俩俩不认识。
: 怎么优化？
: 如果给出了某两个人，判定他俩是不是degree 2, 看friend list交集就行了。
:
: BFS

A*c2014-01-03 08:01

4 楼

嗯，理解。我其实也是自问自答，呵呵。

【在 P****d 的大作中提到】

: 我其实和你一个意思。。。觉得原帖里所谓的面试官提示其实是错的