Microsoft Azure on site interview

Microsoft Azure on site interview

Round one: system design
Behavior Questions: Most challenge project
System design: 设计一个event calendar service，要求用户能够通过这个create event，并且系统能够识别时间冲突（比如event1 选了10：00 - 11:00，那event2就不同选这个时间）
写完之后具体问了nosql和sql的区别，然后让写了一下detect event time overlap的算法，有点像merge interval的变形
之后再问现在允许至多两个event重合，现在怎么修改算法（还是刚刚那个例子，event2现在可以选10:00 - 11:00了，但如果再来event3就不可以）


Round two: Coding
没有behavior questions，直接上题，约瑟夫环，我记得很久之前在leetcode上做过，但面完去找也没找到。题目可以上google搜一下，要求不能用数学公式。
给了double link-list的解，接着开始优化
1. 先讨论step = 0 和 step = 1的case
2. 讨论 step > total solider number的case
3. 然后问我还有没有优化的点。。。我想了一会才发现，如果solider是5，step是4，那其实clockwise走4步，和anti-clockwise走1步是一个效果。


Round three  Coding
Alian Dictionary，但我没做过，上来试了各种想法都被否了，最后在他的循循善诱下说是个可以拓扑排序，这时大概只有10分钟了，他说你赶紧吧，能写多少是多少。
紧赶慢赶，写完了construct graph的部分
留了两分钟，面试官说对我简历的某个项目挺感兴趣的，问了我一下

CloudKitchens On SIte Interview 面经

最近，受CloudKitchens的Recruiter邀请，去CloudKitchens在Los Angeles的总部进行了On Site面试。CloudKitchens是Uber的founder Travis Kalanick新开的startup，面试还是很新颖的。面试安排如下：

早上9:30到12:30: 在laptop上面现场写代码，解决一个实际问题。
中午12:30到1:00：一边吃lunch，一边和hiring manager 面试。就是一个lunch interview
下午1:00到2:00，一个小时的时间，有两个engineers会和你go through早上写的代码，并且做优化。
下午2:00到2:30: 两个面试的engineer会讨论是否要继续面试下去。
下午2:30到3:30：面试
下午3:30到4:30：面试
下午4:30到5:30：面试

先说说我的经历：我面试前觉得用他们提供的电脑，应该会比较好，因为毕竟是他们准备的实际问题，他们提供的电脑的编程环境应该是已经调试好了的。但后来发现，完全不是我想象的这样。

早上9:15am到达大楼，之后一个年轻的女孩领我到了会议室。给了我一个laptop，说让我不要打开，等两个engineer来了之后，再开始。9：30am，两个engineers来了，一个是老员工，一个是刚来不久的新员工。给我讲解了要解决的实际问题。当我打开他们提供的macbook后，发现这个macbook从来没有设置过编程环境，连gcc compiler都没有安装上。这两个engineers也不知道是这种情况，没办法，我只好开始下载，安装，设置编程环境。关键是这个实际问题，还需要用到json，我平时json用的少，弄了半个小时，都没有成功的让gcc link上json library。当时就感觉这个面试要挂了

再来说说这个实际问题：

建立一个production-level的system来模拟厨房中食品订单的fulfillment和delivery。给了一个json input file。 这个json input file包含所有用户的orders。order是这样定义的：
{
    {
        "name": “sandwich”,
        “temp”:  "hot",
        "shelf_life": 300,
         "decay_rate": 0.45
    }
}

Orders can be asynchronously read from 这个json file

shelf life是按秒来计算，温度temp是enum value: hot, cold, and frozen

厨房是以Poisson Distribution来接收orders，假设food可以立刻做出来，然后，把食物摆在shelf上面。

厨房里面有4种shelf：
1） hot shelf， 可以存放20个hot orders
2）cold shelf，可以存放20个cold orders
3）frozen shelf，可以存放20个frozen orders
4）overflow shelf，可以存放30个任意order

当每个hot，code，frozen，shelves放满后，可以放在overflow shelf。当overflow shelf 放满后，food order需要被removed，浪费掉。

就是要设计一个系统来实现上面所说的功能。系统输出的形式自己定义。

上午9：30到12：30这三个小时，就是写一个系统，下午1：00到2：00，这两个engineer再回来和我聊我的系统设计的怎么样。 比如并行的问题，performance的问题，multi-threading的问题，测试问题，等等。

