第二次groupon面筋。。。 - 未名空间MITBBS历史存档

y*e2013-03-07 08:03

1 楼

早上迷迷糊糊的被闹钟吵起来，极不情愿的翻了个身，LD已经起床，洗手间里传出哗啦啦的洗脸声。好希望能继续酣然入眠，可是知道我一定要起床了，恍惚间好像梦见研究生同学，好像我和她在冬天一早起去食堂打饭什么的，心里真是感觉寒冷哪，冬日清晨，牙齿都要打架！
还是挣扎着起来，走到厨房，今天是LD travel需要一大早出发的日子，昨晚我已经打定主意今天一早起来给他做个简单的早餐。洗蕃茄的时候，LD走到厨房，没料到我起来了，很有些吃惊，像小猫一般走到我身后轻轻抱住我，像个小孩子一样的撒娇，嘴巴喃喃低语：“好感动，老婆特地起来做早饭……” 一瞬间心里满满的充满了柔情，虽然还是困的很难受。好久没有和LD一起很早起床了。需要早起的日子一般都是LD独自起来，等他出去快回来的时候我再起床做好饭菜。今天早上的时间比较有限，他需要收拾洗刷、叫taxi，坐轻轨，再去机场……肯定不会有时间做饭的，以往这种情况都是随便吃点点心的，可是谁不想吃一顿热气腾腾的早饭呢？
前些天就为他搭配好了蓝色和灰色两套衬衣领带和毛衫，昨天又把领带结好活扣，可以直接拉上拉下那种。Show给LD看的时候，他非常reli

m*12013-03-07 08:03

2 楼

1. 有一百台machine，专门用来send messages, 如果有某个machine已经发了某个
message（比如A），那其他machine就不必再发了，以免有duplicate，如何避免重复发
送message，告诉对方你的设计和方法。
2. 很简单的编程题，找到树的depth
3. 如何用java implement一个cache，open question，告诉他你的所有想法，我一开
始说cache有个maximum size，超过了之后便使用First come first out，后来在他的
提醒下，觉得这样不好，还是应该用LRU，用hashtable来做。

y*e2013-03-07 08:03

3 楼

赞，还是有老婆好啊

出哗啦啦的洗脸声。好希望能继续酣然入眠，可是知道我一定要起床了，恍惚间好像梦
见研究生同学，好像我和她在冬天一早起去食堂打饭什么的，心里真是感觉寒冷哪，冬
日清晨，牙齿都要打架！
已经打定主意今天一早起来给他做个简单的早餐。洗蕃茄的时候，LD走到厨房，没料到
我起来了，很有些吃惊，像小猫一般走到我身后轻轻抱住我，像个小孩子一样的撒娇，
嘴巴喃喃低语：“好感动
毛衫，昨天又把领带结好活扣，可以直接拉上拉下那种。Show给LD看的时候，他非常
relieved：结领带难哪！有一次他和老板meeting回来笑的不成：“老板说他也不会结
领带，他让一个朋友给结好活扣，然后自己就拉上拉下就
要忙在坐车坐飞机上，可能会来不及吃饭，昨天烤了一些桃酥，说是桃酥，其实家里没
有baking powder，所以样子不很像的，不过吃起来还好，也是酥酥的。
于是纯手工，时间精力花费很多，可是祖母总是会不辞辛苦的亲力亲为。当时不能全部
体会老人家这一举动包含的叮咛嘱托，给LD准备cookie时不禁又深深的被触动:岁月传
承的不仅是一个类似的行

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

: 早上迷迷糊糊的被闹钟吵起来，极不情愿的翻了个身，LD已经起床，洗手间里传出哗啦啦的洗脸声。好希望能继续酣然入眠，可是知道我一定要起床了，恍惚间好像梦见研究生同学，好像我和她在冬天一早起去食堂打饭什么的，心里真是感觉寒冷哪，冬日清晨，牙齿都要打架！
: 还是挣扎着起来，走到厨房，今天是LD travel需要一大早出发的日子，昨晚我已经打定主意今天一早起来给他做个简单的早餐。洗蕃茄的时候，LD走到厨房，没料到我起来了，很有些吃惊，像小猫一般走到我身后轻轻抱住我，像个小孩子一样的撒娇，嘴巴喃喃低语：“好感动，老婆特地起来做早饭……” 一瞬间心里满满的充满了柔情，虽然还是困的很难受。好久没有和LD一起很早起床了。需要早起的日子一般都是LD独自起来，等他出去快回来的时候我再起床做好饭菜。今天早上的时间比较有限，他需要收拾洗刷、叫taxi，坐轻轨，再去机场……肯定不会有时间做饭的，以往这种情况都是随便吃点点心的，可是谁不想吃一顿热气腾腾的早饭呢？
: 前些天就为他搭配好了蓝色和灰色两套衬衣领带和毛衫，昨天又把领带结好活扣，可以直接拉上拉下那种。Show给LD看的时候，他非常reli

