avatar
一道linkedin的graph题# JobHunting - 待字闺中
f*m
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 的问题吧?
avatar
k*e
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 的问题吧?

avatar
b*m
3
这个graph是双向的吧?
avatar
f*e
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 的问题吧?

avatar
f*m
5
能说详细些吗?谢谢

【在 f*****e 的大作中提到】
: mapreduce + various join operations
:
: communication)

avatar
f*m
6
自己顶。
avatar
y*g
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 的问题吧?

avatar
s*w
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 的问题吧?

avatar
m*P
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 的问题吧?

avatar
f*m
11
估计是对preprocessing以后的graph进行bfs

【在 m*****P 的大作中提到】
: 不是bfs吗?
: large scale的话就尽量把比较可能相关的放在一起 比如一个城市的 一个国家的
: 因为他们更可能有联系

avatar
b*h
12
也在想用BFS, data 存放的时候相关的尽量放在一起。 另外BFS期间,每traverse一
层,把Queue进行sort,让存放在相同地方的数据排在一起,这样就减少不同点之间的跳
来跳去。
avatar
f*m
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)

avatar
j*s
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没想到如何提高并行度.
avatar
j*s
15
话说,at most two step 是这样a-c-b吧?这不是2rd connection么?
avatar
f*m
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没想到如何提高并行度.

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。