中午的lunch interview是和一个hiring manager聊天，一边吃着sandwich，一边聊。 聊天的感觉是，当前员工还是挺辛苦的，工作压力大。所有的系统都要重新build。这个lunch interview主要目的是考察candidate是否对这个startup所做的事情感兴趣。

我的面试到下午2：30之后就结束了，早上面试我的两个engineers决定不再面试下去了。这也基本在我的预料当中，3个小时写一个小型系统，前面一个小时在，下载，安装编程环境。后面2个小时，实现了70%左右的功能。 没有完成全部的功能。在下午的1:00到2:00的面试中，并行问题，asynchronous等问题，回答的不是很好。 就这样就结束面试。

给以后面试的candidates的建议是：还是带自己的电脑来，这样比较好，至少可以省去前面的编程环境的调试时间。


在面试的过程中，也问了问他们的工作内容和公司整体发展的情况。在这样一个初创startup里面，工作内容基本都是纯engineering的工作，就是赶紧弄一个working的版本出来。他们现在的用户数还比较小，qps比较低，也不需要考虑scalability的问题。 不过，long term来说，还是会改善系统设计的。

公司的发展方向，我个人觉得还是不清晰的。没有感觉出来和DoorDash有啥本质的区别和优势。现在DoorDash也有了共享厨房。觉得他们做的和DoorDash差不多吧。

大家有啥问题，可以在下方留言，我会尽量解答。

Google Onsite Interview 面经

2020年初Google Onsite面经

第一轮：超级nice的国人姐姐。因为到的比较早，先去kitchen拿了点零食然后闲聊了半天G家的室内装潢（……）和简历上的经历。题目是给一个positive integer N，求N最少能由几个2^i组成。比如N=1的时候，1=2^0，那么N最少能被1个2^0组成。再比如N=7的时候，7=4+2+1=2^2+2^1+2^0，这个case中N最少被3个2^i组成。然后follow up是，可以同时使用正或负的2^i。同样的例子N=7，在这个情况下，7=8-1=2^3-2^0，这样最少只需要2个2^i就能组成N。

第二轮：台湾葛格，人也挺nice的。没有废话直接上题，就是lc的bomb enemy，不同的是bomb也能放在enemy所在的位置。第二题是给一个iterator: 2,3,1,5,1,8… 要求写一个iterator要能return 3,3,5,8… 

第三轮：印度姐，关于最近时间的问题，当前显示时间为 ab:cd，求下一个离当前时间最近的时间，并且只能用｛a,b,c,d｝这个集合里面的数字，数字可以重复使用，不一定要全部用到。输入输出都是字符串。
举个栗子
当前时间为“23:02”，下一个最近的时间为“23:03”
当前时间为“23:58”，下一个最近的时间为“22:55” （第二天的）
我用的方法很蠢，就是找出所有可能的组合，去掉那些不合法的（比如42:23这种），然后求出和当前时间的时间差，取最小的。

第四轮：白人小哥，看起来就智商很高的那种。题目是给一瓶药，里面100颗完整的药片，每天需要吃半颗。每天吃的方法是随机从瓶子里取一颗药，如果是整颗就吃半颗，剩下半颗扔回瓶子里；如果取出的是半颗，那就直接吃掉。第一小问是simulate这个过程，然后print每天瓶中剩下的整颗和半颗的数量，直到空瓶。第二问是，求整个simulation过程中，瓶中剩下1整颗，0半颗的概率。最后问了running time。

除了印度姐姐全程冷漠脸以外其他面试官都很热情友好一天下来感觉面试总体难度还行，并没有某些面经那么难（面之前看别人的面经真是吓得不轻……） 接下来默默等结果吧

[转载 from mitbbs] Pinterest Interview Questions

发信人: sleeper7 (海景别墅), 信区: JobHunting
标  题: 分享一个图钉面筋
发信站: BBS 未名空间站 (Wed Apr  6 15:33:20 2016, 美东)

图钉公司 thumbtack
电话： 
1. Evaluate Reverse Polish Notation
2. constant space get median and mean, input stream, range [0, 10000), 用个
array[10000]就行了
Onsite:
1. design twitter search，面试官google出来的牛人老中，我虽然自己就做是
inverted index的，但答得还不不算太好。
2. 算search的TF/IDF, 题不难但是挺繁琐，search multiple strings, 返回一个总分
数，通过计算TF和IDF。我解释花了很多时间，白板字写得太烂了，最后还有点尾巴没
写完，就说了一下思路，也是老中面试官。
3. search 一个dict中所有前缀为一个string的word。Trie实现，laptop上跑过才行。
4. binary tree的serialization and deserialization. laptop上要能跑过才行。
5. 两轮跟manager, founder吹牛逼，我直接问了founder什么时候上市，founder大概
意思是反正不缺钱，不着急上市，5年内不会吧。
整体感觉里面人很牛，50个工程师撑出超过1B的融资，大部分都是FLG出来的。面试还
是很挑的，我虽然题都做出来了，还不是不成。

