今天真是艳阳天 - 未名空间MITBBS历史存档

今天真是艳阳天# Stock

A*o2010-03-08 08:03

1 楼

来自版上面经,请大牛指点,谢谢了!
4: 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)

5: 设计题: a restful server with 4GB,
given a request such as: http://seq=4?len=60?xxxxdata
the system will store the binary data with that sequence number.
given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.

m*y2010-03-08 08:03

2 楼

赚翻了

l*12010-03-08 08:03

3 楼

at
communication)
Do you mean store or retrieve, it is quite different

【在 A*****o 的大作中提到】

: 来自版上面经,请大牛指点,谢谢了!
: 4: 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)
:
: 5: 设计题: a restful server with 4GB,
: given a request such as: http://seq=4?len=60?xxxxdata
: the system will store the binary data with that sequence number.
: given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.

A*o2010-03-08 08:03

4 楼

RE ...

p*22010-03-08 08:03

5 楼

感觉第一题没什么太大chanllenge呀？查双方friends的合集不久行了吗？这个应该很
快快呀。
第二题是放内存里吗？4G内存还是disk？

y*u2010-03-08 08:03

6 楼

那是2nd degree，不是3rd degree阿

【在 p*****2 的大作中提到】

: 感觉第一题没什么太大chanllenge呀？查双方friends的合集不久行了吗？这个应该很
: 快快呀。
: 第二题是放内存里吗？4G内存还是disk？

A*o2010-03-08 08:03

7 楼

RE一下..

y*x2010-03-08 08:03

8 楼

第一题被L问过,应该是求A和B是否3度好友。
当时说的是：
1. 获得A的好友列表FLa,获得B的好友列表FLb
2. 对FLa中的每个好友Fi，求Fi是否和B是二度好友(就是获得Fi的好友列表FLi,然后和
FLb求交）
如果图很大，最基本的扩展方法是按userid做sharding，然后可以用mergeserver做并
发的求交，或者直接把B的好友列表发送到Fi所在机器上做本地求交后，汇总。
第二题没看明白。。。maxLen是data的大小？还是最多返回100条结果？

at
communication)

【在 A*****o 的大作中提到】

: 来自版上面经,请大牛指点,谢谢了!
: 4: 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)
:
: 5: 设计题: a restful server with 4GB,
: given a request such as: http://seq=4?len=60?xxxxdata
: the system will store the binary data with that sequence number.
: given a request: http://startseq=3?maxLen=100, the system returns all data objects with sequence >= 3 with total data length less equal than 100.

f*k2010-03-08 08:03

9 楼

第一题是不是这么几点
1 userid做sharding
2 取userid的friendslist可以并发
3 递归解决，判断A和B是否是N度好友，相当于判断A的好友和B的好友是否是(N-2)度好友

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

: 第一题被L问过,应该是求A和B是否3度好友。
: 当时说的是：
: 1. 获得A的好友列表FLa,获得B的好友列表FLb
: 2. 对FLa中的每个好友Fi，求Fi是否和B是二度好友(就是获得Fi的好友列表FLi,然后和
: FLb求交）
: 如果图很大，最基本的扩展方法是按userid做sharding，然后可以用mergeserver做并
: 发的求交，或者直接把B的好友列表发送到Fi所在机器上做本地求交后，汇总。
: 第二题没看明白。。。maxLen是data的大小？还是最多返回100条结果？
:
: at

f*k2010-03-08 08:03

10 楼

Q1，有一个问题是，好友数量有没有上限，如果没有上限，当A或B的好友特别多，比如
100W个，这个就要做太多次查找
有好办法解决这个问题吗？

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

: 第一题被L问过,应该是求A和B是否3度好友。
: 当时说的是：
: 1. 获得A的好友列表FLa,获得B的好友列表FLb
: 2. 对FLa中的每个好友Fi，求Fi是否和B是二度好友(就是获得Fi的好友列表FLi,然后和
: FLb求交）
: 如果图很大，最基本的扩展方法是按userid做sharding，然后可以用mergeserver做并
: 发的求交，或者直接把B的好友列表发送到Fi所在机器上做本地求交后，汇总。
: 第二题没看明白。。。maxLen是data的大小？还是最多返回100条结果？
:
: at

y*x2010-03-08 08:03

11 楼

如果两人都有100W好友，如果纯实时计算挺难优化的。
可以做点离线计算把结果准备好？这种有几十万好友的人应该不多，可以把他们之间的
关系（是否是2度，3度等）计算好，定期更新。

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

: Q1，有一个问题是，好友数量有没有上限，如果没有上限，当A或B的好友特别多，比如
: 100W个，这个就要做太多次查找
: 有好办法解决这个问题吗？

n*n2010-03-08 08:03

12 楼

batch view和incremental/delta view merge一下, 就是realtime了。

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

: 如果两人都有100W好友，如果纯实时计算挺难优化的。
: 可以做点离线计算把结果准备好？这种有几十万好友的人应该不多，可以把他们之间的
: 关系（是否是2度，3度等）计算好，定期更新。

p*32010-03-08 08:03

13 楼

http://www.linkedin.com/profile/view?id=251749025&authType=NAME
这样的人根本不给计算的吧

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

: 如果两人都有100W好友，如果纯实时计算挺难优化的。
: 可以做点离线计算把结果准备好？这种有几十万好友的人应该不多，可以把他们之间的
: 关系（是否是2度，3度等）计算好，定期更新。