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

koolcoy

我的算法:
扫描输入, 并且对于任意一个用户x, 计算下面两个集合:
1. 用户x的好友的id集合
2. 把x加为好友的id集合.
有了上面这两个集合, 对于任意要判断y是否是x的二维好友就简单了:
如果: (x的好友的id集合) 交 (把y加为好友的id集合) != 空集, 则y是x的二维好友.

注意: 因为上面算法的特点, 我们可以把每个用户的那两个集合保存到磁盘或数据库, 以提高效率, 这样即使内存很紧的计算机也不会很慢.

[ 本帖最后由 koolcoy 于 2007-7-5 20:52 编辑 ]

koolcoy

原帖由 Edengundam 于 2007-7-5 21:12 发表



bingo

和我想的一样

帮你把分析部分加上:
存储空间开销: 平均每个用户的父好友(别人添加你的用户)为50, 平均每个用户的子好友(你添加其他用户)为50.
10,000,000 * 100 * 4 = 4GB

因为每 ...

赞那个特殊情况的搜索优化

koolcoy

原帖由 福瑞哈哥 于 2007-7-5 21:24 发表


做反向索引，取A的好友集合，再取B的反向好友集合，然后比较两个集合。
我来说具体一点吧，两个有序集合N的比较时间不需要2*N，因为只需要比较两端是否重合就可以了。
但是如果要找出具体路径这种方法就不 ...

怎么能够只比较两端就可以了呢?

koolcoy

原帖由 福瑞哈哥 于 2007-7-5 21:32 发表


如果只是要找他们是否有关系，只比较两端就可以了。

不行吧, 例如两个数组(1, 3, 5), (2, 3, 6), 只比较两端行吗?

koolcoy

原帖由 Edengundam 于 2007-7-5 21:37 发表



嘿嘿, 我那个同学今年又要参加baidu的算法大赛了, 上次就是来北京总部的...他特别牛.....一直搞算法的

给了你个鲜花, 哈哈...

我不太喜欢算法大赛, 感觉很无聊. 并且只有很少的公司会自己做算法. 实际的软件开发对算法需求都不大, 只要程序员心里对算法, 时间复杂度, 空间复杂度有个大概的数就行了.

koolcoy

原帖由 福瑞哈哥 于 2007-7-5 21:46 发表


建立反向连接也是一种方法，其关键是对两个集合的比较算法。希望能从你那儿学习到更详细的方法。

比较集合就两种吧, 复杂度分别为O(m+n)和O(m*ln(n)), 先估算一下哪种快, 然后就用那种方法.