一道linkedin的graph题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道linkedin的graph题

一道linkedin的graph题# JobHunting - 待字闺中

f*m2013-03-06 08:03

1 楼

前些时候本版大牛面过的linkedin的题，没什么好思路。贴出来请大家指点。
Given a social graph, find if there is a path between two persons with at
most 2 steps (3rd level connection), how to handle it in distributed way (
large graph stored at a large number of nodes, minimize cross-communication)
不会涉及到graph merge/split 的问题吧？

k*e2013-03-06 08:03

2 楼

等价于一个person的adjacent list 和另外一个person 的adjacent list是否connect？
不知道

communication)

【在 f*********m 的大作中提到】

: 前些时候本版大牛面过的linkedin的题，没什么好思路。贴出来请大家指点。
: Given a social graph, find if there is a path between two persons with at
: most 2 steps (3rd level connection), how to handle it in distributed way (
: large graph stored at a large number of nodes, minimize cross-communication)
: 不会涉及到graph merge/split 的问题吧？

b*m2013-03-06 08:03

3 楼

这个graph是双向的吧？

f*e2013-03-06 08:03

4 楼

mapreduce + various join operations

communication)

【在 f*********m 的大作中提到】

f*m2013-03-06 08:03

5 楼

能说详细些吗？谢谢

【在 f*****e 的大作中提到】

: mapreduce + various join operations
:
: communication)

f*m2013-03-06 08:03

6 楼

自己顶。

y*g2013-03-06 08:03

7 楼

这种设计题都没标准答案
可以看看这个
http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-

communication)

【在 f*********m 的大作中提到】

f*m2013-03-06 08:03

8 楼

多谢，我好好研究一下。

【在 y*******g 的大作中提到】

: 这种设计题都没标准答案
: 可以看看这个
: http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-
:
: communication)

s*w2013-03-06 08:03

9 楼

这个不是标准的 BFS 吗，可以推广到 n-level 从某人出发找另一个人
就是对 large scale 没概念

communication)

【在 f*********m 的大作中提到】

m*P2013-03-06 08:03

10 楼

不是bfs吗？
large scale的话就尽量把比较可能相关的放在一起比如一个城市的一个国家的
因为他们更可能有联系

【在 f*********m 的大作中提到】

f*m2013-03-06 08:03

11 楼

估计是对preprocessing以后的graph进行bfs

【在 m*****P 的大作中提到】

: 不是bfs吗？
: large scale的话就尽量把比较可能相关的放在一起比如一个城市的一个国家的
: 因为他们更可能有联系

b*h2013-03-06 08:03

12 楼

也在想用BFS， data 存放的时候相关的尽量放在一起。另外BFS期间，每traverse一
层，把Queue进行sort,让存放在相同地方的数据排在一起，这样就减少不同点之间的跳
来跳去。

f*m2013-03-06 08:03

13 楼

问题是一台机器上如何存储边界node。能不能把每个边界node都存两个copy，两个相邻
的机器各一个？比如：node_a和node_b是边界node，在两台机器上各有一个copy。
机器1 机器2
node_c---node_a---node_b | node_a---node_b---node_d
|
找node_a的k-level 邻居，可以先在机器1上用bfs,遇到node_b后（可以给node_b一个
标签，说明他在机器2上也有copy），可以继续在机器2上bfs。
不过题目给定只要3-level邻居，会不会有什么更有效的方法？

connect？

【在 k****e 的大作中提到】

: 等价于一个person的adjacent list 和另外一个person 的adjacent list是否connect？
: 不知道
:
: communication)

j*s2013-03-06 08:03

14 楼

map reduce吧
for node and its adj list,
map emit(node,adj+" 1") and emit(adj,node+" 0")
suffix " 1" stands for I have a friend **
suffix " 0" stands for I am the friend of **
reduce output all combination of value with different suffix "0" and "1",
which is I am the friend of **, and I have a friend **.
And it needs to detect that ** and ** is the same person. (Mutual friend)
传统的bfs没想到如何提高并行度.

j*s2013-03-06 08:03

15 楼

话说，at most two step 是这样a-c-b吧？这不是2rd connection么？

f*m2013-03-06 08:03

16 楼

“And it needs to detect that ** (A) and ** (B) is the same person. (Mutual
friend)”--也就是说，如果A and B are not the same person, then A 和B的
distance是2，对吧？

【在 j******s 的大作中提到】

: map reduce吧
: for node and its adj list,
: map emit(node,adj+" 1") and emit(adj,node+" 0")
: suffix " 1" stands for I have a friend **
: suffix " 0" stands for I am the friend of **
: reduce output all combination of value with different suffix "0" and "1",
: which is I am the friend of **, and I have a friend **.
: And it needs to detect that ** and ** is the same person. (Mutual friend)
: 传统的bfs没想到如何提高并行度.