话说违法交规时，条子就在附近，如何处理。 (转载) - 未名空间MITBBS历史存档

话说违法交规时，条子就在附近，如何处理。 (转载)# Joke - 肚皮舞运动

B*12011-04-08 07:04

1 楼

图论比较弱，觉得应该是用图，请大牛们指点：
Suppose there are 2 persons A and B on FB . A should be able to view the
pictures of B only if either A is friend of B or A and B have at least one
common friend . The interviewer discussed it for nearly 30 minutes . The
discussion mainly included following points -
1. How are you going to store the list of friends for a given user ?
2. File system vs DB
3. Given list of friends of 2 users , how are you going to find common
friends ?
4. If you are going to store the friends in DB then how will the table
look like ?
5. How many servers do you need ?
6. How are you going to allocate work to servers ?
7. How many copies of data will you need ?
8. What problems will you face if you are maintaining multiple copies of
data.

l*u2011-04-08 07:04

2 楼

【以下文字转载自 Automobile 讨论区】
发信人: yulian (恋恋风尘), 信区: Automobile
标题: 话说违法交规时，条子就在附近，如何处理。
发信站: BBS 未名空间站 (Thu Apr 7 23:41:41 2011, 美东)
早上恋床，把预留给路上的时间挤占不少。
时间守恒，上班打卡亦不等人，只能从别处寻回失去的时间。
老天还算配合，local一路绿灯，车流也很顺畅。
眼看快到公司，晚节不保，栽在最后一个路口。
距离50米时绿灯，我估摸着能过就踩油门加速，
25米时等变黄了，我在加速和刹车中选择了继续加速。
不想早上交通灯循环周期缩短，绿灯缩水，黄灯也跟着缩水。
等我过线时，红灯亮了已有半秒钟。
冲了个红灯，自己记住，下次小心就算了，反正那个路口也没有电子摄像。
祸总不是单行的，
快过完路口时突然发现对面反方向有一个条子车也在等红灯，
tmd还是左拐线离我倍儿近。
我下意识的向左望了一眼，有种嫌疑人和条子擦肩而过的感觉。
担心如果继续前行，条子会u-turn后打灯追我，
当机立断立马把车换右车道，拐入一家餐馆的隐秘停车位，弃车徒步上班。
步行到马路上来时，真看到条子把车转了个向在那晃悠，只是没有打灯和鸣笛。
疾步15分钟，终于赶到办公室。
tnnd，太久没运动，
没做一会儿大小腿都酸了，报应啊。
下班去取车，没啥事发生。
我承认我常看警匪片，追逐战，没想到现学现用了一回。
想问诸位，这种方式逃离条子追捕有没有后遗症？大家实践过吗？
p.s. 希望大家，认真开车，出入平安。

P*c2011-04-08 07:04

3 楼

G居然也开始考数据库了，以前很少看到数据库相关的问题。这个题目很难啊，如果我
遇到估计也会答的乱七八糟的。

【在 B*******1 的大作中提到】

: 图论比较弱，觉得应该是用图，请大牛们指点：
: Suppose there are 2 persons A and B on FB . A should be able to view the
: pictures of B only if either A is friend of B or A and B have at least one
: common friend . The interviewer discussed it for nearly 30 minutes . The
: discussion mainly included following points -
: 1. How are you going to store the list of friends for a given user ?
: 2. File system vs DB
: 3. Given list of friends of 2 users , how are you going to find common
: friends ?
: 4. If you are going to store the friends in DB then how will the table

k*e2011-04-08 07:04

4 楼

恋恋风尘啊。。。
那天，
清晨，
路又变成了红灯。
忧伤，
开满车厢，
等上班晚场。。。

【在 l****u 的大作中提到】

: 【以下文字转载自 Automobile 讨论区】
: 发信人: yulian (恋恋风尘), 信区: Automobile
: 标题: 话说违法交规时，条子就在附近，如何处理。
: 发信站: BBS 未名空间站 (Thu Apr 7 23:41:41 2011, 美东)
: 早上恋床，把预留给路上的时间挤占不少。
: 时间守恒，上班打卡亦不等人，只能从别处寻回失去的时间。
: 老天还算配合，local一路绿灯，车流也很顺畅。
: 眼看快到公司，晚节不保，栽在最后一个路口。
: 距离50米时绿灯，我估摸着能过就踩油门加速，
: 25米时等变黄了，我在加速和刹车中选择了继续加速。

B*12011-04-08 07:04

5 楼

是阿，我数据库也忘光了。

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

: G居然也开始考数据库了，以前很少看到数据库相关的问题。这个题目很难啊，如果我
: 遇到估计也会答的乱七八糟的。

t*o2011-04-08 07:04

6 楼

你脑子转的真快

r*n2011-04-08 07:04

7 楼

是楼主自己碰到的题吗？
觉得这题挺难，不过也觉得挺好的，覆盖面挺广，希望大牛出来说说

【在 B*******1 的大作中提到】

