b*****n
发帖数: 618 | 1 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yahoo去年收购的一家在城里的小公司，所以不一
定有代表性。因为re-org我两个月之后才拿到offer，中间还给我match到其他team几次
，Yahoo比较动荡，个人也不看好。
电面：
和director聊了有两个小时，无coding，问了很多之前project内容和hadoop相关的内
容。
最后讨论了一道design，如何设计distributed key-value store，因为他们主要用
HBase。
Programming Test:
Validate Soduko Solution，从文件读solution，尽量用production标准写程序。
Onsite：
五轮Onsite没有coding，全是问实际问题怎么解决和design。
1. 如何设计一个priorityqueue service，client可以submit job request然后server
按照priority执行
2. 需要一个key-value store with 1M qps，most read，1ms 99% latency，如果用
HBase的话会有什么问题，怎么解决
3. 给很多整数，如何用mapreduce找median，如果是很多float数，可以有一定的误差
，如何找
4. Programming Test的扩展，如果soduku matrix非常之大怎么做
然后还有一大堆针对hadoop的各种情况下怎么optimize的问题
onsite完了之后他们director说very positive，然后就开始re-org两个月。Flurry做
的东西其实挺有意思，mobile analytics platform #1，我感觉他们engineer人很nice
，水准也非常不错，可惜没缘分。
############################################################################
###########
Apple：
练手公司1，Apple可以同时面很多组，每个组有各自的recruiter。我把简历递了之后
陆续有10个组联系我，然后每个组基本上都是onsite之前两轮phone，一开始没经验联
系了4个组后来发现实在体力吃不消，光电面就8轮。最后3个组要onsite，这里我犯了
一个错误，告诉他们我在面其他的组，一旦他们知道你在面其他的组就不跟进了，打死
不回email。所以最终我只onsite了一个组。
电面：
1.给平面一堆点，把所有在同一条直线上的点group在一起，求出所有的group
2.一种encoding的方法，如果一个byte第一个bit是0，比如 00000000，那它自己表示
一个字符，如果一个byte第一个bit是1，比如 10000000，那它和它后面紧跟的byte表
示一个字符，现在给一个byte array，判断最后一个字符是一个byte还是两个byte组成。
3.parse message from byte stream，message format是前4个bytes组成的int值表示
message的长度L，然后后面连续的L个byte是message真正的内容，每个message都是这
样表示，需要一边读byte stream一边parse每个message
4. 两个table做join有哪几种方法，分别有哪些drawback
5. merge two sorted list
6. sqrt(double number, double epsilon)
7. auto completion implementation using trie
8. edit distance
9. Implement blockingqueue
10. how is a hive query transferred to mapreduce jobs
Onsite:
1. given a list of pairs, pair.first 表示parent, pair.second表示child,
reconstruct the tree, return the root node.
2. auto completion - design the service
3. design a service, accept stream of events, each event has a type and
timestamp, need to support the query of top k most frequent types in a query
specified [start, end] time range.
4. closest number to target in BST
5. validate soduku / solve soduku, and optimizations
6. 给一个json object，给一个wildcard path with ‘?’ as arbitrary name，比如
a.?.b 找到所有符合path的objects
Apple一般onsite的时候4轮tech interview，中午的时候将来的manager带着吃午饭。
如果tech这4轮面的好会有第5轮见到hiring manager，如果有这一轮基本说明offer没
啥问题了，这轮会是一堆behavior。如果第5轮也没啥问题会有第6轮见大boss，继续
behavior，会问之前做过的project有多牛叉，会吹就行。
同等级下Apple的offer远不如FG给力，而且match不上去，bonus也不会写在offer
letter里面，虽然据说每年的refresh有些组相当多，但是感觉整体上跟FG还是差距比
较大。而且组跟组工作强度差别也很大，有些组忙死有些组闲死，不过software的组一
般都还好，感觉大部分人精神状态还是不错的。
就engineer水平来看，我有遇到水平相当不错的面试官，但是整体水准远不如FG。
他们各个组做项目是完全分开的，基本没交流。做东西完全是product driven，不过
engineer一般需要fullstack，需要自己end to end维护一个product，这点对有些人可
能还比较有吸引力。
############################################################################
###########
Amazon：
练手公司2，我面的是marketing solution和ads相关的team。大公司周期很长，感觉
recruiter不是很上心。
电面：
三哥，但是感觉还行没黑。
1.用trie来解决求dictionary里面所有符合given prefix的word。然后又扩展到prefix
里面有wildcard的情况，然后继续讨论如果要design a system做这个事情怎么搞，需
要注意哪些问题。
Onsite：
居然没有遇到三哥，除了一轮老中外其他都是老白，每一轮开始都是至少15分钟的
behavior，而且每个人还能换着花样问不一样的问题，感觉大部分脑细胞都花在这些没
用的东西上面了，所以感觉很不爽。
1. OOD Restaurant Reservation System
2. Merge K Sorted List
3. K Sized Sliding Window Sum/Minimum Value
4. 给一个css file里面很多class，然后class name里面其实很多重复的，怎么
compress用尽量最小size的string来表示，这样传输的byte比较少。
5. shorten url system design
6. longest palindromic substring
7. robot moving from topleft to bottomright corner of a matrix，matrix里面有
些cell是障碍物不能通过，只能往下或者往右走，有多少种方法。
8. 之前做的项目，和我之前坑爹公司的architecture
相比起他们的behavior问题，我觉得亚麻的engineer水平相当一般，很多design
principle都不知道，可能因为他们内部都直接用aws很多细节都不需要考虑，也有可能
跟我面的组有关系，如果面的是aws会好些吧。
亚麻最后给我senior title，但是package跟其他几家比起来差距略大，所以也就没再
继续谈。
############################################################################
###########
WalmartLab：
我面的是walmartlab里面仅存的几个不是三哥的组，通过靠谱的朋友内推。
面试题整体难度也还好，算法基本上都是常见题目，国人面试官都非常非常非常nice。
只说其中几轮比较有意思的吧
1.topological sort
2.design web crawler system，how to scale，what would be the bottle neck and
how to solve the problem
3. 如何用semaphore或者condition variable实现3个process p1, p2, p3，p2必须要
p1结束才能运行，p3必须要p2结束才能运行
4. bloom filter 如何implement，estimate false rate
5. what is the best design pattern do you think and why
他们onsite有一轮会是跟product manager聊天，就是瞎扯。一个小时我都在绞尽脑汁
找话题，应该是类似culture fit吧，看看你是不是比较容易融入team。
walmartlab是第一个给我比较decent offer的公司，cash给的很多，所以其实我很感激
，而且我面的组的work life balance极好，我见过的最好的没有之一，onsite居然有
两轮是video因为面试官WFH。平时干活也非常自由，没有OKR，没有deadline（是的你
没看错，啥都没有，performance完全老板说了算）。
不去walmartlab的原因是我觉得他们实在缺有经验的engineer，而且很多做的很多东西
都是实验性质的，没有明显的business impact，现阶段我还是比较想去一个大腿比较
多的地方抱一下。
############################################################################
###########
Sumo Logic：
一开始看到这家公司里面好多MIT毕业的人，而且听说他们bar很高，所以一开始也只是
想拿来做一下benchmark。他们基本上都用scala，如果懂一点scala效果会比较好但是
不懂对面试也完全没有影响。
他们的面试是先一轮phone，然后两次onsite，第一次onsite2轮，第二次onsite3轮，
第一次onsite过了才会有第二次onsite。第二次onsite每一轮会有两个面试官，每个面
试官都会出一道题目。
电面：
1. 两个binary tree，每个node存的值有两种可能，1或者0，把两个tree对应node做or
操作。
极为简单，扯了一下immutable data structure然后聊了一会之前做的东西就过了。
onsite 1：
1. 纯聊project和讨论他们现有的data ingestion架构，刚好他们最近想用Kafka所以
就这个话题聊了一个小时，最后没时间做题就结束了
2. 小三哥，但是也不黑。
given a list of intervals，query if another interval is totally covered by
the list of intervals。
totally covered是指整个区间都被某些已有的区间 cover了。
比如如果有 list of intervals = 【（1， 4），（2，8）】
given interval【3，6】就被完全cover了。
然后扩展到design a system来做这个事情，可以query，也可以insert interval，假
设query操作的频率远远大于insert操作，并且interval的数量非常非常多。
onsite 2：
1. 有意思的题目1，设计Bi-directional LRU cache data structure，既可以lookup
key to get value，也可以lookup value to get key，还支持set(key, value)操作，
后面又加了条件，concurrent的情况下，会有什么问题，如何改进，假如set这个操作
的频率远远小于get这个操作的频率，需要写代码实现。
2. robot from topleft to bottomright LC原题，无障碍和有障碍
3. given a list of sets，find all pair of sets having any intersection
4. 有意思的题目2，设计caltrain system，要实现caltrain上车下车刷卡扣钱整个功
能，assume每个station都跟一个central server相连，要处理如果有network
partition怎么办，eventually车费还是要charge到账户上，但是不能影响partition的
station正常运作。要处理某些人下车没刷卡怎么办，followup可以非常多
5. 有意思的题目3，仍然是设计一个cocurrent环境下的time leased cache，但是有些
区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
，如何让这个load的操作对同一个key尽量少发生，需要写代码实现。
这家的题目我觉得非常有意思，engineer都超级nice，感觉我见过的人的能力都非常不
错，年轻一点的反应非常快，年长一点的经验非常丰富。整体上看三哥并不多，虽然
engineering vp是三哥。
这家很有诚意，最后给我的base跟walmartlab差不多，再加上很难估值的option。他们
觉得他们的bar很高，能过他们面试的人不多，所以一旦你过了他们面试，要做好被他
们的recruiter不停骚扰的准备。
有关这个公司，在其他帖子里面我提到过，虽然engineering vp是个三哥，但是感觉还
比较靠谱，不像某些三哥吹牛没有边际，对于整个公司发展的前景比较有数，business
model也很promising，最近刚刚拿到一笔80M的投资。
############################################################################
###########
Palantir：
号称湾区面试最难的公司。但是again我运气比较好没有碰到很难的题目。我觉得这家
公司有点吹的过大了，本身做的东西根本没有什么技术含量，里面都是一群没经验的
stanford小年轻，都是自我感觉超好。另外去这家公司要做好准备每周工作60hours。
估值150亿了还给option我也是醉了，能上市不？我的看法就是这家公司基本就是坑，
从哪个角度来讲都不值得去。
他们的onsite上午会有3轮，然后中午吃完饭后会有一个小时的demo（因为实在没什么
意思所以我差点睡着了），如果上午过了下午还会有1 - 2轮，一般下午会有一轮
system design，另一轮是见hiring manager，如果上午没过demo结束就可以回家了。
电面：
万年不变的电面题，给一个array，问有没有duplicate
follow up1，只要index的距离 < k并且value相同就算duplicate
follow up2，只要index的距离 < k并且value的绝对值差 < d 就算duplicate
follow up3，follow up2能不能有time complexity O(n)的解？
Onsite：
1. OOD astroid game，就是飞机打石块的游戏，石块可以任意形状可以移动，飞机撞
上就挂了，飞机可以发射子弹，子弹打上石块会把石块分成多个小石块按照不同方向和
速度移动。要写伪代码。
2. 每个person有一个list of intervals，表示busy的时间段，问最busy的一段时间分
别都是谁busy。
3. 一个描述起来不算简单的题目，但是算法不难，在版上看到过但是细节记不清了，
好像是给一堆stock profile然后算profit
4. 一个2d matrix，被分成好几个区域，区域之间都是value为0的cell，每一堆
connected的非0cell算是一个区域，问和最大的区域是哪个，要设计API，怎么用json
return结果。
5. system design又是 distributed key-value store，万年不变的题目，后来没啥好
聊的只好跟面试官扯他们的那个atlas，distributed transaction layer，没办法想拿
offer跪舔还是需要的。
基本上每个面试官都是一副老子很牛逼的样子，一问他们到底做了什么牛逼的东西马上
支支吾吾说不出个所以然。他们的offer也没诚意，150k的base + 25k signon +
55000option，没谈就直接拒掉了。
############################################################################
###########
Dropbox：
Dropbox的面试题都是从题库出的，但问题是他们的题库并不大。所以，我可以负责任
的说，你在这个版上找到的面经题目，你在面试过程中绝对能碰到。另外他们复杂的算
法题目并不多，但是大部分是跟concurrency有关的问题。
一般标配是 2轮电面 + 6轮onsite，6轮onsite中居然有两轮是behavior和culture fit
另外，他们面试的要求都是要写能run的code，要写完整的solution，不能写个主要
function就完事。
电面：
1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
常大
2. 被人面过无数次的电话号码转成string，然后再word break那个题目
Onsite：
1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
用最简单的方法实现
3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
runnable代码。
4. system desgin那一轮是两个三哥，轮流轰炸了一个小时，把我之前做的所有东西完
全推翻了，所以这一轮没结束我就知道肯定挂了。
############################################################################
###########
后面这三个公司是整个面试过程中给我感觉最好的三个公司。
Uber：
Uber的效率不是一般的牛叉。我从刚开始被Uber联系到最后拿到offer基本在一个周之
内搞定。面完了Uber之后真的有点心动，因为面我的人我觉得都很牛逼，人也都很超
nice，非常乐于提供很多关于Uber的信息，整个氛围非常积极向上。老板虽然是个三哥
但是也没有任何能吐槽的地方，他手下现在也基本都是老中。
电面：
一般电面会是hiring manager，除了问了一下之前做过什么之外只有一道题目：
OOD card deck，要现场deug，需要能运行
电面后一个小时通知我可以onsite
Onsite：
onsite一般是5轮，中间老板带着吃午饭
5轮中必然有一轮是只讨论之前做过的project，要做好准备，一定要对自己之前做的东
西特别熟
另外我面试过程中问了不少怎么设计一个系统解决Uber实际问题这种题目，很新颖很有
意思
1. 问了我不少关于storm的问题，比如storm怎么保证exact once/at least once
semantic，如何做timed window join，因为我简历上有相关的东西，然后让我用storm
来做一个比较简单的sliding window count。
2. big integer multiplication，要求现场运行代码。
3. longest increasing subarray，longest increasing subpath in a tree，path只
能从root到某个leaf
4. boggle game，given a boggle board and a dictionary，find all words on the
board，
follow up，如果dictionay 不变但是board不停的变怎么优化
follow up，如果board不变但是dictionary不停的变怎么优化
5. given a matrix only containing 1 or 0，find how many rectangles are 4个角
都是1
6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
7. how to design a system to detect if dispatch algorithm has some bug，
dispatch主要是收集所有打车request和available driver的信息然后决定哪个driver
哪个客人
Onsite过后两个小时通知我有offer了，如果onsite过后一两天之内没通知的话，基本
上说明你的waiting list上，要等排在你前面的人据掉offer才可以继续下一步。
############################################################################
###########
Facebook：
initial round我是直接去onsite的，但是根据其他朋友的经验似乎电面或者onsite影
响也根本不大，因为第一轮基本只要没有太大的纰漏都会过。
Onsite：
一共5轮，如果是4级的话会是3轮coding，1轮behavior和1轮system design。因为偏
infra, 所以我有3轮是三哥，当时已经做好挂的准备了。
1. move all 0s to right end of the array
2. decode way
3. binary tree inorder iterator
4. determine if there is a subarray sum to target number
5. convert integer to string，1000 to “one thousand”
6. system design - design facebook music system，只需要design service tier，
两个API
get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
listened music ids for a given user last week. 这个call在load页面的时候要进
行，所以对latency要求比较高。
record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
system design，如何thread safe，如果是districuted syste怎么搞，能想到几种方法
8. behavior那一轮基本上围绕着的主题是，你之前碰到什么难解决的问题，怎么解决
的，你学到了什么，production有过什么比较傻叉的bug，怎么避免的。你之前做项目
有没有cross team的，你怎么说服其他team听你的，等等。聊得过多导致最后没有时间
所有这一轮没有coding
我觉得我的运气很好，再次没有碰到很难的题目，尤其是算法。
############################################################################
###########
Google：
狗家如果真的想快的话还是可以的，我从开始被recruiter联系到offer也是一个周之内
搞定。
狗家和F家整个感觉都很好，面试官都很乐意帮忙，而且明显感觉到水平跟其他公司不
一样，技术功底非常扎实。
再次运气很好所以没有碰到很偏很难的题目，基本上就是水过了。其中几道比较有意思
的题目：
1. 一个正整数可以表示成其他几个正整数的平方和，给任何一个正整数，求最少的那
几个正整数，平方和是给定的数，比如14 = 1^2 + 2^2 + 3^2，如果给的数是14，应该
返回（1，2，3）
2. 给一个dictionary，然后可以support的query是，给一个string，返回在
dictionary里面包含给定string的所有character的最短的string
3. 如何设计google login system
4. web crawl的时候如何判断两个document是相同/相似的。
抱歉很多细节实在记不清了，表达能力也有限没办法在这个帖子里面说的很明白。如果
大家有问题我会尽我所能回答，谢谢。。 |
g*********e
发帖数: 14401 | |
f***o
发帖数: 1548 | |
i******s
发帖数: 301 | |
h*c
发帖数: 23 | 5 厉害！
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
b******i
发帖数: 914 | 6 大牛，赞
最后去哪儿了
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
w*********e
发帖数: 49 | 7 跪了，可以透露下最后去哪了么，还有这么多面试都要请假吗。。。
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
i******s
发帖数: 301 | |
b*****n
发帖数: 618 | 9 把面试集中到一段时间，然后休假
我休假的最后两个礼拜基本上每天一个onsite
【在 w*********e 的大作中提到】
: 跪了，可以透露下最后去哪了么，还有这么多面试都要请假吗。。。
|
z*******o
发帖数: 4773 | |
|
|
w***y
发帖数: 6251 | 11 大神啊
可以介绍一下 distributed kv store 这个题怎么做吗？ |
b*****n
发帖数: 618 | 12 这个题目可以无限可能的答，根据不同use case实现可以有很多种。
In general的话，看看现有的几个比较成熟的就可以了呀
HBase，Cassandra，DynamoDB
【在 w***y 的大作中提到】
: 大神啊
: 可以介绍一下 distributed kv store 这个题怎么做吗？
|
a*****u
发帖数: 1712 | 13 lz offer很不错啊，问下lz这两年在哪个公司工作？ |
l*****z
发帖数: 3022 | 14 楼主的驴是L或T？
【在 a*****u 的大作中提到】
: lz offer很不错啊，问下lz这两年在哪个公司工作？
|
b*****n
发帖数: 618 | 15 在湾区一个被版上黑出翔的三哥公司
【在 a*****u 的大作中提到】
: lz offer很不错啊，问下lz这两年在哪个公司工作？
|
b*****n
发帖数: 618 | 16 不是。。这两家没面而已
我的驴要是L或者T我也不会去面什么雅虎亚麻苹果之类的
【在 l*****z 的大作中提到】
: 楼主的驴是L或T？
|
l****c
发帖数: 782 | 17 楼主是Csco的？
【在 b*****n 的大作中提到】
: 不是。。这两家没面而已
: 我的驴要是L或者T我也不会去面什么雅虎亚麻苹果之类的
|
i**********g
发帖数: 758 | 18 oracle?
感觉lz的说话回帖都很成熟啊，读书前也工作过吧
【在 b*****n 的大作中提到】
: 在湾区一个被版上黑出翔的三哥公司
|
A*******e
发帖数: 2419 | 19 背景：ms毕业不到两年
亚麻最后给我senior title
楼主牛人。
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
A*******e
发帖数: 2419 | 20 是因为包裹明显比其他高吗？G感觉没太大意思啊。
【在 i******s 的大作中提到】
: 去了没报数字的那家
|
|
|
i**********g
发帖数: 758 | 21 大牛能分享下准备过程吗？就是刷那些题？
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
b*****n
发帖数: 618 | 22 这个我后面会讲的，如果没那么着急的话就请先稍等片刻。。
容我先把剩下几个公司黑完
【在 i**********g 的大作中提到】
: 大牛能分享下准备过程吗？就是刷那些题？
|
b*****n
发帖数: 618 | 23 不比其他高，只是觉得去其他家的时机没那么理想。
其实一开始只打算去G，其他家只有两个作用，练手或者抬价，不过面试过程中确实有
动摇过。
【在 A*******e 的大作中提到】
: 是因为包裹明显比其他高吗？G感觉没太大意思啊。
|
f*********5
发帖数: 576 | 24 加上这句就让人觉得很奇怪
感觉上A宁可给SDE2 + high package也不会给SDE3 + low package
很好奇lz面的是哪家亚麻
但是package跟其他几家比起来差距略大，
【在 A*******e 的大作中提到】
: 背景：ms毕业不到两年
: 亚麻最后给我senior title
: 楼主牛人。
|
S**********5
发帖数: 896 | |
r****7
发帖数: 2282 | 26 我觉得U给的略多啊，如果你不是互联网公司的驴子的话。
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
b*****n
发帖数: 618 | 27 很奇怪吗？我面的是总部不是其他子公司，但是team match也给我match三番的组。
我walmarlab拿的是staff title，uber拿的是senior title
【在 f*********5 的大作中提到】
: 加上这句就让人觉得很奇怪
: 感觉上A宁可给SDE2 + high package也不会给SDE3 + low package
: 很好奇lz面的是哪家亚麻
:
: 但是package跟其他几家比起来差距略大，
|
b*****n
发帖数: 618 | 28 算是互联网搞大数据的公司
跟U面的组做的东西刚好比较match，运气比较好
【在 r****7 的大作中提到】
: 我觉得U给的略多啊，如果你不是互联网公司的驴子的话。
|
A*******e
发帖数: 2419 | 29 膜拜。
【在 b*****n 的大作中提到】
: 很奇怪吗？我面的是总部不是其他子公司，但是team match也给我match三番的组。
: 我walmarlab拿的是staff title，uber拿的是senior title
|
m******s
发帖数: 1469 | 30 Zan
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
|
|
r****7
发帖数: 2282 | 31 你F家的offer和我差不多，不知道你g是多少。但是uber的title比我高一级，亚麻我没
面，面的话估计也拿不到senior。
不过你骑驴找马能面这么多公司，真是够牛逼的
【在 b*****n 的大作中提到】
: 很奇怪吗？我面的是总部不是其他子公司，但是team match也给我match三番的组。
: 我walmarlab拿的是staff title，uber拿的是senior title
|
c*******e
发帖数: 621 | 32 感谢楼主分享这么多有用信息
uber 25k股RSU 那就是$32*25000=$800k？ 那远多于fb的offer啊
按我的经验g家只愿意beat fb，却不愿beat uber
所以我推测g也就比fb多一点，match不了uber
老实说，我觉得uber的offer更诱人 |
c***3
发帖数: 10 | 33 赞～ LZ赶紧更新啊 正在面试中 求面经啊
另外LZ整个找工作工程用了多长时间啊？ |
r****7
发帖数: 2282 | 34 G倒是会尝试beat
不过我觉得lz硕士两年非FG的经验，能拿下现在的uber的senior真是太少见了。即使是
FG的经验如果没senior的title都很难。
【在 c*******e 的大作中提到】
: 感谢楼主分享这么多有用信息
: uber 25k股RSU 那就是$32*25000=$800k？ 那远多于fb的offer啊
: 按我的经验g家只愿意beat fb，却不愿beat uber
: 所以我推测g也就比fb多一点，match不了uber
: 老实说，我觉得uber的offer更诱人
|
i**********g
发帖数: 758 | 35 对啊，LZ太厉害了。。。
【在 r****7 的大作中提到】
: G倒是会尝试beat
: 不过我觉得lz硕士两年非FG的经验，能拿下现在的uber的senior真是太少见了。即使是
: FG的经验如果没senior的title都很难。
|
b**********5
发帖数: 7881 | 36 你有什么GitHub么？ 你能说说你这些题目都怎么回答么？ |
A*******e
发帖数: 2419 | 37 我猜楼主背景很强，比如四巨头毕业，做的项目又正是热门。无论如何，感谢愿意无私
分享的大牛。
【在 r****7 的大作中提到】
: G倒是会尝试beat
: 不过我觉得lz硕士两年非FG的经验，能拿下现在的uber的senior真是太少见了。即使是
: FG的经验如果没senior的title都很难。
|
b**********5
发帖数: 7881 | 38 我也是这个背景， 可是快一年了， 也找不到工作。。。 弯曲面试要宽松一点？
【在 A*******e 的大作中提到】
: 我猜楼主背景很强，比如四巨头毕业，做的项目又正是热门。无论如何，感谢愿意无私
: 分享的大牛。
|
l*****z
发帖数: 3022 | 39 楼主这么年轻，又这么牛，的确应该去U博一博，说不准就大发了呢。去G养老公司感觉
可惜了。
【在 c*******e 的大作中提到】
: 感谢楼主分享这么多有用信息
: uber 25k股RSU 那就是$32*25000=$800k？ 那远多于fb的offer啊
: 按我的经验g家只愿意beat fb，却不愿beat uber
: 所以我推测g也就比fb多一点，match不了uber
: 老实说，我觉得uber的offer更诱人
|
l*****z
发帖数: 3022 | 40 明显是刷题不够。leetcode 来三遍FLGTUA都是囊中物
【在 b**********5 的大作中提到】
: 我也是这个背景， 可是快一年了， 也找不到工作。。。 弯曲面试要宽松一点？
|
|
|
m*5
发帖数: 127 | 41 点赞，支持这种干货满满的帖子，比那些天天挖坑瞎喷的高到不知道哪里去了。 |
b**********5
发帖数: 7881 | 42 小姐，我发面经， 不仅给题目， 还给答案，我的解法。。。老实说， 这种面经， 没
什么答案， 没什么和面试官交流过程的， 没什么用
【在 m*5 的大作中提到】
: 点赞，支持这种干货满满的帖子，比那些天天挖坑瞎喷的高到不知道哪里去了。
|
f*****d
发帖数: 2285 | 43 赞！
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
d******v
发帖数: 801 | |
f*****d
发帖数: 2285 | 45 看了楼主的面经，断定楼主是L家的。哈哈
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
a*******6
发帖数: 591 | 46 他自己都说不是L家的了
【在 f*****d 的大作中提到】
: 看了楼主的面经，断定楼主是L家的。哈哈
|
i**d
发帖数: 20 | 47 LZ是牛人，从来潜水的我，特意申了个账户，过来捧场。。。 |
n**********n
发帖数: 196 | 48 楼主应该是RF的
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
M*********r
发帖数: 70 | |
b*****n
发帖数: 618 | 50 不好意思，没法答案的原因是实在有点长，如果需要的话我可以另开一个帖子单独讨论。
还有交流过程我实在记不得这么多了，而且如果真写出来也不知道长到哪里去了。
你如果对特定的题目有问题我可以尝试回忆一下。
【在 b**********5 的大作中提到】
: 小姐，我发面经， 不仅给题目， 还给答案，我的解法。。。老实说， 这种面经， 没
: 什么答案， 没什么和面试官交流过程的， 没什么用
|
|
|
b*****n
发帖数: 618 | |
f*******r
发帖数: 976 | 52 Congrats!
=================================
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给） |
b*****n
发帖数: 618 | 53 大牛谦虚了，我为了换工作强行休假搞的，找不到工作就完了，破釜沉舟比较有效果。。
【在 r****7 的大作中提到】
: 你F家的offer和我差不多，不知道你g是多少。但是uber的title比我高一级，亚麻我没
: 面，面的话估计也拿不到senior。
: 不过你骑驴找马能面这么多公司，真是够牛逼的
|
b*****n
发帖数: 618 | 54 没错，确实很诱人，而且G确实match不了
【在 c*******e 的大作中提到】
: 感谢楼主分享这么多有用信息
: uber 25k股RSU 那就是$32*25000=$800k？ 那远多于fb的offer啊
: 按我的经验g家只愿意beat fb，却不愿beat uber
: 所以我推测g也就比fb多一点，match不了uber
: 老实说，我觉得uber的offer更诱人
|
b*****n
发帖数: 618 | 55 大哥，我不会认识你吧。。
【在 i**d 的大作中提到】
: LZ是牛人，从来潜水的我，特意申了个账户，过来捧场。。。
|
g**4
发帖数: 863 | 56 LZ大牛，offer都那么值钱，而且MS + 2年不到去亚麻能拿到senior！ |
b**********5
发帖数: 7881 | 57 那你能不能另外一个帖子里， 谈一下你所有的design question的回答？
论。
【在 b*****n 的大作中提到】
: 不好意思，没法答案的原因是实在有点长，如果需要的话我可以另开一个帖子单独讨论。
: 还有交流过程我实在记不得这么多了，而且如果真写出来也不知道长到哪里去了。
: 你如果对特定的题目有问题我可以尝试回忆一下。
|
b*****n
发帖数: 618 | 58 OK，我尽量，可以抛砖。
【在 b**********5 的大作中提到】
: 那你能不能另外一个帖子里， 谈一下你所有的design question的回答？
:
: 论。
|
b**********5
发帖数: 7881 | 59 那我接下来几天， 会对你的所有design题， 答一遍。 你要告诉我你怎么答的，面试
官问过什么细节
【在 b*****n 的大作中提到】
: OK，我尽量，可以抛砖。
|
p****2
发帖数: 387 | |
|
|
i**d
发帖数: 20 | 61 恩，中午一起散步的兄弟。。。暗号：红烧肉，烤鸭 哈哈
【在 b*****n 的大作中提到】
: 大哥，我不会认识你吧。。
|
n*********r
发帖数: 2493 | |
w*****d
发帖数: 105 | |
p*******8
发帖数: 344 | 64 楼主太牛了！offer的级别都远高于同等经验的，uber的offer比我的更高，虽然我经验
更多。。分享点经验怎么把算法弄得那么牛吧！ |
a****r
发帖数: 1 | |
i*****d
发帖数: 962 | |
j********l
发帖数: 325 | |
p**o
发帖数: 1012 | 68 赞，好牛啊！
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
z***b
发帖数: 127 | 69 楼主好牛啊，下面这题怎么答的啊？
3. design a service, accept stream of events, each event has a type and
timestamp, need to support the query of top k most frequent types in a query
specified [start, end] time range. |
h****e
发帖数: 2125 | 70 你是不是现在base比较高？你这完全是T3拿高端T4的offer啊。
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
|
|
d******v
发帖数: 801 | 71 楼主大牛，能给说说怎么复习系统设计的吗？网上看了点资料，还是有点云里雾里的感
觉。谢谢！
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
h******6
发帖数: 2697 | 72 太牛了 lz我想问一下你没毕业的时候已经这么牛了还是这两年工作当中学到这么多东
西？ |
m******3
发帖数: 346 | 73 大牛，请问你骑驴找马准备了多久，有什么准备经验么，想知道大概要准备到什么水平
才能去面这些公司 |
c****h
发帖数: 344 | |
C*Y
发帖数: 736 | 75 楼主最后去了哪家？看起来还是U的offer远远抛离其它的，而且U家貌似未来发展空间
更大 |
b*****n
发帖数: 618 | 76 多谢大牛捧场
没有你我拿不到这些offer
另外求继续带红烧肉烤鸭
【在 i**d 的大作中提到】
: 恩，中午一起散步的兄弟。。。暗号：红烧肉，烤鸭 哈哈
|
e**********0
发帖数: 502 | |
e*n
发帖数: 22 | |
h*********g
发帖数: 38 | 79 我寝牛衣敝
爱从抽马策
真境逾难抛
理道须任贤
更欲投何处
爱君直如发
包虎戢金戈
子产昔田畴 |
f****a
发帖数: 98 | |
|
|
f********e
发帖数: 100 | |
b******g
发帖数: 77 | 82 楼主很厉害，天才+努力，没得说
码这么多字不容易，谢谢分享
以楼主的实力和性格，以后在公司大有发展。
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
s****s
发帖数: 345 | 83 太牛了 不过表示怀疑amazon给你sr的title啊
10有89是她们的recruiter忽悠你 因为她们recruiter把SE II也叫过sr
不过反正你也不会去
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
b*****n
发帖数: 618 | 84 I see。。那应该是我naive了。
多谢大牛指点，确实是recruiter说的sr title，
但是我没有看到真的offer就拒掉了
senior是SE III吗？
这个具体怎么算
【在 s****s 的大作中提到】
: 太牛了 不过表示怀疑amazon给你sr的title啊
: 10有89是她们的recruiter忽悠你 因为她们recruiter把SE II也叫过sr
: 不过反正你也不会去
|
a***u
发帖数: 383 | |
s********8
发帖数: 442 | 86 google onsite 的第一题 是用DP 做吗
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
b*****n
发帖数: 618 | 87 也可以用BFS，不过我觉得DP好写点所以用DP做的。
【在 s********8 的大作中提到】
: google onsite 的第一题 是用DP 做吗
|
B********t
发帖数: 147 | 88 这题DP的转移方程怎么写？
【在 b*****n 的大作中提到】
: 也可以用BFS，不过我觉得DP好写点所以用DP做的。
|
b*****n
发帖数: 618 | 89 dp[i] = 1 + min of all dp[i - k ^ 2] for k >= 1 && k <= sqrt(i)
【在 B********t 的大作中提到】
: 这题DP的转移方程怎么写？
|
g*****y
发帖数: 1120 | 90 楼主ms+2yr拿西雅图SDE3的话，估计一半以上的亚麻员工要造反了。
【在 b*****n 的大作中提到】
: I see。。那应该是我naive了。
: 多谢大牛指点，确实是recruiter说的sr title，
: 但是我没有看到真的offer就拒掉了
: senior是SE III吗？
: 这个具体怎么算
|
|
|
b*****n
发帖数: 618 | 91 已经修改原帖了，给大家造成误会请包涵。
【在 g*****y 的大作中提到】
: 楼主ms+2yr拿西雅图SDE3的话，估计一半以上的亚麻员工要造反了。
|
e*********o
发帖数: 505 | 92 膜拜一下牛人。
【在 b*****n 的大作中提到】
: 前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
: 谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
: ，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
: 背景：
: ms毕业不到两年
: 主要申请公司：
: offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
: amazon，apple
: reject：dropbox
: 主要几个包裹：
|
e********3
发帖数: 229 | 93 请问palantir店面第三题的O(n)算法怎么解 |
b*****n
发帖数: 618 | 94 每d个数可以组成一个bucket，
比如d＝4，
那么
bucket［1］＝［1，2，3，4］
bucket［2］＝［5，6，7，8］
。。。
每个bucket最多只能有两个数存在否则就有duplicate，
另外除了要看每个数自己所在bucket之外还要看前边和后边相邻的两个。
用一个hashmap纪录bucket id跟每个数的对应关系。
【在 e********3 的大作中提到】
: 请问palantir店面第三题的O(n)算法怎么解
|
w****r
发帖数: 15252 | |
s******x
发帖数: 417 | |
m******3
发帖数: 346 | 97 楼主能说说yahoo这两题怎么答么？
1. 如何设计一个priorityqueue service，client可以submit job request然后server
按照priority执行
3. 给很多整数，如何用mapreduce找median，如果是很多float数，可以有一定的误差
，如何找 |
m******3
发帖数: 346 | 98 apple的这两题
2. auto completion - design the service
3. design a service, accept stream of events, each event has a type and
timestamp, need to support the query of top k most frequent types in a query
specified [start, end] time range. |
m******3
发帖数: 346 | 99 walmart lab的这个
2.design web crawler system，how to scale，what would be the bottle neck and
how to solve the problem |
m******3
发帖数: 346 | 100 Sumo Logic的，感觉这家题目都很难啊
2. 小三哥，但是也不黑。
given a list of intervals，query if another interval is totally covered by
the list of intervals。
totally covered是指整个区间都被某些已有的区间 cover了。
比如如果有 list of intervals = 【（1， 4），（2，8）】
[这个我的想法就是按照LC先做合并interval,然后检查，有更好的方法么？]
given interval【3，6】就被完全cover了。
然后扩展到design a system来做这个事情，可以query，也可以insert interval，假
设query操作的频率远远大于insert操作，并且interval的数量非常非常多。
[这个扩展怎么搞？]
onsite 2：
1. 有意思的题目1，设计Bi-directional LRU cache data structure，既可以lookup
key to get value，也可以lookup value to get key，还支持set(key, value)操作，
后面又加了条件，concurrent的情况下，会有什么问题，如何改进，假如set这个操作
的频率远远小于get这个操作的频率，需要写代码实现。
4. 有意思的题目2，设计caltrain system，要实现caltrain上车下车刷卡扣钱整个功
能，assume每个station都跟一个central server相连，要处理如果有network
partition怎么办，eventually车费还是要charge到账户上，但是不能影响partition的
station正常运作。要处理某些人下车没刷卡怎么办，followup可以非常多
5. 有意思的题目3，仍然是设计一个cocurrent环境下的time leased cache，但是有些
区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
，如何让这个load的操作对同一个key尽量少发生，需要写代码实现 |
|
|
m******3
发帖数: 346 | 101 dropbox的，感觉这家也很难
1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
常大
Onsite：
1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
[这个应该是用circular window吧，concurrent怎么做呢？]
2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
用最简单的方法实现
3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
runnable代码。 |
m******3
发帖数: 346 | 102 uber的
4. boggle game，given a boggle board and a dictionary，find all words on the
board，
follow up，如果dictionay 不变但是board不停的变怎么优化
follow up，如果board不变但是dictionary不停的变怎么优化
5. given a matrix only containing 1 or 0，find how many rectangles are 4个角
都是1
6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
7. how to design a system to detect if dispatch algorithm has some bug，
dispatch主要是收集所有打车request和available driver的信息然后决定哪个driver
哪个客人 |
m******3
发帖数: 346 | 103 Facebook的这两个
6. system design - design facebook music system，只需要design service tier，
两个API
get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
listened music ids for a given user last week. 这个call在load页面的时候要进
行，所以对latency要求比较高。
record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
system design，如何thread safe，如果是districuted syste怎么搞，能想到几种方
法 |
s******x
发帖数: 417 | 104 能说说这个log_hit get_last_5mins_hit吗？
好像是常见题，但是我的确没找到。谢谢
【在 m******3 的大作中提到】
: dropbox的，感觉这家也很难
: 1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
: 常大
: Onsite：
: 1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
: [这个应该是用circular window吧，concurrent怎么做呢？]
: 2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
: 果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
: 用最简单的方法实现
: 3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
|
m******3
发帖数: 346 | 105 Goole的下面几道
2. 给一个dictionary，然后可以support的query是，给一个string，返回在
dictionary里面包含给定string的所有character的最短的string
3. 如何设计google login system
4. web crawl的时候如何判断两个document是相同/相似的。 |
m******3
发帖数: 346 | 106 不好意思，问了好多，楼主有空帮着回答一下吧，其他有兴趣的同学，也一起讨论吧 |
s******x
发帖数: 417 | 107 这个第一题我觉得就是建立map，把string里所有character都记数。
然后dictionary里面对每个string也一样处理，
然后query的时候，对比character数量，找到最短。
【在 m******3 的大作中提到】
: Goole的下面几道
: 2. 给一个dictionary，然后可以support的query是，给一个string，返回在
: dictionary里面包含给定string的所有character的最短的string
: 3. 如何设计google login system
: 4. web crawl的时候如何判断两个document是相同/相似的。
|
m******3
发帖数: 346 | 108 log_hit get_last_5mins_hit吗，这个我也没看到过原题，不过记得以前看到这里讨论
过，大概思路是用一个circular window, 如果以second为单位，需要一个5*60的
window |
m******3
发帖数: 346 | 109 这个map的key 和 value分别是什么呢？
【在 s******x 的大作中提到】
: 这个第一题我觉得就是建立map，把string里所有character都记数。
: 然后dictionary里面对每个string也一样处理，
: 然后query的时候，对比character数量，找到最短。
|
m******3
发帖数: 346 | 110 找到了，这个帖子有讨论
http://www.mitbbs.com/article_t/JobHunting/32549839.html
【在 s******x 的大作中提到】
: 能说说这个log_hit get_last_5mins_hit吗？
: 好像是常见题，但是我的确没找到。谢谢
|
|
|
e********3
发帖数: 229 | 111 那可以这样吗?用d-1个数组成一个bucket.这样只要第二个数落进相同的bucket并且
index相差k就是dup.同时还要比较左右两边.算bucket可以用数的值/3得到bucket id然
后作为hashmap的key,value可以用一个node包含这个数的index和value.不清楚为什么
你用d来作为bucket size.是有什么地方我miss了吗?
【在 b*****n 的大作中提到】
: 每d个数可以组成一个bucket，
: 比如d＝4，
: 那么
: bucket［1］＝［1，2，3，4］
: bucket［2］＝［5，6，7，8］
: 。。。
: 每个bucket最多只能有两个数存在否则就有duplicate，
: 另外除了要看每个数自己所在bucket之外还要看前边和后边相邻的两个。
: 用一个hashmap纪录bucket id跟每个数的对应关系。
|
s******x
发帖数: 417 | 112 key就是character，value是这个character在这个string内的个数啊。
参考leetcode minslidingwindow。
【在 m******3 的大作中提到】
: 这个map的key 和 value分别是什么呢？
|
B********t
发帖数: 147 | 113 前提是 必须是整数吧
【在 b*****n 的大作中提到】
: 每d个数可以组成一个bucket，
: 比如d＝4，
: 那么
: bucket［1］＝［1，2，3，4］
: bucket［2］＝［5，6，7，8］
: 。。。
: 每个bucket最多只能有两个数存在否则就有duplicate，
: 另外除了要看每个数自己所在bucket之外还要看前边和后边相邻的两个。
: 用一个hashmap纪录bucket id跟每个数的对应关系。
|
b*****n
发帖数: 618 | 114 首先，这是一个size为k的sliding window，hashmap里面应该只存最近的k个数。
其次，bucket的size（最大与最小可能值的差）只要保证＝＝d就行，所以可能其实应
该是d＋1吧，我只是说个思路，size到底是什么不重要。
【在 e********3 的大作中提到】
: 那可以这样吗?用d-1个数组成一个bucket.这样只要第二个数落进相同的bucket并且
: index相差k就是dup.同时还要比较左右两边.算bucket可以用数的值/3得到bucket id然
: 后作为hashmap的key,value可以用一个node包含这个数的index和value.不清楚为什么
: 你用d来作为bucket size.是有什么地方我miss了吗?
|
b*****n
发帖数: 618 | 115 不需要吧
唯一的要求就是bucket的size是d，
这个bucket到底从哪里开始算的，是不是整数完全不重要。
【在 B********t 的大作中提到】
: 前提是 必须是整数吧
|
b*****n
发帖数: 618 | 116 这个题目在另一个帖子里面讨论过了
http://www.mitbbs.com/article_t/JobHunting/32989651.html
【在 s******x 的大作中提到】
: key就是character，value是这个character在这个string内的个数啊。
: 参考leetcode minslidingwindow。
|
b*****n
发帖数: 618 | 117 大哥，这个数量有点多啊，你得给我点时间码字。
另外，这些题目我的解也不一定是最好的解，仅供参考。
【在 m******3 的大作中提到】
: 不好意思，问了好多，楼主有空帮着回答一下吧，其他有兴趣的同学，也一起讨论吧
|
s******x
发帖数: 417 | 118 坐等您的解答。
提前感谢！
【在 b*****n 的大作中提到】
: 大哥，这个数量有点多啊，你得给我点时间码字。
: 另外，这些题目我的解也不一定是最好的解，仅供参考。
|
J*******o
发帖数: 741 | 119 太牛了，lz如果能分享一下如何准备的就更赞拉 |
b*****n
发帖数: 618 | 120 算法真心不牛，你应该也见过搞ACM的，面试从来不需要刷题，那个才叫牛。。
级别这个东西我倒是有一点点心得，就是看对面组的老板是不是特别想要你，做的东西
是不是特别match，如果是的话一般级别都能要下来，这种事情一来运气极为重要因为
坑不是随处都有，二来自己之前做的东西也要尽量挑个还不错的方向。
【在 p*******8 的大作中提到】
: 楼主太牛了！offer的级别都远高于同等经验的，uber的offer比我的更高，虽然我经验
: 更多。。分享点经验怎么把算法弄得那么牛吧！
|
|
|
b*****n
发帖数: 618 | 121 这个题目我觉得我答的挺简单的，但是看起来对面那边也不怎么懂。。
这是个经典的top trend问题，有很多现成的solution来首先得到和处理数据。
因为这个题目当时要求可能query near-real-time的结果，所以我当时直接上Kafka +
Storm，
如果对数据的latency要求没那么高的话，用batch process更好，比如spark/hadoop
mapreduce都可以。
Kafka用来stream event flow，然后Storm process event stream可求top trend
具体用Storm怎么做这一篇文章比较经典：
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
归根结底是sliding window aggregation，随便一个能做这种事情的工具都可以，自己
写一个出来也可以，方法都是一样的。
把时间分成可以容忍误差的小块（比如，每秒），然后每个小块求每种type的event的
数量。
process的结果需要存到persistent datastorage里面做query，比如存到一个kv store
里面，或者database也可以，然后就是 select count(*), type from xxx where
timestamp < xxx and timestamp > xxx group by type order by count(*) limit 10
;这种query。
如果再想加速query的话，比如数据量还是非常非常大，count(*)操作可能会搞很久，
这个首先kv store对于count(*) 和 top k这种的常见agg value一般都会有
precomputation，所以本身就有优化，如果实在没有的话，可以做的事情是自己做
precompute，搞一种数据结构，比如可以利用不同的粒度建一个类似的tree的结构，
tree的leaf node是每秒钟每个type的数量，然后非leaf node就是不同粒度下做的
precompute，可以precompute 每分钟/每小时等等等等，这样做aggretation会快一些
。如果type的种类实在太多每个node存不下，可以适当舍弃一些frequency比较小的
type，比如可以设置一个threashold，频率小于xx的就不用考虑了，这样速度会更快些。
query
【在 z***b 的大作中提到】
: 楼主好牛啊，下面这题怎么答的啊？
: 3. design a service, accept stream of events, each event has a type and
: timestamp, need to support the query of top k most frequent types in a query
: specified [start, end] time range.
|
b*****n
发帖数: 618 | 122 我也是东戳西戳瞎看的
我的另一个帖子里面有一些内容，除了在另一个帖子里面说的资料之外，
半海大神之前的总结贴和flamingos的总结贴也很牛
按照他们帖子里面说的一步一步来，可以先把基本的需要知道的知识和概念搞明白，
然后可以从几个常见的system入手，争取能把一种经典的搞明白，然后很多东西都可以
互相借用。
比如shorten url，feed system等等。
【在 d******v 的大作中提到】
: 楼主大牛，能给说说怎么复习系统设计的吗？网上看了点资料，还是有点云里雾里的感
: 觉。谢谢！
|
b*****n
发帖数: 618 | 123 毕业的时候不懂大数据和system，不过学上的还行，至少几门比较基础的课程，比如OS
，Network，database，web tech还算可以。
大部分东西还是靠工作后慢慢学习和积累的，有机会接触这些东西有实战经验确实非常
有用，可以上手更快。
【在 h******6 的大作中提到】
: 太牛了 lz我想问一下你没毕业的时候已经这么牛了还是这两年工作当中学到这么多东
: 西？
|
b*****n
发帖数: 618 | 124 准备过程和经验在另一个帖子里了。。
大概到什么水平我也没底，所以我一开始面了很多练手的公司，
不过后来觉得练的有点多了，其实没有必要，一般练2-3个就可以了，基本上会有点感
觉，大概知道自己能不能有offer，面试的过程也是个学习和进步的过程，到一定程度
一般能做到心里有数。
【在 m******3 的大作中提到】
: 大牛，请问你骑驴找马准备了多久，有什么准备经验么，想知道大概要准备到什么水平
: 才能去面这些公司
|
b*****n
发帖数: 618 | 125 1.这个跟对面的交流需要比较多定下来一些requirement，比如要求master接受request
，然后让worker执行，client可以query master得到request的进度，master假如挂了
，重启之后仍然能知道所有已经运行完的/正在运行的/还没运行的request的信息，当
一个request在一个worker上运行的时候master挂了那个request应该继续运行不受影响。
这个其实就是个worker pool和scheduler，照着jobtracker或者yarn答就可以了，不过
我没答的那么复杂，既然需要master需要知道所有的task信息，就干脆写到一个
persistent storage里面这样能保证不丢，比如用个kv store或者database都可以，然
后master和worker通过zookeeper来做heartbeat和task assignment，kv store记录每
个task的状态这样restart后可以恢复所有state，worker运行request期间本身不需要
master介入。如果client query进度比较频繁，master可以加memory的write through
cache。
2.这个一般有两种方法吧：
1）类似于linear time求某个array的median的方法，需要多个mapreduce iteration，
每个iteration对每个分段求median，然后利用汇总的所有的median的范围来舍弃一部
分不可能是median的数，然后继续下一个iteration，这样一般效率不高。
2）类似于count sort，mapper记录每个value出现的次数，然后reducer汇总利用出现
的次数来求median，如果数是float的话，可以对所有可能的value分段，每段可以
cover的长度是2×误差，然后对每端进行count来求median
server
【在 m******3 的大作中提到】
: 楼主能说说yahoo这两题怎么答么？
: 1. 如何设计一个priorityqueue service，client可以submit job request然后server
: 按照priority执行
: 3. 给很多整数，如何用mapreduce找median，如果是很多float数，可以有一定的误差
: ，如何找
|
b*****n
发帖数: 618 | 126 2.这个也是个经典题目，每个人问的侧重点可以非常不一样，
这次被问的侧重点后台的index数据结构是神马，估算数据结构需要多大的空间，以及
如何建index。
这个题目一般第一反应是trie，我想了想决定给一个比较费空间但是可以直接用HBase
的解法。。就是把所有可能的prefix做key，然后求它们的后面query频率最高的top x
，这样就可以直接对key lookup。。更新的话，不用很频繁因为process的cost比较高
，offline时不时更新一下就可以了。。
对面问我为什么这么做我说这样比较简单，HBase lookup + mapreduce，不过除了空间
占的比较大之外还有另一个问题就是hotspot，我说那就加random prefix加cache看看
行不行。。
总之。。能上kv store就上kv store，然后哪里需要优化就上cache可以解决很多问题
（这个不一定是对的，但是一般能work），对面表示能不能用一种比较明显的数据结构
来做，我说可以，可能你想要trie吧，不过后面就没再聊了。
3.在前面的回复里面已经说过了
query
【在 m******3 的大作中提到】
: apple的这两题
: 2. auto completion - design the service
: 3. design a service, accept stream of events, each event has a type and
: timestamp, need to support the query of top k most frequent types in a query
: specified [start, end] time range.
|
b*****n
发帖数: 618 | 127 这个也是经典题目，每个人问的东西也会不一样。
这次对面问的侧重点是在不同阶段bottleneck是什么，打算怎么解决。
我答的是：
1.开始的时候network IO是block的因素，需要解决，方法跟dropbox那个题目类似。。
用不同的pool做不同的事情。
2.然后process的latency会是问题，因为要crawl的文件很多，然后开始分布式，把
workload分布到不同的机器/网络上，url based sharding
3.假设cpu很强劲，那么下一个问题可能是每个shard需要记录自己之前已经crawl过的
url，如果直接存内存的话到一定程度就受不了了，所以需要一个比较好的解决方案，
我感觉又可以用老套路了，直接上kv store就行了。。但是被告知不行，这么轻量级的
操作不想借助于外界的系统，而且kv store这个空间占的又多了去了。只能上bloom
filter来解决，但是有一定的false rate，不过大不了多download少数，问题不大。。
我感觉这一轮答的不是特别好，但是应该还是过了。。
and
【在 m******3 的大作中提到】
: walmart lab的这个
: 2.design web crawler system，how to scale，what would be the bottle neck and
: how to solve the problem
|
m******3
发帖数: 346 | 128 楼主不好意思，你有空慢慢写，不着急
【在 b*****n 的大作中提到】
: 大哥，这个数量有点多啊，你得给我点时间码字。
: 另外，这些题目我的解也不一定是最好的解，仅供参考。
|
b*****n
发帖数: 618 | 129 2.可以用segment tree，
不过我用的是跟你一样的方法，然后用同样的方法做system。
query说白了就是个binary search，做一个view只存merge过的情况，写的时候开销会
比较大，不过可以仿照HBase，memory里面存的那部分可以一定的频率跟disk上做merge
，但是不需要每次写的时候都做。
onsite1. 中心思想就是不能用常用的double linked list + hashamp来搞定，原因是
concurrent的情况下必须锁整个linked list，这个throughput会非常差，解决办法是
延迟处理写linked list，有不少钟solution，但是最简单的一种是不用linked list，
maintain hashmap>，get的时候只更新
timestamp，set的时候才真正做从hashmap里面删除的操作。
onsite2.
主要就是每个station如果跟central断了需要各自记录各自的刷卡情况，然后等到连上
central之后再跑一个repair job把应该有的transaction都恢复出来
onsite3. 有一个帖子里面有讨论
http://www.mitbbs.com/article_t/JobHunting/32988733.html
【在 m******3 的大作中提到】
: Sumo Logic的，感觉这家题目都很难啊
: 2. 小三哥，但是也不黑。
: given a list of intervals，query if another interval is totally covered by
: the list of intervals。
: totally covered是指整个区间都被某些已有的区间 cover了。
: 比如如果有 list of intervals = 【（1， 4），（2，8）】
: [这个我的想法就是按照LC先做合并interval,然后检查，有更好的方法么？]
: given interval【3，6】就被完全cover了。
: 然后扩展到design a system来做这个事情，可以query，也可以insert interval，假
: 设query操作的频率远远大于insert操作，并且interval的数量非常非常多。
|
b*****n
发帖数: 618 | 130 1.这个题目主要是要减少读disk的次数和开销，首先按照file的size group一下，然后
在同group里面再找其他方法，这个我不确定，但是做md5被否决了，因为如果md5不存
下来就没啥用。我用的方法是每个file取开始的一段，比如128byte比较是不是有相同
的，相同的再分别group，group完了之后就没办法了，在同group里面的只能把文件全
读一遍比较。
onsite1.
这个版上讨论过多次了，就是不需要太精确，精确到秒，毫秒都行看memory需要多大，
如果是秒的话就是size为300的counter array，记录当前最早的timestamp作为head，
然后用current timestamp做tail，timestamp跟array index的关系是index =
timestamp%300.
如果最早的timestamp <= current timestamp - 300, 需要清除一部分。
onsite2.这个在提示下才做出来，block不是真的block，对面说可以用sleep()一个特
定的时间，那养的话就可以保存一个现在已经预支到什么时候生成的token的时间，然
后用这个时间跟current time比较决定sleep()多少。这样做只需要在更新预支时间的
时候加锁就可以了。
onsite3. 见另一个帖子
【在 m******3 的大作中提到】
: dropbox的，感觉这家也很难
: 1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
: 常大
: Onsite：
: 1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
: [这个应该是用circular window吧，concurrent怎么做呢？]
: 2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
: 果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
: 用最简单的方法实现
: 3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
|
|
|
b*****n
发帖数: 618 | 131 4.1 trie
4.2 inverted index，
5 取每两行，然后看一共有多少个index这两行对应位置的数都是1，假如有k个的话，
那么这两行能组成的满足条件的rectangle数量是k × （k - 1）/ 2，这样的话O(n^3
）就可以了。
6，7 见另一个帖子
the
【在 m******3 的大作中提到】
: uber的
: 4. boggle game，given a boggle board and a dictionary，find all words on the
: board，
: follow up，如果dictionay 不变但是board不停的变怎么优化
: follow up，如果board不变但是dictionary不停的变怎么优化
: 5. given a matrix only containing 1 or 0，find how many rectangles are 4个角
: 都是1
: 6. how to design a system to automatically detect hotspot on geo graph, a
: hotspot is an area such that 打车的request远多于available driver的数量
: 7. how to design a system to detect if dispatch algorithm has some bug，
|
b*****n
发帖数: 618 | 132 6.首先讨论qps多高，load多高，讨论结果是其实系统要求根本没那么高。。因为每首
歌假设4分钟，不吃不喝每天每个人最多也就听360首歌，一个周也就2520首，这个计算
放memory里面也基本上完全无压力。qps更是很低，根本不用做太复杂的design。。
其实还是kv store，HBase刚好比较适合记录user的一系列的action，因为每个cell有
timestamp做key。
想要速度快的话，可以加各层cache，用来buffer写操作和加快读操作。
最后讨论的点转移到其他东西上去了，比如这个东西用Java写会有什么问题，我答GC，
然后开始讨论各种GC，然后又扯到HBase如何failover，如何保证data consistency
7.貌似前面说过了。。
【在 m******3 的大作中提到】
: Facebook的这两个
: 6. system design - design facebook music system，只需要design service tier，
: 两个API
: get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
: listened music ids for a given user last week. 这个call在load页面的时候要进
: 行，所以对latency要求比较高。
: record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
: 需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
: 首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
: 7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
|
a******6
发帖数: 36 | 133 求问大牛，是不是应该是 dp[i] = i + min of all dp[i - k ^ 2] for k >= 1 && k
<= sqrt(i)啊？
另外，我不是特别明白题意。比如input是4，那结果是1^2+1^2+1^2+1^2呢还是2^2?
谢谢lz。
【在 b*****n 的大作中提到】
: dp[i] = 1 + min of all dp[i - k ^ 2] for k >= 1 && k <= sqrt(i)
|
a***n
发帖数: 423 | 134 恭喜楼主。真是心胸宽广的牛人啊，以后肯定会大有作为。 |
a******6
发帖数: 36 | 135 求问lz下面这道题，1） 如果不用list如何体现LRU？ 2）如何实现bi-dirctional
map，另外assume value和key都是unique的么？谢谢啦
【在 b*****n 的大作中提到】
: 6.首先讨论qps多高，load多高，讨论结果是其实系统要求根本没那么高。。因为每首
: 歌假设4分钟，不吃不喝每天每个人最多也就听360首歌，一个周也就2520首，这个计算
: 放memory里面也基本上完全无压力。qps更是很低，根本不用做太复杂的design。。
: 其实还是kv store，HBase刚好比较适合记录user的一系列的action，因为每个cell有
: timestamp做key。
: 想要速度快的话，可以加各层cache，用来buffer写操作和加快读操作。
: 最后讨论的点转移到其他东西上去了，比如这个东西用Java写会有什么问题，我答GC，
: 然后开始讨论各种GC，然后又扯到HBase如何failover，如何保证data consistency
: 7.貌似前面说过了。。
|
b*******y
发帖数: 2048 | 136 这个太牛了，
进来沾沾好运，
同MS毕业3年多，混的像屎一样 |
b*******y
发帖数: 2048 | 137 中午一起散步的兄弟。。。难道除了我们公司还有其他公司华人兄弟们每天中午散步阿
。。。
【在 i**d 的大作中提到】
: 恩，中午一起散步的兄弟。。。暗号：红烧肉，烤鸭 哈哈
|
b*******y
发帖数: 2048 | 138 太牛了，楼主还认真解答大家的问题。。。应该不是机器人。。。
前途无量，求交友。。。 |
f*******r
发帖数: 976 | 139 恭喜，都是好包袱！
关键字: 面经
发信站: BBS 未名空间站 (Sat Jun 13 17:27:31 2015, 美东)
前段时间骑驴找马终于告一段落，感觉本版的技术贴和面经贴帮助非常之大，也非常感
谢共享资源的各路大牛。希望提供一些信息和个人感受给还在找工的童鞋，有帮助最好
，但是毕竟本人资历尚浅，如果有不对的地方也请轻喷。
背景：
ms毕业不到两年
主要申请公司：
offer：facebook，google，uber，palantir，sumo logic，walmartlab，yahoo，
amazon，apple
reject：dropbox
主要几个包裹：
U： 145k base + 25k股 RSU
F： 150k base + 40k signon + 10%bonus + 260k美元 RSU
W： 165k base + 50k signon + 20%bonus + 35k美元 RSU每年（
这个略复杂，相当于每年35k美元RSU的refresh，但是每次refresh分四年给）
再上各个公司的面经和感受：
Yahoo：
最早面的公司，面的是Flurry Team，Yahoo去年收购的一家在城里的小公司，所以不一
定有代表性。因为re-org我两个月之后才拿到offer，中间还给我match到其他team几次
，Yahoo比较动荡，个人也不看好。
电面：
和director聊了有两个小时，无coding，问了很多之前project内容和hadoop相关的内
容。
最后讨论了一道design，如何设计distributed key-value store，因为他们主要用
HBase。
Programming Test:
Validate Soduko Solution，从文件读solution，尽量用production标准写程序。
Onsite：
五轮Onsite没有coding，全是问实际问题怎么解决和design。
1. 如何设计一个priorityqueue service，client可以submit job request然后server
按照priority执行
2. 需要一个key-value store with 1M qps，most read，1ms 99% latency，如果用
HBase的话会有什么问题，怎么解决
3. 给很多整数，如何用mapreduce找median，如果是很多float数，可以有一定的误差
，如何找
4. Programming Test的扩展，如果soduku matrix非常之大怎么做
然后还有一大堆针对hadoop的各种情况下怎么optimize的问题
onsite完了之后他们director说very positive，然后就开始re-org两个月。Flurry做
的东西其实挺有意思，mobile analytics platform #1，我感觉他们engineer人很nice
，水准也非常不错，可惜没缘分。
############################################################################
###########
Apple：
练手公司1，Apple可以同时面很多组，每个组有各自的recruiter。我把简历递了之后
陆续有10个组联系我，然后每个组基本上都是onsite之前两轮phone，一开始没经验联
系了4个组后来发现实在体力吃不消，光电面就8轮。最后3个组要onsite，这里我犯了
一个错误，告诉他们我在面其他的组，一旦他们知道你在面其他的组就不跟进了，打死
不回email。所以最终我只onsite了一个组。
电面：
1.给平面一堆点，把所有在同一条直线上的点group在一起，求出所有的group
2.一种encoding的方法，如果一个byte第一个bit是0，比如 00000000，那它自己表示
一个字符，如果一个byte第一个bit是1，比如 10000000，那它和它后面紧跟的byte表
示一个字符，现在给一个byte array，判断最后一个字符是一个byte还是两个byte组成。
3.parse message from byte stream，message format是前4个bytes组成的int值表示
message的长度L，然后后面连续的L个byte是message真正的内容，每个message都是这
样表示，需要一边读byte stream一边parse每个message
4. 两个table做join有哪几种方法，分别有哪些drawback
5. merge two sorted list
6. sqrt(double number, double epsilon)
7. auto completion implementation using trie
8. edit distance
9. Implement blockingqueue
10. how is a hive query transferred to mapreduce jobs
Onsite:
1. given a list of pairs, pair.first 表示parent, pair.second表示child,
reconstruct the tree, return the root node.
2. auto completion - design the service
3. design a service, accept stream of events, each event has a type and
timestamp, need to support the query of top k most frequent types in a query
specified [start, end] time range.
4. closest number to target in BST
5. validate soduku / solve soduku, and optimizations
6. 给一个json object，给一个wildcard path with ‘?’ as arbitrary name，比如
a.?.b 找到所有符合path的objects
Apple一般onsite的时候4轮tech interview，中午的时候将来的manager带着吃午饭。
如果tech这4轮面的好会有第5轮见到hiring manager，如果有这一轮基本说明offer没
啥问题了，这轮会是一堆behavior。如果第5轮也没啥问题会有第6轮见大boss，继续
behavior，会问之前做过的project有多牛叉，会吹就行。
同等级下Apple的offer远不如FG给力，而且match不上去，bonus也不会写在offer
letter里面，虽然据说每年的refresh有些组相当多，但是感觉整体上跟FG还是差距比
较大。而且组跟组工作强度差别也很大，有些组忙死有些组闲死，不过software的组一
般都还好，感觉大部分人精神状态还是不错的。
就engineer水平来看，我有遇到水平相当不错的面试官，但是整体水准远不如FG。
他们各个组做项目是完全分开的，基本没交流。做东西完全是product driven，不过
engineer一般需要fullstack，需要自己end to end维护一个product，这点对有些人可
能还比较有吸引力。
############################################################################
###########
Amazon：
练手公司2，我面的是marketing solution和ads相关的team。大公司周期很长，感觉
recruiter不是很上心。
电面：
三哥，但是感觉还行没黑。
1.用trie来解决求dictionary里面所有符合given prefix的word。然后又扩展到prefix
里面有wildcard的情况，然后继续讨论如果要design a system做这个事情怎么搞，需
要注意哪些问题。
Onsite：
居然没有遇到三哥，除了一轮老中外其他都是老白，每一轮开始都是至少15分钟的
behavior，而且每个人还能换着花样问不一样的问题，感觉大部分脑细胞都花在这些没
用的东西上面了，所以感觉很不爽。
1. OOD Restaurant Reservation System
2. Merge K Sorted List
3. K Sized Sliding Window Sum/Minimum Value
4. 给一个css file里面很多class，然后class name里面其实很多重复的，怎么
compress用尽量最小size的string来表示，这样传输的byte比较少。
5. shorten url system design
6. longest palindromic substring
7. robot moving from topleft to bottomright corner of a matrix，matrix里面有
些cell是障碍物不能通过，只能往下或者往右走，有多少种方法。
8. 之前做的项目，和我之前坑爹公司的architecture
相比起他们的behavior问题，我觉得亚麻的engineer水平相当一般，很多design
principle都不知道，可能因为他们内部都直接用aws很多细节都不需要考虑，也有可能
跟我面的组有关系，如果面的是aws会好些吧。
亚麻package跟其他几家比起来差距略大，所以也就没再继续谈。
############################################################################
###########
WalmartLab：
我面的是walmartlab里面仅存的几个不是三哥的组，通过靠谱的朋友内推。
面试题整体难度也还好，算法基本上都是常见题目，国人面试官都非常非常非常nice。
只说其中几轮比较有意思的吧
1.topological sort
2.design web crawler system，how to scale，what would be the bottle neck and
how to solve the problem
3. 如何用semaphore或者condition variable实现3个process p1, p2, p3，p2必须要
p1结束才能运行，p3必须要p2结束才能运行
4. bloom filter 如何implement，estimate false rate
5. what is the best design pattern do you think and why
他们onsite有一轮会是跟product manager聊天，就是瞎扯。一个小时我都在绞尽脑汁
找话题，应该是类似culture fit吧，看看你是不是比较容易融入team。
walmartlab是第一个给我比较decent offer的公司，cash给的很多，所以其实我很感激
，而且我面的组的work life balance极好，我见过的最好的没有之一，onsite居然有
两轮是video因为面试官WFH。平时干活也非常自由，没有OKR，没有deadline（是的你
没看错，啥都没有，performance完全老板说了算）。
不去walmartlab的原因是我觉得他们实在缺有经验的engineer，而且很多做的很多东西
都是实验性质的，没有明显的business impact，现阶段我还是比较想去一个大腿比较
多的地方抱一下。
############################################################################
###########
Sumo Logic：
一开始看到这家公司里面好多MIT毕业的人，而且听说他们bar很高，所以一开始也只是
想拿来做一下benchmark。他们基本上都用scala，如果懂一点scala效果会比较好但是
不懂对面试也完全没有影响。
他们的面试是先一轮phone，然后两次onsite，第一次onsite2轮，第二次onsite3轮，
第一次onsite过了才会有第二次onsite。第二次onsite每一轮会有两个面试官，每个面
试官都会出一道题目。
电面：
1. 两个binary tree，每个node存的值有两种可能，1或者0，把两个tree对应node做or
操作。
极为简单，扯了一下immutable data structure然后聊了一会之前做的东西就过了。
onsite 1：
1. 纯聊project和讨论他们现有的data ingestion架构，刚好他们最近想用Kafka所以
就这个话题聊了一个小时，最后没时间做题就结束了
2. 小三哥，但是也不黑。
given a list of intervals，query if another interval is totally covered by
the list of intervals。
totally covered是指整个区间都被某些已有的区间 cover了。
比如如果有 list of intervals = 【（1， 4），（2，8）】
given interval【3，6】就被完全cover了。
然后扩展到design a system来做这个事情，可以query，也可以insert interval，假
设query操作的频率远远大于insert操作，并且interval的数量非常非常多。
onsite 2：
1. 有意思的题目1，设计Bi-directional LRU cache data structure，既可以lookup
key to get value，也可以lookup value to get key，还支持set(key, value)操作，
后面又加了条件，concurrent的情况下，会有什么问题，如何改进，假如set这个操作
的频率远远小于get这个操作的频率，需要写代码实现。
2. robot from topleft to bottomright LC原题，无障碍和有障碍
3. given a list of sets，find all pair of sets having any intersection
4. 有意思的题目2，设计caltrain system，要实现caltrain上车下车刷卡扣钱整个功
能，assume每个station都跟一个central server相连，要处理如果有network
partition怎么办，eventually车费还是要charge到账户上，但是不能影响partition的
station正常运作。要处理某些人下车没刷卡怎么办，followup可以非常多
5. 有意思的题目3，仍然是设计一个cocurrent环境下的time leased cache，但是有些
区别，假如delete操作是一个daemon thread来做不用太多考虑，但是get(key)操作的
逻辑是如果key不在cache里面，需要一个非常expensive的操作把对应value load进来
，如何让这个load的操作对同一个key尽量少发生，需要写代码实现。
这家的题目我觉得非常有意思，engineer都超级nice，感觉我见过的人的能力都非常不
错，年轻一点的反应非常快，年长一点的经验非常丰富。整体上看三哥并不多，虽然
engineering vp是三哥。
这家很有诚意，最后给我的base跟walmartlab差不多，再加上很难估值的option。他们
觉得他们的bar很高，能过他们面试的人不多，所以一旦你过了他们面试，要做好被他
们的recruiter不停骚扰的准备。
有关这个公司，在其他帖子里面我提到过，虽然engineering vp是个三哥，但是感觉还
比较靠谱，不像某些三哥吹牛没有边际，对于整个公司发展的前景比较有数，business
model也很promising，最近刚刚拿到一笔80M的投资。
############################################################################
###########
Palantir：
号称湾区面试最难的公司。但是again我运气比较好没有碰到很难的题目。我觉得这家
公司有点吹的过大了，本身做的东西根本没有什么技术含量，里面都是一群没经验的
stanford小年轻，都是自我感觉超好。另外去这家公司要做好准备每周工作60hours。
估值150亿了还给option我也是醉了，能上市不？我的看法就是这家公司基本就是坑，
从哪个角度来讲都不值得去。
他们的onsite上午会有3轮，然后中午吃完饭后会有一个小时的demo（因为实在没什么
意思所以我差点睡着了），如果上午过了下午还会有1 - 2轮，一般下午会有一轮
system design，另一轮是见hiring manager，如果上午没过demo结束就可以回家了。
电面：
万年不变的电面题，给一个array，问有没有duplicate
follow up1，只要index的距离 < k并且value相同就算duplicate
follow up2，只要index的距离 < k并且value的绝对值差 < d 就算duplicate
follow up3，follow up2能不能有time complexity O(n)的解？
Onsite：
1. OOD astroid game，就是飞机打石块的游戏，石块可以任意形状可以移动，飞机撞
上就挂了，飞机可以发射子弹，子弹打上石块会把石块分成多个小石块按照不同方向和
速度移动。要写伪代码。
2. 每个person有一个list of intervals，表示busy的时间段，问最busy的一段时间分
别都是谁busy。
3. 一个描述起来不算简单的题目，但是算法不难，在版上看到过但是细节记不清了，
好像是给一堆stock profile然后算profit
4. 一个2d matrix，被分成好几个区域，区域之间都是value为0的cell，每一堆
connected的非0cell算是一个区域，问和最大的区域是哪个，要设计API，怎么用json
return结果。
5. system design又是 distributed key-value store，万年不变的题目，后来没啥好
聊的只好跟面试官扯他们的那个atlas，distributed transaction layer，没办法想拿
offer跪舔还是需要的。
基本上每个面试官都是一副老子很牛逼的样子，一问他们到底做了什么牛逼的东西马上
支支吾吾说不出个所以然。他们的offer也没诚意，150k的base + 25k signon +
55000option，没谈就直接拒掉了。
############################################################################
###########
Dropbox：
Dropbox的面试题都是从题库出的，但问题是他们的题库并不大。所以，我可以负责任
的说，你在这个版上找到的面经题目，你在面试过程中绝对能碰到。另外他们复杂的算
法题目并不多，但是大部分是跟concurrency有关的问题。
一般标配是 2轮电面 + 6轮onsite，6轮onsite中居然有两轮是behavior和culture fit
另外，他们面试的要求都是要写能run的code，要写完整的solution，不能写个主要
function就完事。
电面：
1. 给一堆file，如何比较有效率的把内容完全相同的file group到一起，file可能非
常大
2. 被人面过无数次的电话号码转成string，然后再word break那个题目
Onsite：
1. log_hit(), get_last_5mins_hits()那个题目，concurrent怎么搞
2. token bucket，假设每x秒提供一个token，然后外面可以申请任意数量的token，如
果token不够就block，要求concurrent情况下，不能有专门的thread产生token，怎样
用最简单的方法实现
3. web crawler，要分析可能的bottleneck，然后转化成concurrent运行的版本，写
runnable代码。
4. system desgin那一轮是两个三哥，轮流轰炸了一个小时，把我之前做的所有东西完
全推翻了，所以这一轮没结束我就知道肯定挂了。
############################################################################
###########
后面这三个公司是整个面试过程中给我感觉最好的三个公司。
Uber：
Uber的效率不是一般的牛叉。我从刚开始被Uber联系到最后拿到offer基本在一个周之
内搞定。面完了Uber之后真的有点心动，因为面我的人我觉得都很牛逼，人也都很超
nice，非常乐于提供很多关于Uber的信息，整个氛围非常积极向上。老板虽然是个三哥
但是也没有任何能吐槽的地方，他手下现在也基本都是老中。
电面：
一般电面会是hiring manager，除了问了一下之前做过什么之外只有一道题目：
OOD card deck，要现场deug，需要能运行
电面后一个小时通知我可以onsite
Onsite：
onsite一般是5轮，中间老板带着吃午饭
5轮中必然有一轮是只讨论之前做过的project，要做好准备，一定要对自己之前做的东
西特别熟
另外我面试过程中问了不少怎么设计一个系统解决Uber实际问题这种题目，很新颖很有
意思
1. 问了我不少关于storm的问题，比如storm怎么保证exact once/at least once
semantic，如何做timed window join，因为我简历上有相关的东西，然后让我用storm
来做一个比较简单的sliding window count。
2. big integer multiplication，要求现场运行代码。
3. longest increasing subarray，longest increasing subpath in a tree，path只
能从root到某个leaf
4. boggle game，given a boggle board and a dictionary，find all words on the
board，
follow up，如果dictionay 不变但是board不停的变怎么优化
follow up，如果board不变但是dictionary不停的变怎么优化
5. given a matrix only containing 1 or 0，find how many rectangles are 4个角
都是1
6. how to design a system to automatically detect hotspot on geo graph, a
hotspot is an area such that 打车的request远多于available driver的数量
7. how to design a system to detect if dispatch algorithm has some bug，
dispatch主要是收集所有打车request和available driver的信息然后决定哪个driver
哪个客人
Onsite过后两个小时通知我有offer了，如果onsite过后一两天之内没通知的话，基本
上说明你的waiting list上，要等排在你前面的人据掉offer才可以继续下一步。
############################################################################
###########
Facebook：
initial round我是直接去onsite的，但是根据其他朋友的经验似乎电面或者onsite影
响也根本不大，因为第一轮基本只要没有太大的纰漏都会过。
Onsite：
一共5轮，如果是4级的话会是3轮coding，1轮behavior和1轮system design。因为偏
infra, 所以我有3轮是三哥，当时已经做好挂的准备了。
1. move all 0s to right end of the array
2. decode way
3. binary tree inorder iterator
4. determine if there is a subarray sum to target number
5. convert integer to string，1000 to “one thousand”
6. system design - design facebook music system，只需要design service tier，
两个API
get_top_10_list_music_ids(int64 userid) - return top 10 most frequent
listened music ids for a given user last week. 这个call在load页面的时候要进
行，所以对latency要求比较高。
record(int64 userid, int64 musicid, int64 timestamp) - 每当user听一首歌，就
需要记录下来，这个可以asynch进行，需要eventually consistent，但不需要每听一
首歌马上就能反映到上一个call中。要做各种spec和resource的estimation。
7. 抄dropbox那个问题，get_hits_last_5mins(), record_hit()，但是后面又扯到
system design，如何thread safe，如果是districuted syste怎么搞，能想到几种方法
8. behavior那一轮基本上围绕着的主题是，你之前碰到什么难解决的问题，怎么解决
的，你学到了什么，production有过什么比较傻叉的bug，怎么避免的。你之前做项目
有没有cross team的，你怎么说服其他team听你的，等等。聊得过多导致最后没有时间
所有这一轮没有coding
我觉得我的运气很好，再次没有碰到很难的题目，尤其是算法。
############################################################################
###########
Google：
狗家如果真的想快的话还是可以的，我从开始被recruiter联系到offer也是一个周之内
搞定。
狗家和F家整个感觉都很好，面试官都很乐意帮忙，而且明显感觉到水平跟其他公司不
一样，技术功底非常扎实。
再次运气很好所以没有碰到很偏很难的题目，基本上就是水过了。其中几道比较有意思
的题目：
1. 一个正整数可以表示成其他几个正整数的平方和，给任何一个正整数，求最少的那
几个正整数，平方和是给定的数，比如14 = 1^2 + 2^2 + 3^2，如果给的数是14，应该
返回（1，2，3）
2. 给一个dictionary，然后可以support的query是，给一个string，返回在
dictionary里面包含给定string的所有character的最短的string
3. 如何设计google login system
4. web crawl的时候如何判断两个document是相同/相似的。
抱歉很多细节实在记不清了，表达能力也有限没办法在这个帖子里面说的很明白。如果
大家有问题我会尽我所能回答，谢谢。。
【在 b*****n 的大作中提到】
: 6.首先讨论qps多高，load多高，讨论结果是其实系统要求根本没那么高。。因为每首
: 歌假设4分钟，不吃不喝每天每个人最多也就听360首歌，一个周也就2520首，这个计算
: 放memory里面也基本上完全无压力。qps更是很低，根本不用做太复杂的design。。
: 其实还是kv store，HBase刚好比较适合记录user的一系列的action，因为每个cell有
: timestamp做key。
: 想要速度快的话，可以加各层cache，用来buffer写操作和加快读操作。
: 最后讨论的点转移到其他东西上去了，比如这个东西用Java写会有什么问题，我答GC，
: 然后开始讨论各种GC，然后又扯到HBase如何failover，如何保证data consistency
: 7.貌似前面说过了。。
|
l******l
发帖数: 209 | |
|
|
l******l
发帖数: 209 | |