[转载 from mitbbs] 骑马找独角兽的过程

发信人: geniusxsy (小尾羊), 信区: JobHunting
标  题: [bssd]糖一下骑马找独角兽的过程
发信站: BBS 未名空间站 (Sun Feb  7 04:28:51 2016, 美东)

干货不多，大家有兴趣打发时间的话就看看吧。这贴也许对fresh grad没啥意义吧，对
experienced或许更有用些。

＊＊＊＊＊＊＊ 我是小广告的分割线 ＊＊＊＊＊＊＊＊＊＊
帮ld求好心朋友帮忙内推下三番或者中半岛的轻松养老型的马工职位，ld在某软某办公
软件里呆了若干年，现在才发现没有积累到什么流行的技术，现在想找工作背景上比较
吃亏。不过ld底子和学习能力都很好的。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

背景是在西雅图地区的G干了五年多主要做backend。最近一两年前，身边朋友纷纷跳槽
，现在比较后悔的就是，早知道两年前刚拿到卡就该挪一挪，拖到现在算有点晚了。另
外一方面，在G干的活，现在也越来越提不起兴趣。朋友的怂恿和激励下，去年10月终
于下决心要跳了。
==> take away: 要跳趁早，时机不等人。

当时也没想要跳湾区，差不多就是一心想去打车公司的西雅图分店。其实去年夏天就有
些蠢蠢欲动了，刷了几道题后懒了又不了了之。10月份开始认真刷lc，刷的也不快，到
12月才勉强刷一遍。后来回想，浪费很多时间，其实各个种类挑着做50~100道应该就差
不多了。然后花了很多时间精力去复习系统相关的知识。G家自己的用过的infra复习下
，spanner没用过，正好跟新project沾点边就看了个大概。有些东西像chubby, pubsub
用过但是内部完全不懂，趁这个机会也翻翻人家的design doc有点大致的了解。当然最
后我觉得也没有真正派上太大的用，不过做为知识积淀也挺好。然后就是市面上的技术
我是完全没接触过，起初还很担心，不过学了一圈下来也觉得没啥高大上的，大多能在
G里面找到类似的，而且比起G做的更简化。这些花的时候不必刷题少，而且design doc
/tech report/paper这些读起来可没有做题那么有趣。
==> take away: experienced hire，刷题到一定程度就够了，其他的知识积淀还是更
重要。

废话一堆之后，来聊聊面试经历吧。如果你是来找算法题，可能要失望了。忘了有没有
签nda，不过遇上很多国人interviewer，慎重起见我尽量模糊化具体的面试题。其实我
说了也没用，真的，更重要的东西其实是在交流上。

12月朋友催我说打车公司又要融了以后pay的越来越少要来赶快啊，我总觉得没准备充
分犹豫了一阵，月底才鼓起勇气让朋友递了简历。对拼趣一直也挺感兴趣，也让朋友帮
递了，不过说实话，当时也就是想试试而已。然后顺手找人帮投了个脸书家，想拿来练
手。听说facebook考刷题比较多，我自以为擅长做题。加上我背景里面social graph, 
infra, product都沾点边，去面之前有种offer手到擒来的感觉。结果就悲剧了，怎么
说呢，也不算是被黑，发挥的也不好，有些很弱的失误回家路上就意识到了。算法题基
本上都是lc上的，有一道是hard但是那种非常经典大家都会做的，其他都是medium水平
的题，一共涉及了binary tree, stack, backtracking, prefix tree这些知识点。系
统题是让设计一个code search系统，基本上就是先装模作样分析估算下，然后画画大
的框架，反正差不多就是凭着经验和感觉走，然后接下来就是interviewer提问，对某
些component或者某些具体的情况zoom in进去讨论。虽然search我没做过，indexing系
统还是稍微接触过的，但是时间久了忘了不少，回家后又正好补了下知识。
==> take away: 面最心仪的公司前练练手也很有必要。