: 图论比较弱，觉得应该是用图，请大牛们指点：
: Suppose there are 2 persons A and B on FB . A should be able to view the
: pictures of B only if either A is friend of B or A and B have at least one
: common friend . The interviewer discussed it for nearly 30 minutes . The
: discussion mainly included following points -
: 1. How are you going to store the list of friends for a given user ?
: 2. File system vs DB
: 3. Given list of friends of 2 users , how are you going to find common
: friends ?
: 4. If you are going to store the friends in DB then how will the table

c*e2011-04-08 07:04

8 楼

这句很传神啊。。。
我下意识的向左望了一眼，有种嫌疑人和条子擦肩而过的感觉。

【在 l****u 的大作中提到】

: 【以下文字转载自 Automobile 讨论区】
: 发信人: yulian (恋恋风尘), 信区: Automobile
: 标题: 话说违法交规时，条子就在附近，如何处理。
: 发信站: BBS 未名空间站 (Thu Apr 7 23:41:41 2011, 美东)
: 早上恋床，把预留给路上的时间挤占不少。
: 时间守恒，上班打卡亦不等人，只能从别处寻回失去的时间。
: 老天还算配合，local一路绿灯，车流也很顺畅。
: 眼看快到公司，晚节不保，栽在最后一个路口。
: 距离50米时绿灯，我估摸着能过就踩油门加速，
: 25米时等变黄了，我在加速和刹车中选择了继续加速。

q*x2011-04-08 07:04

9 楼

these questions have nothing to do with graph ah.
but good questions.

the
one
The
?
common
table

【在 B*******1 的大作中提到】

: 图论比较弱，觉得应该是用图，请大牛们指点：
: Suppose there are 2 persons A and B on FB . A should be able to view the
: pictures of B only if either A is friend of B or A and B have at least one
: common friend . The interviewer discussed it for nearly 30 minutes . The
: discussion mainly included following points -
: 1. How are you going to store the list of friends for a given user ?
: 2. File system vs DB
: 3. Given list of friends of 2 users , how are you going to find common
: friends ?
: 4. If you are going to store the friends in DB then how will the table

c*e2011-04-08 07:04

10 楼

这没啥，我也做过非常类似的事。。
当时是闯了一个stop sigh. 发现对面是警车。说时迟那时快，
我一个急刹，停在路上。他果然掉个头，老老实实的跟过来。
他问我有事么?我说没有。他让我take care.就88了

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

: 你脑子转的真快

r*n2011-04-08 07:04

11 楼

我随便说说，看是否有大牛出来吧
1. format存成file或者db table,存的内容基本就是user id(unique)的friend关系，
比如file每行 1 2就表示user1和user2是friend
2.file存在io问题，interface上得自己重新建立datastructure来提供常见的function
,同时这也是优势，更灵活，有完全控制权；可以像读triangle mesh一样读进来，然后
建立mesh；db通常有先有工具，只需考虑table schema的设计，有index等手段优化
search等功能；db易于数据同步，备份，建立db cluster, load balance等常见手段
3. 两个数组按照user id升序排列，找相同id,O(m+n)遍历，可以找完
4. tableName:Connection, 两个column friendStart, friendEnd,都用来存放userId,
两个column都是index
select distinct friend from (
select friendEnd from Connection tbl,
(select friendEnd from Connection where friendStart=A) AS directFriend
where tbl.friendStart=directFriend.friendEnd
Union ALL
select friendEnd from Connection where friendStart=A
)
差不多就能把user A的直接好友和1层简洁好友都选出来
5，6：根据userid建立hash (hash key可以考虑user location等),分配到对应的server index上，同时也就是database
server的id,具体多少台server不知道怎么答？而且如何根据user的相似度做cluster,分散数据到各个表也不清楚
7,8: 因为数据量太大，db table肯定得分割，如何数据冗余，做分割就不知道了。必
须得有database denormalization的过程，假如跨server，问题有如何同步数据(一个
transaction进去？)，load balance具体的cluster操作？
觉得有大型sns数据库实际操作的能出来讲讲，给个啥link的也好

【在 B*******1 的大作中提到】

: 图论比较弱，觉得应该是用图，请大牛们指点：
: Suppose there are 2 persons A and B on FB . A should be able to view the
: pictures of B only if either A is friend of B or A and B have at least one
: common friend . The interviewer discussed it for nearly 30 minutes . The
: discussion mainly included following points -
: 1. How are you going to store the list of friends for a given user ?
: 2. File system vs DB
: 3. Given list of friends of 2 users , how are you going to find common
: friends ?
: 4. If you are going to store the friends in DB then how will the table

m*l2011-04-08 07:04

12 楼

你能听懂他说话？

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

: 这没啥，我也做过非常类似的事。。
: 当时是闯了一个stop sigh. 发现对面是警车。说时迟那时快，
: 我一个急刹，停在路上。他果然掉个头，老老实实的跟过来。
: 他问我有事么?我说没有。他让我take care.就88了

