f*********m
发帖数: 726 | 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****e
发帖数: 116 | 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**m
发帖数: 1466 | |
f*****e
发帖数: 2992 | 4 mapreduce + various join operations
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 的问题吧？
|
f*********m
发帖数: 726 | 5 能说详细些吗？谢谢
【在 f*****e 的大作中提到】
: mapreduce + various join operations
:
: communication)
|
f*********m
发帖数: 726 | |
y*******g
发帖数: 6599 | 7 这种设计题都没标准答案
可以看看这个
http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-
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 的问题吧？
|
f*********m
发帖数: 726 | 8 多谢，我好好研究一下。
【在 y*******g 的大作中提到】
: 这种设计题都没标准答案
: 可以看看这个
: http://techportal.inviqa.com/2009/09/07/graphs-in-the-database-
:
: communication)
|
s*w
发帖数: 729 | 9 这个不是标准的 BFS 吗，可以推广到 n-level 从某人出发找另一个人
就是对 large scale 没概念
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 的问题吧？
|
m*****P
发帖数: 1331 | 10 不是bfs吗？
large scale的话就尽量把比较可能相关的放在一起 比如一个城市的 一个国家的
因为他们更可能有联系
【在 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 的问题吧？
|
|
|
f*********m
发帖数: 726 | 11 估计是对preprocessing以后的graph进行bfs
【在 m*****P 的大作中提到】
: 不是bfs吗？
: large scale的话就尽量把比较可能相关的放在一起 比如一个城市的 一个国家的
: 因为他们更可能有联系
|
b*******h
发帖数: 53 | 12 也在想用BFS， data 存放的时候相关的尽量放在一起。 另外BFS期间，每traverse一
层，把Queue进行sort,让存放在相同地方的数据排在一起，这样就减少不同点之间的跳
来跳去。 |
f*********m
发帖数: 726 | 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******s
发帖数: 48 | 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******s
发帖数: 48 | 15 话说，at most two step 是这样a-c-b吧？这不是2rd connection么？ |
f*********m
发帖数: 726 | 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没想到如何提高并行度.
|
