[WTB] Sandisk Extreme CF Card - 未名空间MITBBS历史存档

[WTB] Sandisk Extreme CF Card# PhotoGear - 摄影器材

n*y2011-09-10 07:09

1 楼

刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
list, user可以发Post, 问如何设计friends可见。
后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user朋
友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法？
不知道怎么答了。。
大家有什么好方法吗？

w*s2011-09-10 07:09

2 楼

物品名称
Sandisk Extreme CF Card
买家联系方式
版上兄弟如果有多的，卖我一个吧。谢谢！prefer 8G PM price
可接受价格
具体要求

t*c2011-09-10 07:09

3 楼

Make the user's friend list as a hash map?

w*s2011-09-10 07:09

4 楼

有人有多的么？谢谢！

j*r2011-09-10 07:09

5 楼

这东西其实要看N有多大。N不大，读可以，N大，靠写。这是典型的Twitter设计题。
多一层就多给你一个选择，全读，全写，写朋友。选啥要靠实测。

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

: 刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
: list, user可以发Post, 问如何设计friends可见。
: 后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user朋
: 友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法？
: 不知道怎么答了。。
: 大家有什么好方法吗？

e*t2011-09-10 07:09

6 楼

有32g

n*y2011-09-10 07:09

7 楼

假设FB的情况，N=200，每个User200个friend. 请问如果是写的话是用HashMap的意思
吗？写到cache里面？
这东西其实要看N有多大。N不大，读可以，N大，靠写。这是典型的Twitter设计题。

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

: 这东西其实要看N有多大。N不大，读可以，N大，靠写。这是典型的Twitter设计题。
: 多一层就多给你一个选择，全读，全写，写朋友。选啥要靠实测。

w*s2011-09-10 07:09

8 楼

给个价吧谢谢

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

: 有32g

n*y2011-09-10 07:09

9 楼

请问HashMap的话是不是要放在cache里面，否则跟N^2次DB read得到friend的friend
list也没多大差别了吧？cache能放下这么大hashMap吗？需要sharding？会不会有
overhead啥的？

【在 t******c 的大作中提到】

: Make the user's friend list as a hash map?

d*n2011-09-10 07:09

10 楼

经典题。
每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
），全部去重按时间线逆序合并起来再把帖子读出来。
帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
朋友都在一个地区的话，其实都是内存操作。

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

: 刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
: list, user可以发Post, 问如何设计friends可见。
: 后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user朋
: 友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法？
: 不知道怎么答了。。
: 大家有什么好方法吗？

n*y2011-09-10 07:09

11 楼

你说的是friends可见吧，怎么实现friends的friends可见，而且O（N）？

【在 d****n 的大作中提到】

: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。

d*n2011-09-10 07:09

12 楼

你写和读的都是朋友圈啊。
你和小A是朋友，小A和小B是朋友。你的发帖就发到小A那里去了，然后小B读到小A的帖
子里面就有你的。
O(N)是近似，就是假设每个人平均每小时发5个贴，然后每个人平均有20个朋友，然后
每次给你看3小时历史，那就是~N*5*20*3，其中N是你的朋友数。

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

: 你说的是friends可见吧，怎么实现friends的friends可见，而且O（N）？

j*r2011-09-10 07:09

13 楼

写就是直接把帖子写到朋友的timeline里。这样对读优化。这么做的原因就是写可以异
步，对延迟要求不高，而读不行。
牺牲存储可以提高Scalability，避免hot row. 反过来N小读不是问题，就可以对存储优
化。

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

: 你说的是friends可见吧，怎么实现friends的friends可见，而且O（N）？

p*a2011-09-10 07:09

14 楼

能不能维护一个 friend of friend list？post 的时候根据 privacy 给这个list上的
人发。
[在 neverlandly (neverlandly) 的大作中提到：]
:刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
:list, user可以发Post, 问如何设计friends可见。
:后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user
朋友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法
？不知道怎么答了。。
:大家有什么好方法吗？

d*n2011-09-10 07:09

15 楼

结论是不可行。
例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，D
删了C，都会造成你刚刚po给D的帖子必须删掉。
如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。

friend
user

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

: 能不能维护一个 friend of friend list？post 的时候根据 privacy 给这个list上的
: 人发。
: [在 neverlandly (neverlandly) 的大作中提到：]
: :刚面FB onsite, 问了一道design题。privacy setting. 说是每个user有一个friend
: :list, user可以发Post, 问如何设计friends可见。
: :后来follow up 问如何设计user朋友的朋友也可见，我说先找user的朋友，再找user
: 朋友的朋友，他说这样就O(N^2)了，问有没有O(N)来设计friend of friend可见的方法
: ？不知道怎么答了。。
: :大家有什么好方法吗？

p*a2011-09-10 07:09

16 楼

