Uber-NY onsite (zz)

原帖地址:mitbbs

实习求职终于uber offer,全职求职始于uber rej,what a life。带着唯一的return
offer继续骑驴找马找全职了。

====感想====
0,千万不要看点科技博客,小文章就觉得懂design了,千万不要!常见design题有什
么用,还是被大牛们按在地上摩擦了!所以下面都是我自己总结出来的合适答案,可能
还是会导致你被按在地上摩擦,大家随便看看。

1,Uber NY的Bar很高,尤其是design bar,不想浪费机会的小伙伴还是申Uber SF吧。
刷算法基本对Uber NY没用的,目前Uber NY就没有new grad,第一批new grad的要求必
然是overflow的。
2,几乎纯Design面试,new grad永远的痛,狠狠一巴掌打在自以为design很熟的我脸
上。面我的四个人都干过小公司CTO甚至大公司的技术核心,“你们这些说名词的new
grad,根本不懂design的境界”。

3,真机IDE测试,能bug free就bug free,对方的笑容不代表他认可你先run再debug。
大家都是专业的,笑容什么都不代表。

4,Uber NY的压力明显也比Uber SF要大,大家都很匆匆忙忙,留学生同学们尤其要注
意,要考虑好你适合不适合这里。业绩压力绝对是很大的。

5,面试里很明显的表现不好的地方,就是我说了一些buzzword(kafka,riak,thrift
)之后,并不能很好地解释具体理由和这些技术的核心优势。再来一次一定不乱丢buzz
word了。宁愿说原理和raw model,也不随便丢名字。

6,Hiring Manager和面试官的热情,Uber NY在做的事依然让我很向往,不过只能下次
再来过了。I'll be back!

7,我主要看的复习design的东西:http://www.meetqun.com/thread-767-1-1.html,https://github.com/checkcheckzz/system-design-interview,然后就是每一个技术名词都去看下文档,大概的应用场景,他们主开发者的演讲。接下来的准备估计会看更深了。

====Onsite====
一轮:我暑假的mentor的CMU同学,一开始聊了5分钟家常和我mentor如何逗比很开心。
然,并,卵。

1,常见题-Design spotify,主要在问playlist和shuffle list功能。
>player,playlist,song这些类要怎么搭配比较合适,自由发挥。常见的OOD设计。
>如何让用户之间分享playlist做到最快,让用户之间通信而不是找中央服务器拿,进
程间通信(IPC)和线程间通信(ITC)的常见实现(这里wiki一下,总有几个你熟的名
词)。
>想增加一个shuffle功能,自动随机排序当前list里的歌,这个shuffle怎么写。经典
的knuth洗牌算法,写在白板上。
>用户想shuffle之后回到之前那个版本,如何处理。要把每一次shuffle的结果存起来
。用map或者链表存可以快速存取。用户还想删除当前shuffle的版本的话,写个简单的
双链表删除当前node并且更新位置即可。
>设计一个函数goto(int step),让用户可以返回到某个shuffle次数之后的结果(比如
用户在100万次shuffle后的版本,想回到50万次shuffle的版本,吓得我当时尾巴都掉
了)。我先提到继续用map,用consistency hashing来减少rehash的麻烦。对方说不太
可行,因为复杂度还是太高,但是consistency hashing的方向是对的。
>>然后totally lost,开始丢buzzword,说amazon的dynamo有个ring结构可以进一步压
缩rehashing的工作量或者linkedin的voldemort可以加速大数据的读取和存储,redis
的跳表结构可以压缩空间使用,可以用多级cache或者LRU cache来增加读取速度。全部
都不满意,而且scale越来越大,用户shuffle的次数可以billion级,用户的歌单可以
billion级等等。最后跪求提示,在暗示下意识到可以改造随机数生成器,在洗牌算法
里用我提供的seed进行随机数生成,这样只需要存对应次数的seed。对方表示认可,但
是依然可以优化,时间不够了。丢名词的那几分钟,简直就是被慢慢摩擦的过程。