等脸书结果期间面了两轮u的店面，两轮都是很nice的中国人，跟第一位大哥中文聊天
也聊得非常愉快，coding题目也不难，用queue就能解决，大概也是放水吧。第二位系
统设计也是国人，问的google map，当时也没怎么准备过geospatial方面的话题，我觉
得磕磕碰碰的，结果还是承蒙面试官放水给过了。P家店面又是中国人，运气很好，问
了中等难度的lc题，就给水过了。不过有意思的是，这两家的coding都是online写完编
译调试，像我这样经常犯些typo或者弱智失误的，调试能力就可以弥补一些粗心，啪啪
啪的很快改完跑通，大概也给interviewer留下确实能干活的印象吧。不过坏处是如果
一两分钟没调出来，压力瞬间爆棚，只能扛着了。
==> take away: 其实大部分国人还是很nice的，遇上是缘分和运气！

这个时候fb悲剧的消息到了，感觉信心很受挫，情绪比较低落，本来觉得十拿九稳的事
情都黄了。其实现在想想悲剧是好事，让我带着卑微的心态努力尽力的准备之后的面试。

打车公司的onsite是在三番，虽然我申的职位是在西雅图。第一轮是老美mgr，名义是
考behavior，其实就是聊天，没有什么奇怪的问题。我准备的也比较充分，比较放松，
吹吹自己做项目的经历，侃侃对他家美好前景的向往，大家聊的也很愉快。第二轮是设
计题，他家的几道经典设计题目之一，设计netflix。还是先需求功能分析，然后画大
框架结构，然后主要问了下，serve media file怎么做到high available, high 
throughput，这方面其实不太懂，这个时候就只有借助知识储备开始瞎扯，一会儿瞎扯
些分布文件系统的东西，一会儿又瞎扯些backup requests，parallel read等方案，然
后上面的caching层再扯几句。接着又继续问了recommendation系统，时间不多，只能
大致提了下user-based/item-base CF这些。其实几年前粗略的看过一些netflix做推荐
的资料，马马虎虎应付一下还凑合。总的感觉还是聊的比较愉快，交流上基本上还是比
较合拍。接下来一轮，我现在还有点摸不着头脑的感觉，很open的problem solving，
说是design但又不是system design，大概就是主题公园排队时提供fast track，比如
，交5块钱，告诉你一个小时后回来，有点像scheduling系统。最后还让写code简单模
拟一下。我稀里糊涂的都忘了怎么答的，感觉答的如何心里很没谱，最后居然也还是给
过了，也许是我东扯西扯一堆，擦着边击中了面试官心里想听的点子上？接下来一轮是
coding，简单的有点莫名其妙，其实后来听了不少别人的面经，U家问简单coding题似
乎是很正常的！不过然后不停的followup，如果这个是正式的code，unit test你怎么
写，让你自己做code review，有哪些你会改的，怎么refactor？感觉是在考察实际工
作中写码的能力，其实也make sense，毕竟工作里面是没有机会写太fancy的算法。不
过我觉得这样面，有工作经验的人写码多的人，尤其是从像g这样code review严的地方
出来的，应该都能pass才对。最后一个人又是聊天，大概聊了一半时间后，顺带着引出
一个系统设计问题，也是经典的高频题，就是让设计他家的打车系统里面的一个
feature，轻松搞定，走人。

总的来说，一大半时间感觉都是聊天，扯，吹牛。他家也特别看重culture fit，就是
你要有passion，要有ownership，做事快，take risk。我觉得这些都是靠聊天里面慢
慢透露出来的信息，不是说简单直接了当的问。当然了，认真准备culture fit我觉得
是非常有必要的，其实技术上的水平和背景经历，面试之前基本上就是定下来了的，而
culture fit是可以通过认真准备更充分的体现自己的fit。对了，每个interviewer必
问一次为什么想来U家，我都快能背下我的答案了，最后一个人问的时候，我就明给他
说， 前面问过很多次了，I’ll try to answer this in a different way，然后就即
兴了。
==> take away: 面试中交流聊天非常重要，我觉得不亚于做题写码的重要性。

一个星期后就是拼趣的面试。这一个星期内主要的功夫是花时间用他家的产品，做功课
，产品功能，business model，并且想想哪些是做的很好的，哪些地方可以提高怎么提
高。然后拼趣家的四点文化，认真想下交谈中怎么结合自己的经历能体现出来，对于有
经验的人，我想这些下功夫都是能做好的。虽然我准备了这些，但是最后其实很多准备
的东西都没有机会用上，不过至少还是让我有足够的信心去和面试官交流。拼趣的中国
人非常多，更难得的是，中国人都很抱团很友善，有三轮都是中国人面试官。因为准备
加入拼趣，面试题就不详细写了。
==> take away: 有针对性准备充分，也许会胜过广撒网批发面

