今天不讲LONG BP,讲讲SHORT BP - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

今天不讲LONG BP,讲讲SHORT BP

今天不讲LONG BP,讲讲SHORT BP# Stock

x*u2010-07-01 07:07

1 楼

背景：master，3年，application track
电面：
1) lowest common ancestor; merge intervals
2) find the smallest character that is strictly larger than the search
character; minimal distance between two words
onsite:
1) sum nested list; given a sequence of DNA (ATGC), find the 10-letter
sequence that has the most occurrences
2) technical communication. 介绍一个你最自豪的项目，会穿插问你一些问题
3) maximum points on a line 只做了一个题，开始互相介绍之后，因为对他做的东西
比较感兴趣，我问了他一些问题占用了好些时间。
4) design a web-based hangman game. 两个表情严肃的印度大哥，怎么也逗不笑
5) hosting manager. 互相介绍，问了问背景。剩下时间全在讨论一个新API发布的问
题。这个API所有的接口全变了，存储也是全新的架构并且初始为空（数据在旧API后面
的存储），线上业务会读写数据。问怎么无缝线上发布，出问题怎么回滚，某些API调
用方没时间更新API的情况下怎么关掉旧API的server等等各种细节问题。
面完之后3个工作日就过了HC，不过将近2周之后的上周四才和team manager聊，比面试
还难，一个多小时惨烈的search engine细节问题，现在还在等offer中，求祝福……

c*o2010-07-01 07:07

2 楼

Short BP at $50, cover it today. Compensate for other long stock loss.

y*e2010-07-01 07:07

3 楼

什么叫lower_bound啊？杀码题，竟然从来没听说过

x*u2010-07-01 07:07

4 楼

不好意思，说错了，是upper_bound：
find the smallest character that is strictly larger than the search
character

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

: 什么叫lower_bound啊？杀码题，竟然从来没听说过

y*e2010-07-01 07:07

5 楼

明了，谢lz。祝周一就拿到正式offer！

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

:
: 不好意思，说错了，是upper_bound：
: find the smallest character that is strictly larger than the search
: character

x*u2010-07-01 07:07

6 楼

谢谢！希望如此！

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

: 明了，谢lz。祝周一就拿到正式offer！

e*a2010-07-01 07:07

7 楼

difficult!
did u work on search engine during ur master study?

x*u2010-07-01 07:07

8 楼

没有，但是他们貌似很有经验。先是问我懂不懂search engine，我说知道basic
concept，然后他们就开问了。

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

: difficult!
: did u work on search engine during ur master study?

e*a2010-07-01 07:07

9 楼

it was amazing that u could handle their questions of search engine
that covers lots of knowledge and tech.

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

: 没有，但是他们貌似很有经验。先是问我懂不懂search engine，我说知道basic
: concept，然后他们就开问了。

g*v2010-07-01 07:07

10 楼

祝顺利拿到offer！
能说下电面第二个题么：find the smallest character that is strictly larger
than the search character; minimal distance between two words
不是很明白这个题目。
能说说你怎么答hangman那个设计题的么？
谢谢！

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

: 背景：master，3年，application track
: 电面：
: 1) lowest common ancestor; merge intervals
: 2) find the smallest character that is strictly larger than the search
: character; minimal distance between two words
: onsite:
: 1) sum nested list; given a sequence of DNA (ATGC), find the 10-letter
: sequence that has the most occurrences
: 2) technical communication. 介绍一个你最自豪的项目，会穿插问你一些问题
: 3) maximum points on a line 只做了一个题，开始互相介绍之后，因为对他做的东西

y*e2010-07-01 07:07

11 楼

hangman,hangman, pls lz!!强烈要求说说怎么答的

y*e2010-07-01 07:07

12 楼

这是两个题，用分号隔开的。。。。。

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

: 祝顺利拿到offer！
: 能说下电面第二个题么：find the smallest character that is strictly larger
: than the search character; minimal distance between two words
: 不是很明白这个题目。
: 能说说你怎么答hangman那个设计题的么？
: 谢谢！

x*u2010-07-01 07:07

13 楼

