面试题求高效算法：好友推荐策略

lingyv119

现有一个社交网站，其好友推荐策略为：
       用户A和用户B不是好友，当二人的共同好友数量超过好友推荐阈值m(可配置)时，就向A和B分别推荐为彼此好友。

任务为：
       不使用STL和Mapreduce,
         对设定的m值，给定一组用户及各自好友列表，对这一组用户，反复自动应用上述好友推荐策略后（假设每次推荐都被采纳），求指定用户的最终好友列表。
       要求算法复杂度不高于O（n^2）,用户总数规格不受限；

注：好友关系是双向的，即：如果用户A是用户B的好友，那么用户B一定也是用户A的好友。

简单举例：m =0,  A<->B, A<->C，由于B,C有>m个共同好友A，所以他们自动被推荐为彼此好友：B<->C;
             m>0的情况不再举例；

----------------------------------------------------------------------------------------------------------------------------
一般做法都是：使用二维数组保存互相之间的关系，每次添加关系时遍历新加的这两个用户的所有好友，判断他们是否满足好友关系，
              但这么搞有几次轮询或递归，复杂度是大于O(n^2) 的；
              我试过用户数大于2K时，m=0的情况下，执行时间需要好几分钟。

zhaohongjian000

方法还是这么个方法，但是改用邻接表来实现会好很多（在用户数很大的时候）。

folklore

a <=> b０．．．ｂｎ　．．．．　ｂｍ
bｎ．．．．ｂｍ．．．ｂｋ  <=> c

给ｂｘ设一Flag，从A到ｂｘ，设置
再从ｃ到ｂｘ，查Flag，已设置则ｃｏｕｎｔ＋＋

count即所求

lingyv119

请大家说出自己解法的算法复杂度。。。

shang2010

回复 2# zhaohongjian000


    生产环境一般不用链表，研究的时候数值比较小还能忍受

shang2010

回复 1# lingyv119


    为神马不肯用stl，想把问题搞复杂么？？


是哪家公司的啊？？

zhaohongjian000

shang2010 发表于 2013-03-11 13:05
回复 2# zhaohongjian000

用户之前的好友关系，如果用矩阵表示的话一定是一个稀疏矩阵，你算算当用户数比较大的时候矩阵的消耗？

shang2010

回复 7# zhaohongjian000


    能做这种业务的都是有钱的大户，不差钱，要你绞什么脑汁帮公司省钱哈

多参加一下技术活动认识朋友，散散心也是好的，业界有好办法会在一定的技术场合公开分享的，到时候大家一起copy

zhaohongjian000

zhaohongjian000 发表于 2013-03-11 16:17
用户之前的好友关系，如果用矩阵表示的话一定是一个稀疏矩阵，你算算当用户数比较大的时候矩阵的消耗？

绞尽脑汁？如果邻接表就算的上是“绞尽脑汁”，那我不知道什么问题是简单的，也不知道二维数组有没有绞尽您的脑汁。

zhaohongjian000

shang2010 发表于 2013-03-11 16:53
回复 7# zhaohongjian000

顺带，不用回复我了。我跟楼主说可以用邻接表，你说邻接表不好；我说邻接表的好处，你立马改口说公司有钱，不差这点服务器资源。我也懒得跟你算，因为你不过是在东扯西扯，我不愿跟您扯，您找别人。