每个人按远近程度有不同的 frends list, 假如D也是我的直接朋友，那我的f有 C和D
，然后f of f也有C 和 D。如果我和C删除好友，C从我的f list上消失，D从我的f of
f list上消失；接着C 和 D删除好友，C 从我的 f of f list上消失。最后我的 f
list 上有D，f of f list 空着。这样貌似也可行？
[在 dynkin (化神奇为腐朽) 的大作中提到：]
:结论是不可行。
:例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，
D删了C，都会造成你刚刚po给D的帖子必须删掉。
:如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
:friend
:user

j*r2011-09-10 07:09

17 楼

当然是可以的，timeline这种东西是不recall的。我封了你我不见得想让你知道，我之
前的帖子你可能已经看过了，拿掉反而让你知道我封了你。

，D

【在 d****n 的大作中提到】

: 结论是不可行。
: 例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，D
: 删了C，都会造成你刚刚po给D的帖子必须删掉。
: 如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
:
: friend
: user

d*n2011-09-10 07:09

18 楼

然后面试官就可以问你以下的问题：
我和c已经是好友，然后e加我为好友，你就要把c之前发的帖子全部拷贝一份给e？
我和f原先是好友，然后我删掉了f，你就要在f那里把所有c的帖子删掉，然后在c那里
把所有f的帖子也删掉？
如果我是大v，我有2000个朋友，是不是每次我加减一个好友你都要对我目前所有的好
友之间做一样的操作？
假如我没有加减好友，只是c修改了帖子，是不是对我所有的好友要把之前的旧帖子删
掉或者修改？你觉得数据库怎么设计才可以实现这样随机修改的功能？

D
of

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

: 每个人按远近程度有不同的 frends list, 假如D也是我的直接朋友，那我的f有 C和D
: ，然后f of f也有C 和 D。如果我和C删除好友，C从我的f list上消失，D从我的f of
: f list上消失；接着C 和 D删除好友，C 从我的 f of f list上消失。最后我的 f
: list 上有D，f of f list 空着。这样貌似也可行？
: [在 dynkin (化神奇为腐朽) 的大作中提到：]
: :结论是不可行。
: :例如你和小D是小C的朋友，所以你们俩是FoF。但是如果你删了C，C删了你，C删了D，
: D删了C，都会造成你刚刚po给D的帖子必须删掉。
: :如果考虑到你和D也可以是直接朋友，所以上面当中其中有几个是做不到的。
: :friend

d*n2011-09-10 07:09

19 楼

这个属于没搞清楚需求。
面试官肯定会问你这个问题：你在fb上加了一个朋友，你觉得是不是想马上可以看到他
朋友圈的帖子？你删了一个朋友，你是不是马上不想看到他所有的朋友圈帖子？
无论你回答是或者否，一般接下来面试官都会按照这个需求来让你设计。

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

: 当然是可以的，timeline这种东西是不recall的。我封了你我不见得想让你知道，我之
: 前的帖子你可能已经看过了，拿掉反而让你知道我封了你。
:
: ，D

s*32011-09-10 07:09

20 楼

这个time line 是都存在内存里吗? 因为就算内存crash 似乎也不用重建 history 看
不到就看不到了呗

【在 d****n 的大作中提到】

: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。

s*32011-09-10 07:09

21 楼

大牛能说说这怎么设计吗.....thanks

【在 d****n 的大作中提到】

: 然后面试官就可以问你以下的问题：
: 我和c已经是好友，然后e加我为好友，你就要把c之前发的帖子全部拷贝一份给e？
: 我和f原先是好友，然后我删掉了f，你就要在f那里把所有c的帖子删掉，然后在c那里
: 把所有f的帖子也删掉？
: 如果我是大v，我有2000个朋友，是不是每次我加减一个好友你都要对我目前所有的好
: 友之间做一样的操作？
: 假如我没有加减好友，只是c修改了帖子，是不是对我所有的好友要把之前的旧帖子删
: 掉或者修改？你觉得数据库怎么设计才可以实现这样随机修改的功能？
:
: D

j*r2011-09-10 07:09

22 楼

timeline都是做成immutable, 这才是scalability的关键。朋友圈帖子在前，删朋友在
后，完全没有收回的必要。收回反而显得不自然。微信你要recall,也就给你很短时间。

【在 d****n 的大作中提到】

: 这个属于没搞清楚需求。
: 面试官肯定会问你这个问题：你在fb上加了一个朋友，你觉得是不是想马上可以看到他
: 朋友圈的帖子？你删了一个朋友，你是不是马上不想看到他所有的朋友圈帖子？
: 无论你回答是或者否，一般接下来面试官都会按照这个需求来让你设计。

d*n2011-09-10 07:09

23 楼

前面有。

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

: 大牛能说说这怎么设计吗.....thanks

p*a2011-09-10 07:09

24 楼

谢谢指点！有一点不太明白的是为什么要在朋友（或者朋友的朋友）的timeline中主动
删之前的post，是不是跟pull/push方式的选择有关？假定我们使用pull模式，用户登
录或者刷新后，根据自己的friend list 和 f of f list 去pull有权限的posts；此后
若任何朋友关系变动，只更新这两个lists；直到下次再登陆或者刷新的时候，根据改
动后的lists去pull。大v的问题是不是可以特殊处理：对大v不考虑 f of f 关系？