m*P2013-03-07 08:03

4 楼

第一题啥想法

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

: 1. 有一百台machine，专门用来send messages, 如果有某个machine已经发了某个
: message（比如A），那其他machine就不必再发了，以免有duplicate，如何避免重复发
: 送message，告诉对方你的设计和方法。
: 2. 很简单的编程题，找到树的depth
: 3. 如何用java implement一个cache，open question，告诉他你的所有想法，我一开
: 始说cache有个maximum size，超过了之后便使用First come first out，后来在他的
: 提醒下，觉得这样不好，还是应该用LRU，用hashtable来做。

m*s2013-03-07 08:03

5 楼

赞温馨

y*g2013-03-07 08:03

6 楼

how about every machine stores the messages it has sent and does a graph
traversal before sending messages

m*12013-03-07 08:03

7 楼

you don't need to. 我告诉他我所有想法，一开始我说，一个machine发消息的同时也
发给其他machine一个消息说我已经发了，你们不用发了。面试官说，那如果两个
machine同时发呢？然后我说，那这样，我想到两种方法，一种是发消息的时候不是直
接发出去，而是先发给一个buffer，由buffer来决定要发的东西，如果有duplicate的
消息，自然就不会重复发。另外一个，我说是不是可以把从数据库取出消息的这个操作
设置成synchronize的，然后在数据库里设立一个flag，一开始是true，当一个消息已
经取出了，flag就变成false, 当其他machine试图取消息的时候，一看到是false，自
然就不取了。对方说用buffer这种方法workable，但是他问要是取出消息之后那个
machine crash了怎么办，我说要有task take over 机制，然后他要我解释了一下。。
这是我的思路，求大神指教！

p*22013-03-07 08:03

8 楼

能不能用两个queue，一个待处理的，一个正在处理的。发送完毕从正在处理的里边删
除。如果一段时间没有删除，则从新放回待处理的queue，认为发送失败了。

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

: you don't need to. 我告诉他我所有想法，一开始我说，一个machine发消息的同时也
: 发给其他machine一个消息说我已经发了，你们不用发了。面试官说，那如果两个
: machine同时发呢？然后我说，那这样，我想到两种方法，一种是发消息的时候不是直
: 接发出去，而是先发给一个buffer，由buffer来决定要发的东西，如果有duplicate的
: 消息，自然就不会重复发。另外一个，我说是不是可以把从数据库取出消息的这个操作
: 设置成synchronize的，然后在数据库里设立一个flag，一开始是true，当一个消息已
: 经取出了，flag就变成false, 当其他machine试图取消息的时候，一看到是false，自
: 然就不取了。对方说用buffer这种方法workable，但是他问要是取出消息之后那个
: machine crash了怎么办，我说要有task take over 机制，然后他要我解释了一下。。
: 这是我的思路，求大神指教！

c*l2013-03-07 08:03

9 楼

第一题是个trick question
在distributed systems环境里面，failure is norm；两台机器同时发一条消息的可能
性绝对是存在的。所以你要做的就是保证server端接受处理message的operator是
idempotent的
也就是第一次operator操作和第二次operator出来的结果是一样，side effect也是一
样（如果有）
有些operator是naturally idempotent的，比如set function，或者read function；
有些不是，比如charge信用卡 - 同一个transaction charge客户两次绝对是个噩梦
怎么解决non naturally idempotent呢？
1. message have to have a unique ID
2. server code has to explicitly record the already processed messages; you
can use traditional DB or distributed key-value store (DynamoDB, Cassandra)
to do it

c*r2013-03-07 08:03

10 楼

use TOKEN.
Pass the token around, only the machine has the token can send message.

p*22013-03-07 08:03

11 楼

还是并行吗？

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

