j*****y
发帖数: 1071 | 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.
不是面试题目，只是想想, 呵呵 :) |
l*****a
发帖数: 14598 | 2 多级不就是图吗？或者多叉树
你说的那个情况PM定义需求，developer实现。
怎么解决都可以
graph
【在 j*****y 的大作中提到】
: 比如
: 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排序，那么找两个人的共同
|
j*****y
发帖数: 1071 | 3 那给定一个 A, B, 如何判断他们中间隔了几个人呢？
不会每次要算一次 shortest path 吧？
那样太慢了。
【在 l*****a 的大作中提到】
: 多级不就是图吗？或者多叉树
: 你说的那个情况PM定义需求，developer实现。
: 怎么解决都可以
:
: graph
|
l*****a
发帖数: 14598 | 4 你是FB的PM？
听说他们在搞graph search
你的问题很像他们的需求啊
【在 j*****y 的大作中提到】
: 那给定一个 A, B, 如何判断他们中间隔了几个人呢？
: 不会每次要算一次 shortest path 吧？
: 那样太慢了。
|
f*****e
发帖数: 2992 | 5 数据库问题，Friend-Friend关系就行了。
multiway-join + hadoop可以解决你说的问题。
【在 j*****y 的大作中提到】
: 那给定一个 A, B, 如何判断他们中间隔了几个人呢？
: 不会每次要算一次 shortest path 吧？
: 那样太慢了。
|
j*****y
发帖数: 1071 | 6 一点也不懂 database的咋搞阿 :)
我就想能不能通过基本的 data structure 来 理解这些东西
【在 f*****e 的大作中提到】
: 数据库问题，Friend-Friend关系就行了。
: multiway-join + hadoop可以解决你说的问题。
|
j*****y
发帖数: 1071 | 7 呵呵，看来这个 idea还是有点意思，是吧 :)
【在 l*****a 的大作中提到】
: 你是FB的PM？
: 听说他们在搞graph search
: 你的问题很像他们的需求啊
|
f**********o
发帖数: 793 | 8 Linkedin 的 degree 应该不是 on demand
算出来的， 而是每天跑一遍整个graph， 结果算好了的。
可以试一下， 加一个人，看看他的朋友的
degree 过多久会更新。 |
w**z
发帖数: 8232 | 9 刚写了个， 放在Cassandra .key 是user ID, column are list of friends.
graph
【在 j*****y 的大作中提到】
: 比如
: 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排序，那么找两个人的共同
|
j*****y
发帖数: 1071 | 10 怎么访问 Cassandra? 多谢.
【在 w**z 的大作中提到】
: 刚写了个， 放在Cassandra .key 是user ID, column are list of friends.
:
: graph
|
w**z
发帖数: 8232 | 11 Jersey, tomcat + Hector.
【在 j*****y 的大作中提到】
: 怎么访问 Cassandra? 多谢.
|
j*****y
发帖数: 1071 | 12 没有 search到，可以给个 link 吗？ 多谢 ：）
【在 w**z 的大作中提到】
: Jersey, tomcat + Hector.
|
h****e
发帖数: 928 | 13 一般这样的问题，最好找现成的开源软件，然后看看他们的design doc，
这样面试时回答就不会离谱。
找到一个现成的，不过没时间看：
http://www.neo4j.org/ |
j*****y
发帖数: 1071 | 14 多谢.
【在 h****e 的大作中提到】
: 一般这样的问题，最好找现成的开源软件，然后看看他们的design doc，
: 这样面试时回答就不会离谱。
: 找到一个现成的，不过没时间看：
: http://www.neo4j.org/
|