打车公司最先给offer的，但是包裹一开始压的非常低，base跟现在差不多持平还略低
一点，只有$43w股票，基本上包裹就是跟现在持平，很失望。直到我有了拼趣的offer
，才追上来，谈到68w也谈不动了。

拼趣很快给了口头offer但是各种原因数字拖了一周才出来，base还不错比现在高，但
考虑到州稅。。。股票最后给涨到1个米，整个过程非常爽快，我也很开心。我知道有
牛人能要到更大的包裹，不过我想自己满意了就好。朋友说他家每年给的refresher也
比较给力，想起来纸面上的数字还是很吸引人。当然，如果没上市，就是一堆废纸。这
次也是我第一次真正经历negotiation，最后效果也还满意，也从朋友那里学习了不少
讨工钱的经验，如果有人有兴趣可以私信我，或者下次有空写写。

最后选了P，钱给的满意是比较小的一个因素，其实U给的也算还不错了。其他很多个人
的考虑，这里就不多说了。至于公司前景的比较上，不用说U的吸引力非常大上市几乎
是必定的，P的风险相比更大，但是潜力也不错，团队也很强，我觉得拼趣的
monetization做的不错，感到有比较强的信心。有机缘跟很多p家的国人接触过，觉得
他家中国人多而且友善团结融洽，这点很喜欢。

[转载 from mitbbs] Google Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: 狗家面经
发信站: BBS 未名空间站 (Fri Apr 15 01:20:25 2016, 美东)

电面太容易 ， 忘了

1. Number of Islands
2. Find Median from Data Stream, 举例描述每一步
3. Compute Avg for Data Stream, 小心overflow
4. MapReduce求稀疏矩阵乘法
5. Binary Search Tree Iterator, 举例描述每一步
6. Longest Alternating Subsequence

[转载 from mitbbs] Palantir Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: Palantir面经
发信站: BBS 未名空间站 (Fri Apr 15 01:44:22 2016, 美东)

电面: 
先给你看一下棋牌游戏介绍 https://en.wikipedia.org/wiki/Connect_Four

然后题目关系不大. 实现一个函数能解码以下被run length encoding的2D char数组 

|_|_|_|_|_|_|r|
|_|_|r|_|_|_|_|
|b|r|b|r|b|r|_|
|b|b|b|r|r|b|_|
|b|r|r|b|b|r|_|
|r|b|b|r|r|r|b|

   * 'r' 代表红棋
   * 'b' 代表黑棋
   * '_' to 代表空
例如以上例子编码是 6_r2_4_brbrbr_3b2rb_b2r2br_r2b3rb

函数返回char[6][7]

Onsite: 
1. 面试官突然拿出一副牌。说有N个人, 每人分一手牌.  按以下规则玩牌
   a) 每人出一张牌放桌面, 比大小, 不比花色, 没有joker
       * 其中只有一个人有最大牌，此人赢走桌面上的牌
       * 其中k人有最大牌, 此k人每人拿走三张手牌. k个人继续a)直到最后有一个赢
家出现,  此人赢走桌面上的牌
       * 如果在要出1张或3张牌的时候，手上没牌了, 此人彻底输了

   写一个函数, 输入每个玩家的手牌, 求最后的赢家

2. 设计一个类似JIRA的系统
3. 设计一个监控系统, 定时监控远端服务器的参数，远端服务器挂了能报警. 多线程
   
P家吃完午饭，放一小时demo, 如果下午没面, 说明已跪.

已跪

[转载 from mitbbs] Amazon Interview Questions

发信人: lusty (lusty), 信区: JobHunting
标  题: 亚麻面经
发信站: BBS 未名空间站 (Fri Apr 15 02:12:28 2016, 美东)

电面: 
geeksforgeeks: Sort a nearly sorted (or K sorted) array
亚麻是唯一见过电面面culture的公司, customer obsession, ownership
电面后culture跪了, 刷题pass. 

onsite: 
1. design rate limiter
2. 实现一函数， 输入为两字符串，其中任意一串为另一串的prefix返回true, 否则
false
3. 实现一数据结构, 支持以下两操作

void addURL(String url);
String getKthMostFrequentURL(int k);