P*c2011-04-08 07:04

13 楼

楼主面的什么组啊。这种题目如果不是面google+应该不会这么domain specific吧。

function
userId,

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

: 我随便说说，看是否有大牛出来吧
: 1. format存成file或者db table,存的内容基本就是user id(unique)的friend关系，
: 比如file每行 1 2就表示user1和user2是friend
: 2.file存在io问题，interface上得自己重新建立datastructure来提供常见的function
: ,同时这也是优势，更灵活，有完全控制权；可以像读triangle mesh一样读进来，然后
: 建立mesh；db通常有先有工具，只需考虑table schema的设计，有index等手段优化
: search等功能；db易于数据同步，备份，建立db cluster, load balance等常见手段
: 3. 两个数组按照user id升序排列，找相同id,O(m+n)遍历，可以找完
: 4. tableName:Connection, 两个column friendStart, friendEnd,都用来存放userId,
: 两个column都是index

c*e2011-04-08 07:04

14 楼

很久没和你聊天了，很想你。

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

: 你能听懂他说话？

s*n2011-04-08 07:04

15 楼

这个open问题本来就应该用nonsql来解。做到sql就是歪了。人家也就是顺着问下去了。

function
userId,

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

: 我随便说说，看是否有大牛出来吧
: 1. format存成file或者db table,存的内容基本就是user id(unique)的friend关系，
: 比如file每行 1 2就表示user1和user2是friend
: 2.file存在io问题，interface上得自己重新建立datastructure来提供常见的function
: ,同时这也是优势，更灵活，有完全控制权；可以像读triangle mesh一样读进来，然后
: 建立mesh；db通常有先有工具，只需考虑table schema的设计，有index等手段优化
: search等功能；db易于数据同步，备份，建立db cluster, load balance等常见手段
: 3. 两个数组按照user id升序排列，找相同id,O(m+n)遍历，可以找完
: 4. tableName:Connection, 两个column friendStart, friendEnd,都用来存放userId,
: 两个column都是index

m*l2011-04-08 07:04

16 楼

离婚了么？

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

: 很久没和你聊天了，很想你。

l*i2011-04-08 07:04

17 楼

Why so many FB questions carry the title of google?

l*u2011-04-08 07:04

18 楼

联想到电影镜头

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

: 这句很传神啊。。。
: 我下意识的向左望了一眼，有种嫌疑人和条子擦肩而过的感觉。

s*f2011-04-08 07:04

19 楼

以菜鸟的经验，读完G三篇（GFS，BIGtable，mapreduce)之后，你的回答能从40分提高
到70分。

function
userId,

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

: 我随便说说，看是否有大牛出来吧
: 1. format存成file或者db table,存的内容基本就是user id(unique)的friend关系，
: 比如file每行 1 2就表示user1和user2是friend
: 2.file存在io问题，interface上得自己重新建立datastructure来提供常见的function
: ,同时这也是优势，更灵活，有完全控制权；可以像读triangle mesh一样读进来，然后
: 建立mesh；db通常有先有工具，只需考虑table schema的设计，有index等手段优化
: search等功能；db易于数据同步，备份，建立db cluster, load balance等常见手段
: 3. 两个数组按照user id升序排列，找相同id,O(m+n)遍历，可以找完
: 4. tableName:Connection, 两个column friendStart, friendEnd,都用来存放userId,
: 两个column都是index

c*e2011-04-08 07:04

20 楼

暂时没考虑过。

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

: 离婚了么？

w*o2011-04-08 07:04

21 楼

什么是 GFS?

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

: 以菜鸟的经验，读完G三篇（GFS，BIGtable，mapreduce)之后，你的回答能从40分提高
: 到70分。
:
: function
: userId,

c*e2011-04-08 07:04

22 楼

你呢？和大帅什么时候办喜事？

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

: 离婚了么？

y*u2011-04-08 07:04

23 楼

google file system
因为gfs只有single master node，所以google早就打算重写了

提高

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

: 什么是 GFS?

m*l2011-04-08 07:04

24 楼

要未雨绸缪

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

: 暂时没考虑过。

s*f2011-04-08 07:04

25 楼

重写后是啥样子？有没有paper？

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

: google file system
: 因为gfs只有single master node，所以google早就打算重写了
:
: 提高

c*e2011-04-08 07:04

26 楼

好。我抓紧找。

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

: 要未雨绸缪

g*e2011-04-08 07:04

27 楼

应该是fully distributed system。没有master node，各个机器平权。

m*l2011-04-08 07:04

28 楼

那个谁一直在等你

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

: 好。我抓紧找。

s*f2011-04-08 07:04

29 楼

u can check Amazon dynamo, p2p distributed system, more reliable, but not as
efficient as gfs, i think.

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

: 应该是fully distributed system。没有master node，各个机器平权。

B*e2011-04-08 07:04

30 楼

俺通常都是按GTA的模式，直接用bazooka把警车轰上天，然后HLL的飘然而去。