: use TOKEN.
: Pass the token around, only the machine has the token can send message.

c*r2013-03-07 08:03

12 楼

题目的要求就是不要并行发送某种ｍｅｓｓａｇｅ．
Token 只是对某种ｍｅｓｓａｇｅ
对其他活动没限制。
Token是 Distributed system 里Group communication的一种犯(X)法

x*02013-03-07 08:03

13 楼

mark

o*d2013-03-07 08:03

14 楼

我觉得若要保证没有重复
设计中都必须得有一个centralized的结构来处理（比如你提到的buffer以及
synchronize）
否则没法办到

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

: you don't need to. 我告诉他我所有想法，一开始我说，一个machine发消息的同时也
: 发给其他machine一个消息说我已经发了，你们不用发了。面试官说，那如果两个
: machine同时发呢？然后我说，那这样，我想到两种方法，一种是发消息的时候不是直
: 接发出去，而是先发给一个buffer，由buffer来决定要发的东西，如果有duplicate的
: 消息，自然就不会重复发。另外一个，我说是不是可以把从数据库取出消息的这个操作
: 设置成synchronize的，然后在数据库里设立一个flag，一开始是true，当一个消息已
: 经取出了，flag就变成false, 当其他machine试图取消息的时候，一看到是false，自
: 然就不取了。对方说用buffer这种方法workable，但是他问要是取出消息之后那个
: machine crash了怎么办，我说要有task take over 机制，然后他要我解释了一下。。
: 这是我的思路，求大神指教！

j*y2013-03-07 08:03

15 楼

你这个是 hash 的idea吧，用 hash value来确定哪台机器发送 message
感觉需要一个 master server 来负责决定哪台机器

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

: use TOKEN.
: Pass the token around, only the machine has the token can send message.

j*e2013-03-07 08:03

16 楼

还有愿意去他家啊？他家ceo都挂了。。。

m*12013-03-07 08:03

17 楼

嗯，后来我也提到了增加个master node

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

: 你这个是 hash 的idea吧，用 hash value来确定哪台机器发送 message
: 感觉需要一个 master server 来负责决定哪台机器

m*12013-03-07 08:03

18 楼

1. 有一百台machine，专门用来send messages, 如果有某个machine已经发了某个
message（比如A），那其他machine就不必再发了，以免有duplicate，如何避免重复发
送message，告诉对方你的设计和方法。
2. 很简单的编程题，找到树的depth
3. 如何用java implement一个cache，open question，告诉他你的所有想法，我一开
始说cache有个maximum size，超过了之后便使用First come first out，后来在他的
提醒下，觉得这样不好，还是应该用LRU，用hashtable来做。

b*12013-03-07 08:03

19 楼

挖一个坟
在想第一个咋做

c*f2013-03-07 08:03

20 楼

第一题不会是paxos吧...

d*n2013-03-07 08:03

21 楼

1. Before sending a message, the machine need to check the leader that there
is no ongoing sending on same message and the message has not been sent.
if this is the new message, the leader will record this message and issue
a work ticket. If the message failed to be sent, the machine need to notify
server on the failure so another machine can send it. If message sent, the
machine which sent it notify the leader to commit the message.
Another way is to use some existing distributed message queue such as Azure
Service Bus, it has dedupe feature built in.

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

: 1. 有一百台machine，专门用来send messages, 如果有某个machine已经发了某个
: message（比如A），那其他machine就不必再发了，以免有duplicate，如何避免重复发
: 送message，告诉对方你的设计和方法。
: 2. 很简单的编程题，找到树的depth
: 3. 如何用java implement一个cache，open question，告诉他你的所有想法，我一开
: 始说cache有个maximum size，超过了之后便使用First come first out，后来在他的
: 提醒下，觉得这样不好，还是应该用LRU，用hashtable来做。

N*i2013-03-07 08:03

22 楼

感觉第一题可以问下如何unique define a message. 然后用distributed hash table
记录。
不过blooming filter感觉更适合一点。还需要具体讨论要求。
请大牛指教。

z*b2013-03-07 08:03

23 楼

第一题可以用 distrituted lock + distributed hash table.
前者用zookeeper可以搞定，就是你发一个消息，先拿到分布式锁，然后查询hash
table查询是否已经被别人发过了，没过过就发出去，并且写到ｈａｓｈ　ｔａｂｌｅ
．