根本不能说是handle，这方面我不懂，比起其他面试很没自信。对面是两个人，期间扯
不清楚还用了collabedit边写边讲，具体对话如下。大家谨慎阅读，很有可能我说了很
多错的东西，他们也没有当场指出。如果懂行的朋友望指正一下。
对方：reverted index怎么partition，怎么scale
我：按term来hash，用consistent hashing来保证加机器之后数据不用全部reshuffle。
对方：consistent hashing怎么工作的
我：blahblah（写了个小例子解释）
对方：你讲讲加了个node之后发生了什么
我：加了机器后，新机器收到了查某个term的请求，就去老机器上拉数据过来再存着..
（被打断）
对方：client怎么会发请求到新机器
我：因为加了机器之后hash ring更新了，有一部分term的请求导到新机器了
对方：怎么更新的
我：可以用ZooKeeper存机器列表，新机器register到zookeeper后，各client那边的
listener就更新列表
对方：新加的机器怎么知道到哪里去找某个term的数据
我：顺着hash ring找前面那台就是原来存的地方。除了来了请求更新数据以外，还可
以搞个额外的job在半夜导数据
对方：你说的是按term来hash，除了这个你还有别的partition方法吗
我：（想了半天没想出来）给term设个id，用这个id来分
对方：不用任何term的信息
我：（沉默。。）是不是可以按client的地址，欧洲的发到欧洲cluster，北美发北美
，但这要求数据duplicate或者完全isolated
对方：这是另外一码事
我：如果跟term无关，那client就不知道该把请求发到哪去，如果随机发到一台，没有
那个term的话，怎么找到数据呢
对方：（沉默）
我：是不是请求发到这边有个master 再路由到term的机器
对方：那不还是按term吗
我：（沉默）我不知道该怎么partition
（我简化了对话内容，只保留大致主题，总之很长时间才说到document id）
对方：可以按document id来
我：噢，这样是可以保证相关的词更容易land到一台机器上吗
对方：为什么？
我：（意识到自己错误）噢我想错了。。那用document id来partition有什么好处？
对方：（沉默）（笑）
我：这应该是你们想问我的吧（笑）
对方：是的，你说说有什么好处
我：我还没明白这怎么work，那这样partition的话，每个搜索请求都要request所有机
器啊
对方：是的。
我：可能这样latency比较好？异步请求所有的机器，这样每个回复的package都比较小
。另外用term来hash的话可能有data skew的问题，有些常用词的doc id特别多。
对方：你提到异步请求，你能讲讲这里怎么请求所有机器吗。
我：（不大明白他想问什么）就是我发了请求不等回复就发下一条请求啊
对方：but how？
我：我之前是用c++的，我们公司有个framework可以blahblah...
对方：你这里是等所有机器回复了再返回结果吗
我：是的，可以设个timeout，超时的就不等了
对方：有办法减小latency吗
我：可以先返回部分结果
对方：怎么做
我：收到每个partition的回复就直接发回去，按request id再合并
太长了，记不清楚了，大致还问了按doc id来partition具体怎么扩容，用term来
partition在network上有什么好处，等等。我没有相关经验，靠一知半解和他们的提示
一路胡诌。活活折腾了一个多小时。

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

: it was amazing that u could handle their questions of search engine
: that covers lots of knowledge and tech.

x*u2010-07-01 07:07

14 楼

不好意思，这是两个题，用分号隔开的。
http://www.careercup.com/question?id=5726366532108288
http://www.careercup.com/question?id=5725709041401856

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

x*u2010-07-01 07:07

15 楼

好的，我大概说说。当时讲的比较散乱，基本是他们问一个方面我答一个方面。
首先我不懂这个游戏，让他们介绍了一下。
然后我确认了一下前台（web端）的基本内容，把几个简单的交互画了一下跟他们确认
要实现的内容：1. 用户登录；2.可以查看历史游戏结果；3. 可以load未完成游戏；4.
可以new game。
再就是问每个game的词从哪来，有多少词可以选。
再就是开始整理前后台交互的api了，我是边讲边想的，就假装自己在做前台页面。
首先页面全静态放CDN，前台向后台ajax请求/get_info，后台校验cookies的session是
否过期，过期则返回需要登陆的错误码，前台弹登陆框（这里他们问我返回什么状态码
，我说200，他们表示质疑，我说不用跳转我们直接根据错误码在原页面显示登陆框也
一样），这个登录态校验所有的请求都会有。如果用户已登陆就返回用户的历史游戏记
录，列了下json格式。
然后实现查看历史游戏结果，这里就不需要后台了，因为登陆之后所有游戏记录都返回
了。
再是load一个游戏，请求/load 输入游戏id，返回游戏status（id，时间，猜过的字母
，当前单词，剩余次数）
或者create一个游戏，请求/create，返回游戏status
再就是玩游戏猜词了，前台请求/guess 发送游戏id，所猜字母，后台返回游戏status
基本就这些，再就说说存储，这个全都可以拿key-value的storage存着，一个是用户的
key，再就是游戏的key，用户key下面存历史游戏，游戏key下面存游戏status；词典也
可以存里面，搞个不一样的前缀加上数字，每次创建游戏时random一下取一个出来。
我现在想到的就这些了，当时讲的也没章法，东一榔头西一棒子。

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

: hangman,hangman, pls lz!!强烈要求说说怎么答的

y*e2010-07-01 07:07

16 楼

谢谢lz的详细回复，我一直不知design怎么交流，看到你的过程感觉心里有点底了。你
对人对事这么认真，想必一定的负责的员工，linkedin很有眼光撒

4.

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

: 好的，我大概说说。当时讲的比较散乱，基本是他们问一个方面我答一个方面。
: 首先我不懂这个游戏，让他们介绍了一下。
: 然后我确认了一下前台（web端）的基本内容，把几个简单的交互画了一下跟他们确认
: 要实现的内容：1. 用户登录；2.可以查看历史游戏结果；3. 可以load未完成游戏；4.
: 可以new game。
: 再就是问每个game的词从哪来，有多少词可以选。
: 再就是开始整理前后台交互的api了，我是边讲边想的，就假装自己在做前台页面。
: 首先页面全静态放CDN，前台向后台ajax请求/get_info，后台校验cookies的session是
: 否过期，过期则返回需要登陆的错误码，前台弹登陆框（这里他们问我返回什么状态码
: ，我说200，他们表示质疑，我说不用跳转我们直接根据错误码在原页面显示登陆框也