4.  给一文本文件, 每行一整数. 写一函数，传入文件名, 输出K largetst numbers.
5. culture, culture, culture

[转载 from mitbbs] Thumbtack On Site Interview

发信人: lusty (lusty), 信区: JobHunting
标  题: Thumbtack面经
发信站: BBS 未名空间站 (Fri Apr 15 20:09:08 2016, 美东)

已经很久远了,  记不大清了

1. 给一个int流, 取值在0-1000, 求running中位数
2. Trie树,  通配符匹配
3. Design Facebook 图片相关的, 包含CDN, haystack
4. 倒排索引

[转载 from mitbbs] Airbnb On Site Interview

发信人: lusty (lusty), 信区: JobHunting
标  题: Airbnb面经
发信站: BBS 未名空间站 (Fri Apr 15 23:30:08 2016, 美东)

电面, 先看符漫画 http://xkcd.com/287/
然后你的目的是实现一个这样的函数, 根据菜单回答问题: 我怎么点餐能恰好花掉X刀?
例如:  从菜单上怎么点餐能恰好花掉15.05刀?

陷阱1: 老中点餐一个菜不会点多次, 这个可以点多次
陷阱2: 价格不能用float,否则答案会因为floato精度问题少一组.

楼主因第2个陷阱而跪, 虽然能编译，能跑, 但少了一组答案

[转载 from mitbbs] Uber On Site Interview

发信人: lusty (lusty), 信区: JobHunting
标  题: Uber 面经
发信站: BBS 未名空间站 (Fri Apr 15 01:33:31 2016, 美东)

Uber: 

1. Merge Two Sorted Lists
2. Sparse Matrix Multiplication
3. 给一个n列类似俄罗期方块的盘, 往下掉方块. 方块定义如下: 
class Block {
        int left;
        int right;
        int height;
}
其中 0<= left < right < n ,  像俄罗斯方块一样会叠起来. 求最高高度

class FallingBlock {
public FallingBlock(int width);
public void fallBlock(Block block);
public int getMaxHeight();
}
4. design whatsapp

[转载 from mitbbs] Cloudera面经

发信人: lusty (lusty), 信区: JobHunting
标  题: Cloudera面经
发信站: BBS 未名空间站 (Fri Apr 22 20:14:49 2016, 美东)

电面: 
1. 实现一个histogram, 能inc/get每种metric的counter.     
void incCounter(String metric)
int getCounter(String metric)
2. followup: 修改以上histogram应付并发读写


onsite: 
1. how to create a generic singleton class
2. 求integer流中最近k条数据的avg

public class KAvg {
    public KAvg(int k );

    public void add(int x);
   
    public int getKAvg();
}

followup: 并发add/getAvg

3. 用AtomicLong或compareAndSwap原语实现spin_lock, spin_semaphore, reentrant_
spin_lock
描述spin_lock的self deadlock情况

4. design whatsapp

5. behavior/ team conflict/strength/weakpoint

6. go through background

[转载 from mitbbs] Walmartlabs面经

发信人: lusty (lusty), 信区: JobHunting
标  题: Walmartlabs面经
发信站: BBS 未名空间站 (Fri Apr 22 20:00:06 2016, 美东)

电面， Environment Variable Resolution

给一堆环境变量定义
        A={B}_{C} //{B} is similar to $B
        B={D}
        C={D}
        D=x
这里的环境变量用{}括起来, 在linux是用$或${}
写程序把以上等式解析成
        A=x_x
        B=x
        C=x
        D=x


Onsite:

1.  给几个TB的文本文件， 文件每一行是一个登录时间timestamp. 用MapReduce求前
后登录时间差最大的n条记录
2. 要你讲各种常用design patterns. Singleton模式如何pass parameter
3. Singleton模式如何应付concurrency
4. go through background
5. behavior

[转载 from mitbbs] FB On Site Interview Questions 面经

发信人: lusty (lusty), 信区: JobHunting
标  题: FB 面经
发信站: BBS 未名空间站 (Tue May 10 15:36:42 2016, 美东)


Jedi: 
  go through背景
  light coding: clone a graph

Ninjia:
　给一个task序列ABBABBC, 和相同task的最小interval. 例如interval=3, 则BB运行
时间为5. 写一个函数输入task序列和interval, 输出运行时间。
　followup: 写一个调度函数，输入task序列和interval，输出task最优执行序列

Pirate: 
  设计一个大型在线多人视频系统，支持FB的scale