【在 d****n 的大作中提到】

: 然后面试官就可以问你以下的问题：
: 我和c已经是好友，然后e加我为好友，你就要把c之前发的帖子全部拷贝一份给e？
: 我和f原先是好友，然后我删掉了f，你就要在f那里把所有c的帖子删掉，然后在c那里
: 把所有f的帖子也删掉？
: 如果我是大v，我有2000个朋友，是不是每次我加减一个好友你都要对我目前所有的好
: 友之间做一样的操作？
: 假如我没有加减好友，只是c修改了帖子，是不是对我所有的好友要把之前的旧帖子删
: 掉或者修改？你觉得数据库怎么设计才可以实现这样随机修改的功能？
:
: D

w*z2011-09-10 07:09

25 楼

fanout 一般都是在写的时候做的。 immutable 确实是关键。如果能把 post 做到能改
的就太牛了。

timeline都是做成immutable, 这才是scalability的关键。朋友圈帖子在前，删朋
友在
间。

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

: timeline都是做成immutable, 这才是scalability的关键。朋友圈帖子在前，删朋友在
: 后，完全没有收回的必要。收回反而显得不自然。微信你要recall,也就给你很短时间。

F*02011-09-10 07:09

26 楼

上路了已经

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

: 谢谢指点！有一点不太明白的是为什么要在朋友（或者朋友的朋友）的timeline中主动
: 删之前的post，是不是跟pull/push方式的选择有关？假定我们使用pull模式，用户登
: 录或者刷新后，根据自己的friend list 和 f of f list 去pull有权限的posts；此后
: 若任何朋友关系变动，只更新这两个lists；直到下次再登陆或者刷新的时候，根据改
: 动后的lists去pull。大v的问题是不是可以特殊处理：对大v不考虑 f of f 关系？

a*o2011-09-10 07:09

27 楼

大牛，我想了一天，终于明白你的解释了。
这个应该算O(N)的算法。

【在 d****n 的大作中提到】

: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。

n*y2011-09-10 07:09

28 楼

大牛你好，我今天跟FB一专门搞privacy的美国大牛又谈到了这个问题，把post时候写
到朋友timeline这个思路跟他说了一遍，想不到他是这样回复的：
This can be done simpler, without any extra writes.
A hint: You are thinking about the problem as "How to check if C is a friend
of friends of A". But it is possible to rephrase the question in an other
way which will make the problem much simpler to solve.
竟然还有更好的办法，any idea？

【在 d****n 的大作中提到】

: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。

m*32011-09-10 07:09

29 楼

mark!!!

a*i2011-09-10 07:09

30 楼

这个意思是A写的时候写到朋友B那儿
然后B的朋友C从B那儿读？
然后复杂度，写是A的朋友个数；读是C的朋友个数？

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

: 大牛，我想了一天，终于明白你的解释了。
: 这个应该算O(N)的算法。

s*p2011-09-10 07:09

31 楼

我知道我来的很晚了，但是我还是有个疑惑想问问，不知道你看不看得到。
就是读帖子的时候从朋友那里度，写的时候也全部写到朋友那里，
那么这样就有个问题就是你自己的朋友的post你怎么读到呢？
比如你和A是好友， A发一个帖子到你的 timeline去了，但是你看帖的时候只会从你
的朋友的timeline里面去找，这样是找不到A的帖子的啊？除了这一个疑惑，我觉得
您的思路很好的解决了friends of friends的问题，很棒！

【在 d****n 的大作中提到】

: 经典题。
: 每个人有一个帖子的timeline，里面只包含朋友的发帖的signature。
: 发帖子的时候，你直接写帖子的signature到所有朋友的timeline里面。
: 看帖子的时候，就是把所有朋友的帖子signature翻一遍（里面也包含了自己发的帖子
: ），全部去重按时间线逆序合并起来再把帖子读出来。
: 帖子本身存在按时间分区的数据库里面，而且只用在每个数据中心留一份。假设你所有
: 朋友都在一个地区的话，其实都是内存操作。

s*k2011-09-10 07:09

32 楼

所有人的post都进一个大immutable hash table，key 是user id， value是内容，你
每次读只需要本地搞定friend，FoF或者其他隐私，算出来一个读user的list，然后去
table把内容都读出来
scalability再扩展慢慢来，

friend

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

: 大牛你好，我今天跟FB一专门搞privacy的美国大牛又谈到了这个问题，把post时候写
: 到朋友timeline这个思路跟他说了一遍，想不到他是这样回复的：
: This can be done simpler, without any extra writes.
: A hint: You are thinking about the problem as "How to check if C is a friend
: of friends of A". But it is possible to rephrase the question in an other
: way which will make the problem much simpler to solve.
: 竟然还有更好的办法，any idea？

f*n2011-09-10 07:09

33 楼

难道就是某章的pull push那个办法么？

f*n2011-09-10 07:09

34 楼

终于看到个聊正经事情的帖子了

d*v2011-09-10 07:09

35 楼

mark一下