一道百度试题，大家来试试

feiyang21687

考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有500个好友，
好友必须是这个系统中的其它用户。好友关系是单向的，用户B是用户A的好友，但A不一定是B的好友。

用户以ID形式表示，现给出好友列表数据的文本形式如下：
1  3,5,7,67,78,3332
2  567,890
31  1,66
14    567
78  10000
…
每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。


要求：
请设计合适的索引数据结构，来完成以下查询：
给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。
如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

详细说明自己的解题思路，说明自己实现的一些关键点。
并给出实现的伪代码实现建立索引过程和查询过程，并说明空间和时间复杂度。

限制：
用户数量不超过1000万，平均50个好友。

福瑞哈哥

每个用户是排序数组，用户id就是数组索引。
用户好友用排序数组，初始长度50，以后根据情况realloc扩充。
查找就简单了，定位用户A，遍历A的好友，af1,af2,...,afn，
再查找afx的好友看有没有B。完成。
内存也就使用几百M。
内存可能不止这么多，麻烦。

[ 本帖最后由 福瑞哈哥 于 2007-7-5 17:36 编辑 ]

feiyang21687

这样算法的时间复杂度O(n^2)，太慢了。

福瑞哈哥

原帖由 feiyang21687 于 2007-7-5 17:13 发表
这样算法的时间复杂度O(n^2)，太慢了。

如果能放在内存中，如果你能做到比这还快，还干嘛去百度做题啊？
如果不嫌罗嗦，就使用双向指针吧。每个用户把视自己为朋友的用户也列出来。不过我是不会这么做的。

啊，双向指针也并不快。

[ 本帖最后由 福瑞哈哥 于 2007-7-5 17:30 编辑 ]

ivhb

原帖由 feiyang21687 于 2007-7-5 17:13 发表
这样算法的时间复杂度O(n^2)，太慢了。

用qsort+bsearch，怎么得出的那个复杂度？

converse

福瑞的算法,最坏的情况下要把某ID的所有好友的好友都给查一遍的.

福瑞哈哥

原帖由 ivhb 于 2007-7-5 17:24 发表



用qsort+bsearch，怎么得出的那个复杂度？

同意，好友是顺序遍历是N，间接好友查找就不需要N了。
我觉得设计有一点是不能把非重要或者非常用功能当作优化重点。

福瑞哈哥

原帖由 converse 于 2007-7-5 17:27 发表
福瑞的算法,最坏的情况下要把某ID的所有好友的好友都给查一遍的.

没错，不过不是O(N^2)。

jigloo

http://www.wespoke.com/archives/001077.html

spibit

typedef struct _user {   int userid;   // 好友数目   int count;   // 好友列表数组，最后一个为0表示结束。   int *friends; }user_t; // user_t指针的数组，假设数据已经全部读进来了，users数组最后一个为0，表示结束。 user_t *users[]; // 这个函数，获取users数组里面 userid匹配的 user， // 已经排序好的，折中搜索？复杂度ln(n)，实现略。 user_t  * users_get_user(user_t **users, int userid); // 是好友吗？看在不在好友列表里面了， // 已经排序好的，折中搜索？复杂度ln(n)，实现略。 int user_is_friend(user_t * user, int userid); // B是A好友的好友？ int yes = 0; int * friendsA = users_get_user(users, A)->friends; user_t  * friendsAA; while (0 != friendsA) {   friendsAA = users_get_user(users, *friendsA);   if (0 == user_is_friend(friendsAA, B))   {     yes = 1;     break;   }   friendsA ++; }

[ 本帖最后由 spibit 于 2007-7-5 18:07 编辑 ]