NinJia:
  Best Time to Buy and Sell Stock 
  followup: 返回买入和卖出时间的Index
  Search in Rotated Sorted Array

Pirate:
  设计一个系统。输入为FB用户的status流, 每个status的组成为多个tags, 用户可通
过　tag1 and tag2 or tag3之类的查询语句, 查出满足这些条件的status list.

Pirate: 
  设计一个google maps

Ninjia:
  leetcode Move Zeros变种
  leetcode Subsets变种

Pirate: 
  设计shortURL 系统

【转载 From MITBBS】Facebook On Site 面经

1. 给你一些平面的点（坐标是整数），求能够成正方形的数目。
我想了想这题大概可以这么做：把每两个点之间的距离用hashmap存下来，key是
distance, values是arraylist of point pairs， 比如（p1, p2), (p3,p4)之间距离
都是6, 把他们都放到map.get(6)的list里面。这样一共要查（n,2)pairs, time也就是
(n^2). 下一步对于每一个distance, 查看对应的list size是不是大于4（至少有4个
pairs之间距离相同）。然后对于每一个list再进一步确定有没有正方形，比如
(p1,p2), (p1,p3), (p1,p4), (p2, p3), (p2, p4), (p3, p4) 都在list里，就可以确
认这四个点可以组成正方形。。。。确认的时候可以再建一个hashmap, map p1 to (p2
, p3, p4), p2 to (p3, p4), 然后找需要的pair是不是都在map里。。。就是好麻烦这
个solution, 不知有没有简单点的解法？


2. 设计json的data structure实现json encoding 要求one line version先不考虑
indent，follow up考虑indent和括号
来自这里
http://www.mitbbs.com/article_t/JobHunting/32883371.html
没有思路，不知怎么start， 还请大家帮忙。。。

[From MITBBS] Facebook and Google Interview Questions

Facebook:
Phone:
Input: Given a matrix of 0, there are some areas populated with 1, 2, 3s.
Output: Map<int, numOfRegions>

Onsite:
Round 1: cultural, project deep dive, things that can be done better
Round 2: Calculator, implement a function to output the current display 
based on the inputs that is already typed.
Round 3: Word Ladder II in Leetcode
Round 4: Design facebook event notification system (push on mobile app, and 
pull on web), discuss storage/api, how to generate events, prefer to use 
periodical job to scan incoming events and generate messages accordingly
Round 5: Culture fit, strength, how to deal with disputes among colleagues, 
reverse linked list in pairs

Google:
1. Given a robot and a maze, the robot supports these apis:
Turn left, move forward, checkIsExit
Write a program to make it move to the exit

2. Design Youtube access control system, storage, scales

3. Suppose there are k threads, write a multi-thread program to make them 
come to deadlock, I use semaphore at first, then was asked to implement it 
with countDownLatch

4. RunLength encoding, discuss various ways to minimize the encoded string 
under different constraints

5. Design a system to generate Ids for distributed DBs, discuss various 
Zookeeper patterns (leader elections etc).
For a given number, how to return minimum number of squares that sums up to 
this number

【转载 From MITBBS】FB 面经

一个月以前面的了，没什么营养，还是发给大家看看吧, 希望对大家有帮助，已经跪了。

电面： 中国大叔面的，大叔很nice，遇到我写有bug的时候都会着急的提醒我，题也很
简单。

1： 给n个点找出离远点最近的k个， k<<n。
2: 给三个 api isSmall()  isMid() isBig() 给一个array 排序，只要不被迷惑， 知
道其实是lc 上 sort color的变种就很简单了。

On Site：

1： 聊自己的research，白人manager，说自己以前是faculty，人非常nice。气场也比
较合， 我讲完之后还说把email给我，说我面试后有问题可以问他，然后问了个 two 
sum。

2：亚洲小哥，也很nice，第一道题是 Lc 上的String Multiplication。 然后出了一
个打印 tree路径的题，后来问我做过没有，只能说做过类似的，后来换了一道 的 
decode way 变形，要把所有的可能的组合都打印出来，写了一个recursion。

中午和内推我的本版汤唯姐姐吃饭，在此谢谢汤唯姐姐，大牛非常nice，大家内推可以
去找他。吃饭的时候还说，上午过了最难的两轮，下午都是国人面试官，应该简单点。

3：国人面试官，貌似气场不太合，我写code的时候尽量解释，可能人家
觉得我也做不出来，无聊的看了很久手机。出了这个题
http://www.mitbbs.com/article_t/JobHunting/32906379.html