二轮:一个做前端的小哥,而且是很前端的前端。
1,count and say。
>我直接作死说我做过(其实是太过自信了),让小哥卡了几分钟,好像是他唯一的用
来考非前端的题。然后说改设计吧。也许不应该让他这么没面子,毕竟也是做过CTO的
人啊,也许吧。

2,常见题-facebook friends recommendation。
>首先朋友之间的关系如何存储。常规的sql乃至常规的nosql(比如mongodb)为什么不
适合这个模型(因为关系会互相嵌套,为了处理这些嵌套,开发过程也会很繁琐),如
何解决-使用graph db。因为我在fb做过了解他们的TAO架构,所以稍微说了下,可以把
朋友关系存在边上,这样本身node就只是用户就足够了,提取关系时也可以很轻松的
batch 操作。常见的开源的就是neo4j,可以看看他们的自我介绍和应用场景。也可以
看看fb的engineering blog对于tao的介绍。
>然后如何进行推荐,从最基本的bfs开始说,每个用户为起点,bfs出去到距离2的时候
停下,这个bfs不记录visited,单纯看有有多少用户和当前用户距离为2(就是有一个
共同好友),所以把结果打印出来,重复出现最多的几个用户就是最适合推荐的。
>>follow up,如何提高效率,当用户数大到一定程度时?这里就是典型的MR应用,因
为每次记录都是(用户名,1)这样,把所有的加起来就是典型的reduce步骤。如何提
高反复处理的效率,可以缓存结果,也可以用spark这种基于运算而非基于数据的模型
,把运算传递给数据。说简单了就是传统的Hadoop的优缺点分析。
>>>再follow up,如何对新增的用户进行快速的处理,如何对距离3甚至关系更远的用
户进行分析?这里开始就要谈到collaborative filtering和相关的开源库比如Apache
Mahout了,然后瞎扯了可以用spark streaming来进行流式处理,对方来兴趣了,问我
spark streaming的discretized stream如何适用到这个题目,卒。

3,问完设计,上机写个简单的类似字典搜索。给你代表字典的list和代表输
入的list,把输入字符串里所有出现在字典里的部分大写(对,就是breaking
bad的片尾staff表那样)。
>现在想起来,估计是有陷阱的。我当时太开心,就说好吧我们来写吧。几分钟写完,
还装逼地说我们来写个JUnit test吧。其实这些都是intern面试之后积累的,因为他们
家面试经常让你开自己的ide,写完了自己写个junit test来assert equal。
>test写完,准备run之前,问了一句,你是想我按了run看错误去debug,还是先我肉眼
debug一下再run呢。对方笑了笑说都行。。。现在想起来,我选错答案了。
>然后跑出错,debug,又出错,再debug,两轮快速迭代,增加了2个边界检查,通过。
对方要求我发代码给他看看,开心发完之后就聊天了。现在想起来,我应该主动要求把
代码再优化下的,傻逼兮兮又被按在地上摩擦了吧,自己还不知道。

