一般社交网站的"friend"是怎么存储的呢?# JobHunting - 待字闺中
j*y
1 楼
比如
A 有 friend B , C
B 有 friend A, D
C 有 friend A E
D 有 friend B.
E 有 freind C
friend 是相互的, A 是 B的friend那么B 一定也是 A的 friend
首先每个 用户有一个 唯一的 ID
给每个用户创建一个 friend list,friend list 里面存储的就是 ID, 就变成了 graph
的 adjacency-list 的表示, 每个 list可以通过 用户 id排序,那么找两个人的共同
朋友的话,线性搜索就可衣做到。 不知道有没有更好的方法存储。
linkedin 里面的 1st connection 容易实现, 它的 2nd connection, 3rd
connection,
这个是怎么做到的呢。
比如 A 加了 B, 那么 B 的 friend list 里面所有不是 A的friend的话, 就加到 A 的
2nd connection list里面, 但是感觉这么做会有冲突,比如一个人这么看是 A 的
2nd
connection, 那么看会是 A 的 3rd connection, 怎么 resolve.
不是面试题目,只是想想, 呵呵 :)
A 有 friend B , C
B 有 friend A, D
C 有 friend A E
D 有 friend B.
E 有 freind C
friend 是相互的, A 是 B的friend那么B 一定也是 A的 friend
首先每个 用户有一个 唯一的 ID
给每个用户创建一个 friend list,friend list 里面存储的就是 ID, 就变成了 graph
的 adjacency-list 的表示, 每个 list可以通过 用户 id排序,那么找两个人的共同
朋友的话,线性搜索就可衣做到。 不知道有没有更好的方法存储。
linkedin 里面的 1st connection 容易实现, 它的 2nd connection, 3rd
connection,
这个是怎么做到的呢。
比如 A 加了 B, 那么 B 的 friend list 里面所有不是 A的friend的话, 就加到 A 的
2nd connection list里面, 但是感觉这么做会有冲突,比如一个人这么看是 A 的
2nd
connection, 那么看会是 A 的 3rd connection, 怎么 resolve.
不是面试题目,只是想想, 呵呵 :)