class IntFileIterator {
  boolean hasNext();
  int next();
}

class{
  public boolean isDistanceZeroOrOne(IntFileIterator a, IntFileIterator b)；

}
// return if the distance between a and b is at most 1.. 
// Distance: minimum number of modifications to make a=b
// Modification:
//   1. change an int in a
//   2. insert an int to a
//   3. remove an int from a

都怪自己事先没把本版的题都做一遍，然后就跪在这道题上了，巧的是貌似帖子的一个
妹子也是这个国人同学面的，大家记得一定把这道题做一下。

4. 国人面试官面出的 design：Shorten Url。面试官人非常nice，可是自己答的一般
，在此谢谢他。

白人经理很nice，果然当天就写了个email给我，说很enjoy 和我的talk。hr拖了很久,
上周通知，不出意料的跪了。

【转载 From MITBBS】surveymonkey面经

周二去palo alto总部onsite，周五被告知不move on，分享一下面经希望对大火有用。

店面：华人大哥，主要聊了做过的project，聊得很合拍，最后问了道很简单的题目
given a string consisting of a set of characters, return a new string of the
original characters sorted in alphabet order. e.g given 'abcabcabc' return 
'aaabbbccc'


onsite总的来说面试不难，去之前recruiter说有五轮，但当天实际面了六轮，分别来
自两个组（collect team and analysis team）

1. 组1阿三HM，刚进来一看好像还很friendly的样子，先介绍了他的组和公司的情况，
然后让我介绍自己的工作经历。我说完这问大哥点点头，然后掏出了一页纸，上面都是
问题。。。。都是很detail的问题，比如http post和put有什么区别，这个真被问到了
，就答了他们都可以用来send request to update/create data，答不出区别。。。还
有被问hadoop的archicture以及hive和pig latin有什么区别，这个可能和我简历有关
，之前工作中用过hive，pig是在学校时上课用过，实际工作没用过，磕磕碰碰说了点
区别，貌似他不太满意，但关键hive是之前工作用的，两年多了，面的职位也和hadoop
这些完全不相关。到了这里我就感觉很不好了。也算我没有准备好吧。。。最后没做题
目。

2. 组2的白人senior engineer/tech lead, 其实他刚离开组2去组建一个新的team. 还
是照例聊他们team和我的background，还有一些backend相关的知识点，然后让用queue
实现stack

3. 组2白女，fullstack or frontend engineer，不记得了。基本都是聊天，从和他们
聊还是可以看得出来这公司的culture不错，貌似很多人都很喜欢公司，公司鼓励大家
不要加班，而且说他们周四很多人都work from home。但是聊到快完了她才说要不我问
你一道问题吧，让顺时针90度旋转nxn的matrix，我说用四个变量确定当前的上下row和
左右column，然后一层层旋转，写了旋转当前上下行的代码。她说ok

4. 组1三姐和new hire白男（shadow）， 很常规的先过简历再做题，leetcode 原题
Search a 2D Matrix，我给了O(M*N)，O(M+N)和O(logM*N)三种思路和coding

5. 管组1的三哥director。可见三哥三姐很喜欢扎堆，组1都是三哥三姐。但好的一点
是这三位的英语都还挺好懂的，特别是三姐和这位director，感觉基本没有印度口音。
这位哥们说他加入猴子公司才三年，就从tech lead／senior升到director了，下面管
着三个team。聊了聊公司的engineering现状和当前的challenge，他们现在已经摆脱了
startup刚开始的艰难时期，现在的主要问题是scale up带来的挑战（engineering，
management）。因为他没有带我的简历，所以就只让我说说工作经验，然后把现在工作
的architecture／workflow给他讲讲。最后他说组1在找senior，我就说我可能不还不
够senior，他到是很坦率的说他也觉得我可能fit他们的要求，但其他组如果合适会考
虑，这是他们招人的policy。

6. 管组2的director，非常热情的白人大叔，先问了我的experience，说完我的
background真好符合他的组，那一瞬间我都感觉可能有offer了。。。。然后他讲了一
下他们的architecture和他多么喜欢serveymonkey，公司提供了很多opportunity，比
如那个白男本来是他的team的，他们都很喜欢他，他离开他很心疼，但也了解白男想去
做新的东西，这对他对公司都是好事。看得出来人挺nice。

说实话，除了第一轮，后面我感觉都挺好的，本来还以为能有offer，昨天被据了还是
有点小难过。不过想想自己确实有些准备不足，也不能怪别人，只能move on了。