三轮:一个前Google大牛,上来就把我简历丢开说我们聊聊uber吧。
1,常见常见题-Design Uber。
>https://cnodejs.org/topic/557b9cff16839d2d53936242,建议各位先把这个里面的
那张图看下,它大概描述了早先的Uber模型(最新的应该很不一样了),有个概念就好
,千万不要去硬记那些名词。
>上面模型里的mongodb是错的,千万别说mongodb,可以去搜下为什么初创公司发展之
后都要脱离mongodb。最新最正确的架构看下面这条。
>http://highscalability.com/blog/ … arket-platform.html,这里是关于目前的架构的介绍,基于他们架构师的一个7月份的talk。然并卵,别死记硬背。这个网站本身有很多不同大网站的architecture的分析,都可以看,对名词最好能多深入了解一下应用场景和实现方式。
>先从最基本的用户验证开始问,我看太多科技博客以为上来就问我大架构的东西。结
果一开始迷惑了一阵子直奔dispatching service,傻到回答别人说http是stateless,
tcp是stateful这种奇怪的答案。其实就回答一个POST请求就好了。网络层7栈结构我都
能背了,还在这里犯这种傻,我对不起老师。
>验证之后,如何不需要进行后续验证,这里可以说cache下用户的登录状态,也可以让
用户在post请求里加入生成的密匙,就像OAuth那样。对方似乎对OAuth类的做法不是很
满意,“可以是可以,算一种办法吧”。
>用户要给服务器发送什么信息。物理地址,请求的车型,当地时间。可以JSON也可以
CSV,序列化后加密发送。问我CSV和JSON的优缺点。
>>follow up,问我知道不知道RPC,我说了解一点比如thrift但是基本没用过。然后问
我这里如何应用,我说可以用JSON-RPC类的库来进行序列化以及加密,这样可以提高用
户模块和服务器模块的协作性。对方不是很满意我说不出thrift的一些优缺点或者细节。
>用户点下请求后,服务器如何选择最合适的司机并且通知他们。根据trip time,wait
time还有trip fare以及司机availability(car pool的话,现在在载人的司机也是可
以的)进行判断。司机数据可以按照城市进行Sharding,考虑到有大小城市,可以多个
小城市的shard放在一起,一个大城市的shard使用一个节点。让我聊这样shard的问题
,提到跨城市的trip可能会导致切换shard,这种很低效。
>>follow up,在大量用户请求和大量司机可用的情况下,如何提高效率。这里我又犯
傻,直接说他们目前在用的那个supply demand模型。根本不懂还卖弄就是被按在地上
摩擦。其实这就是个基本的生产者消费者的模型,分布式+message queue谈到了就好了
。他们家的supply demand的主要作用其是和price有关。
>如何保证一个司机不会发给两个不同的用户。这里可以上锁,但是要考虑怎么用锁,
是处理这个请求的thread拿个锁,还是记录在用户相关的缓存数据里,然后要如何锁,
是锁住数据库里的一个object,还是修改一个变量。这里我又傻逼地说了几句就开始说
,哎呀你们家之前用php,因为php的多线程,线程间通讯不够好所以出过一个司机给两
个用户的事,后来不是改成single thread的nodejs,然后用ringpop来轮排操作保证
ITC以及IPC了还有原子性了嘛。其实人家想听到的是更本质的东西,而不是这些花哨的
名词吧。
>data center爆了怎么办。一直有一台config server,爆了就把请求转移到backup
server。backup server可以定期复制数据过来。爆的那段时间里丢失的in flight
data,可以通过在司机和用户手机上预存一部分数据,重新连接后验证两边的数据,如
果不一致就从用户和司机手机上请求最新的数据。这就是uber的做法,他可能意识到了
我复习过,”噢很有意思嘛,我们的做法很类似呢“。
>旅途开始了之后,怎么把用户和司机的状态更新好。这里一台update server和司机通
信,另外一台和用户通信就可以。
>旅途结束后,如何搞定payment。这里要用RPC类的办法去调用其他micro service(比
如business service),然后这个请求发过去之后,如何保证付款一定能成功。这里我
说可以用个简单的message queue,并且带有consume at least once的特性,比如
kafka这样。
>>follow up,kafka是怎么实现的,怎么存的。我只想起来kafka是producer, broker,
consumer分离,使用linux的page cache进行存储和page swap,并且consumer会
guarantee consume once。对方似乎不是很满意。没实际用过kafka,大概不能明白核
心科技吧。

四轮:hiring manager,大大牛,纯culture fit。
1,why uber。常见问题,自己想吧,谈钱也没事,大家都懂。
2,why uber want you。继续常见问题,自己想吧,答实在点,大家都忙。
3,自己做过的最喜欢的项目,自己的三个缺点,三个优点,这都是常见的了。
4,自由提问。我问了why I want to join uber,what can I expect to be in 5
years if at Uber,what can I get here in 2 years。看反应应该不是烂问题,不过
我自己回想是觉得有些装逼了,还好这里人人逼格都非常高。

因为不能编辑,所以如果有什么说错的地方欢迎各位交流。