电面1-2轮，一般就是coding
onsite一般是4轮，2轮coding，1轮design，1轮behavior+coding
校招的话，那轮design也变成coding了
https://github.com/WeizhengZhou/leetcode3/blob/master/fb.txt
和B
class A {
public void foo (A a) {
...
}
}
class B extends A {
public void foo (B b) {
...
}
}
问这么写会不会有问题
2. 关于Database的题，假如你执行
select * from employee
employee是一个table
但是返回错误说，这个table不存在什么的，但是现在已知存在这个table,问你可能是
什么原因。
完全没有思路，就说我也不知道。。。
3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效的词，字典是给定的。
http://www.weiming.info/zhuti/JobHunting/33055253/
http://www.bbsdigest.com/thread/index?bid=13&tid=33055253
比如，
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.
但是如果，这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。
然后问你怎么选每个位置的candidates，最终可以让能组成的词最多。
没有什么特别好的思路，问是不是brutal search，还有更好的方法吗？答：你如果要
brutal search的话，你估算一下时间。
我就开始算时间，发现很长，然后面试官说，那你想办法优化。。。但是因为算brual
search的时间算了太长时间了，就没什么时间优化了。。。
其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
，最后的时间提问。
1. 一来就是一道简单题，翻转链表
// Reverse a Singly Linked List
// Example Input: A -> B -> C
// Example Output: C -> B -> A
他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部
分，所以很快就写完了。
2.第二题直接copy 题目，感觉跟leetcode上面的interval那题很相似，简单一点点。
// Given a array of pairs where each pair contains the start and end time of
a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False
同样的思路+复杂度。 同样是变种题，还变简单了，很快写完。（主要是考比较器的
override吧）
3. follow up第二题
// determine the minimum number of meeting rooms needed to hold all the
meetings.
// Input array(pair(1, 4), pair(2,3), pair(3,4), pair(4,5))
// Output: 2
我看表还剩下10分钟，然后想了3min钟，面试官就说没时间了，要不你说说思路。然后
说了一下思路，面试官说OK。让我提问题。瞎问了一个问题。面试官还特别详细的解答
了。他说超了一点时，不过没关系。 然后互相感谢了一下，客套了一下。就再见了。
第二天HR说下一轮Onsite了。
Clone graph
onsite
1. 一个manager 先聊behavior， 然后做了一个小题
isOneEditDistance 判断两个string是不是只差一个编辑距离。
2. 3Sum 变体，每个数字可以重复用。
3. System design设计手机上读取photo feeds的app。
功能： 读取好友的最近图片
阅览好友的相册
要求： 满足功能的同时减少对手机的能耗。
4. (1) 一维度向量相乘。每个向量很长，billion个数字。
(2) 多线程 reader 跟 writer 的经典问题。
加面
1. 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
2. search in rotated sorted array LC原题。
decode ways LC原题。
1， valid palindrome, leetcode 原题，但是不能修改String, 所以就不能用s.
toLowerCase(), 当时就急了，因为不知道Character的 toLowerCase的method是什么，
她说写sudo-code就可以了。很快做出来了，然后写test cases
2, Binary Search的变型，Git Bisect, 从某一个版本开始，引入了一个bug, 然后让
我找出引入这个bug的第一个文件。binary search之
Given a list of words，find all palindrome pairs(two words that can build a
palindrome). For example, "ddcba" and "abc"are palindrome pairs, since they
can build "abcddcba" which is palindrome.
Follow up，可以组合任意个单词，怎么找到最长的可能的palindrome.
面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
google安排了两轮电话面试
第一轮是个三姐，LC上的insert interval类似的题，之后各种讨论follow up
第二轮是个美国人，问题是给你一个sorted的长度为N的数组，求所有数组内出现次数
超过N/4次的数字（popular numbers）
我写出了O（N） time O（1）Space，之后面试官问我有没有更好的解法了，我说我想
不出来了
接着问了一道followup， 现在给你一个time complextity O（1）的function， 叫做
findCandidates（A）， return的结果是一个长度为3的数组，popular numbers是这个
数组的一个子集，问如果用这个function，能否改进time complexity。
这道题我写的时候出了个index out of range 的bug，被面试官指出，马上改过来。
最后讨论了如何test我写的这个function
第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
inplace，线性复杂度。这一题做的很顺利。面试官说good enough
我估计得至少两倍空间存在，最惨的情况是字符串上全是a，然后又要求inplace的话。。
我的想法是把字符串先复制到数组的后面，然后再挨个拷回前面
我的做法跟你差不多。区别是先把字符从后往前modify，然后拷回前面去
第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
我试了一下，果断发现bug，修好。
然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂
。然后lz就删了重新用levelorder traversal写了一遍，写完的时候其实就超时了一分
钟左右。面试官没让lz检查，说已经good enough了，不过还是指出一个小错误，然后
自己主动把那个bug改掉了。然后面试官说这题有空间复杂度O(1)的做法，不过lz当时
估计也想不出来这么做。
先问了两道behavior问题都是前一晚上在版上看过了。真是感谢本版
1. 为什么想来facebook
2. 你觉得facebook有什么值得改进的地方
两道技术题。
1.几个数字array，像这样的：
1
11
21
1211
111221
给n，返回第n行的结果。第二行返回前面一行每个number的count。我用的recursive方
法。不知道是不是最优的。
2. 3sum
最后剩了九分钟的样子他说没时间再做一题了 T T，让我问了问题就提前结束了。求
bless！
电面 1
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n
onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero
Given a string with parentheses, return a string with balanced parentheses
by removing the fewest characters possible. You cannot add anything to the
string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
注意：balance(")(())(") != "()()"
大概是给一个数组，然后有一些数是重复的，然后找到重
复最多的那个数，比如说 int input[]={3,7,4,3,6,1,3,6}，重复最多的数是3，这些3
的index分别是0 3 6，那么要求程序以相等的概率返回这3个index,
int computeIndex(int[] input);
33.3% return 0
33.3% return 3
33.3% return 6
当时因为叙述的比较绕，所以光题目就理解了半天，最后在他的提示下找到答案：先扫
第一遍，找到出现最多的那个数（比如3），然后写个random函数, 再扫第二遍，每次
遇到3就调用这个Random函数，若Random返回值大于一个阈值就返回当前的index。比如
这个函数可以是
bool ran(int size){
if(random()*size<1)
return true;
return false;
}
Given a sequence of distinct integers, your program must remove as few
elements as possible in order for the elements which are not removed to
appear in ascending order. If there is more than one way to do this, your
program must print one solution, then print the number of all solutions.
Example.
Given 1 2 3 8 10 5 6 7 12 9 11 4 0
Remove 8 10 12 4 0
Remain 1 2 3 5 6 7 9 11 (ascending)
To form an ascending sequence, you must remove at least 5 elements. There is
only one way to do it.
不太理解print the number of all solutions.难道要先找出max length of the
substring，然后再来找solution？
leetcode原题，Valid Panlindrome
"A man, a plan, a canal: Panama" is a palindrome.
这题之前做过，也很简单，但当时太紧张出了一个很sb的bug，还是在面试官提示下找
到的。15行的代码出bug实在是不能犯的错误。另外在判断一个char是否letter的时候
没有另用函数把一堆&&写了两次，被批评不够简洁。
第二题，将1->2->3->4->5->6->7 变成 1->7->2->6->3->5->4，不能用额外空间
第一遍用了recursive很快解决，被指出用了stack额外空间，开始改iterative，最后
因为第一题浪费时间手忙脚乱没改完。说了一下大概思路草草收场，面完就知道不妙。
4天后被通知挂了。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
Facebook一个：
1 reverse linkedlist (这个我无话可说)
2 decide whether two strings are “similar”, definition of “similar” :
only allow at most one modification, definition of “modification”: insert,
delete, or replace
1。isBST。
2。reverse words in sentence。
面试官非常nice，可能题目也不难，主要考察会不会编程。
最后稍微多聊了一些work相关的东东，超时几分钟。
前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List<String>
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [john@gmail.com]
#2 Mary [mary@gmail.com]
#3 John [john@yahoo.com]
#4 John [john@gmail.com, john@yahoo.com, john@hotmail.com]
#5 Bob [bob@gmail.com]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List<List<Contact>>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍。
第二个人也是出了两道题目，第一题是给两个string，判断其中一个string能否对其中
的一个字符通过一次的insertion或者一次deletion或者一次replacement变成另外一个
string，比如
cat cast True #第一个string通过一次insertion可以变成第二个string
cat at True #deletion
cat cot True #replacement
cat dog False
cat cat False #因为这两个string相同，不需要任何的操作，要返回false
第二题是找出factorial(n)中有多少个0，我跟他说我做过
第三个人大部分时间都是问的experience，问为什么Facebook，对Facebook的哪个
feature最喜欢，为什么喜欢，然后这个feature还有什么不足。之后让给他一个非常
specific的例子说当你和同事出现技术上的冲突的时候，应该怎么解决，问的特别细，
特别深入。之后让写一道题，是leetcode上的，linux里面的cd命令那题，就是给定你
当前的系统路径比如/a/b，然后你要cd到另外一个目录，给你cd的输入比如cd ../pq/.
/r，那么最后的路径应该就是/a/pq/r，要求输出最后这个路径
coding：两个大数相加，leetcode原题
onsite：
一共四轮
1. 正则匹配。这个题目从前做过，所以大概有印象，做的比较快
2. 谈我的dissertation， 面试官一直challenge我为什么读博士，说我的论文太
mathematical，为什么不做点实用性强的。然后还有一个coding题目
一个链表 1->2->3->4->5
转换成 1->5->2->4->3
开始的时候，我给了一个递归的方法，然后他让我improve，只说思路就可以，给出了
一个线形的方法。
3. system design
问如何实现 Facebook messenger
给出了一个hierarchical infrascture.
应该能够保证scalable
4. 两个问题，第一个是给了一段python的code，问这个code干什么用的
第二个是实现支持‘*’的ls
这个可以用递归来实现
1 二进制加法
/**
* i.e.
*
* char a[] = "11";
* char b[] = "1";
* char *c = bstradd(a, b); // c is a pointer to "100"
2 分层遍历二叉树
前两题. binary tree level by level，用两种方法来解决。
第三题. 3-Sum，找一个数组里面是否有3个数加起来等于0.
1. Palindrome String (LeetCode)
2. Sum3 (LeetCode)
3. Letter Combinations of a Phone Number (LeetCode)
Sum3还给了排序和HashTable两种解法
Onsite Interview：
一共三轮，每轮45分钟，因为是Master所以没有System Design：
1. 半轮Culture Fit的问题，另外一道Coding，Sort List (LeetCode)，要求In Place
，递归的解法要用到Call Stack，讨论了一下没想到更优化的方法，就写了递归Merge
的解法。
2. 两道Coding题目，一道可以化为普通的Binary Search，另外一道是Anagrams (
LeetCode)，都很快搞定，之后剩下将近20分钟就让我提问题了，随便聊了一下感觉还
挺愉快。
3. 先详细的问了本科的一个项目，之后一道Coding，
要求将Binary Tree以Inorder的
顺序转化为Circular Doubly Linked List，在递归Inorder Traverse的基础上做了些
修改，处理Corner Case的时候稍微花了点时间，
电面， 中国大哥， 问了一题，就是给read4k，实现read any bytes. 读大文件时如何
优化
onsite:
1， 美国人， 给一个词，判断是不是Palindome,
然后扩展问，给一个字典，找出所有对 单词，这两个单词可以组成一个palindom,
然后有问，可以组合任意个单词，怎么找到最长的可能的palindom
2, 中国大哥， 问了 permutation 和几种变体
3, 问现在的项目和resume
4, 美国人， 系统设计，设计各系统能返回 top 10 listened songs from your friends.
Clone graph
1. 一个manager 先聊behavior， 然后做了一个小题
isOneEditDistance 判断两个string是不是只差一个编辑距离。
2. 3Sum 变体，每个数字可以重复用。
3. System design设计手机上读取photo feeds的app。
功能： 读取好友的最近图片
阅览好友的相册
要求： 满足功能的同时减少对手机的能耗。
4. (1) 一维度向量相乘。每个向量很长，billion个数字。
(2) 多线程 reader 跟 writer 的经典问题。
加面
1. 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
2. search in rotated sorted array LC原题。
decode ways LC原题。
一个是分层打印二叉树，一个是老式手机键盘数字对应字母，给几个数字，求全部可能的组合
1. Find successor in BST
2. Find minimum number in a rotated sorted array (当时这个题还没在leetcode里，所以写得代码有些繁琐，估计因为这个要再电面一轮）
电面2
1. Insert a node into a sorted circular linked list ( all next element is larger except for the last one), the given head can point to any node
1 -> 3 -> 5 ->7
^ |
| |
| _ _ _ |
如果node的值是2，则插入1和3之间；如果node的值是8或者0，插入7和1之间。
要考虑node值重复的情况，虽然结果一样，但要和面试官讨论新的节点插入的位置，可
能插入在最开始或最后，我不记得了。
例如插入3, 结果是1->3->3'->5->7或者1->3'->3->5->7
2. Clone graph(leetcode)
第一轮：聊research，最后问了一题，
write a function f(x), so that f(x) returns true with x% probability。
第二轮：Given k sorted linked list, n elements in total, merge them into one sorted linked list。
经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
heap。
第三轮：convert a binary search tree into sorted double-linked list。
implement memcpy.
第四轮：System design。
Given a location (a coordinate), return top 100 nearest places.
Follow up, given a location, return top 100 events within x months in nearest places。follow up 其实就是多加一个时间维度。
提出的方案就是对平面坐标系做grid，每个grid里的locations放到一台机器上。搜索
的时候就是针对input的location找到候选的grids(以某个半径画个圆)，再从中通过
map-reduce找到前100个location。
可以根据grid里location的密度或者访问量决定是不是要再做partition以提高
scalability。
follow up的话就是多加一个dimension代表时间。
1. Palindrome String (LeetCode)
2. Sum3 (LeetCode)
3. Letter Combinations of a Phone Number (LeetCode)
Onsite Interview：
一共三轮，每轮45分钟，因为是Master所以没有System Design：
1. 半轮Culture Fit的问题，另外一道Coding，Sort List (LeetCode)，要求In Place
，递归的解法要用到Call Stack，讨论了一下没想到更优化的方法，就写了递归Merge
的解法。
2. 两道Coding题目，一道可以化为普通的Binary Search，另外一道是Anagrams (
LeetCode)，都很快搞定，之后剩下将近20分钟就让我提问题了，随便聊了一下感觉还
挺愉快。
3. 先详细的问了本科的一个项目，之后一道Coding，要求将Binary Tree以Inorder的
顺序转化为Circular Doubly Linked List，在递归Inorder Traverse的基础上做了些
修改，处理Corner Case的时候稍微花了点时间，感觉上可能栽在这一轮。
1） 国人大哥，culture fit半小时, 花10分钟象征性做了一个非常简单的回文。感觉
大哥人很好。
2） 国人大哥，非常简单的题矩阵相乘，然后follow up,涉及到tree， hashmap,
arraylist，也都很简单。 代码也得也都很顺利，感觉大哥人很好。
3）老印，最长的括号子序列。题不难，感觉这轮做得很差，老印提醒了2次，代码改了
几次， 虽然写出来了，老印最后照了相，知道挂了。
5）白人，设计一个在线图片编辑系统，完全没有经验，只能按版上的partition,
backup, cache等瞎说。边引导边回答。当面给的feedback都还算positive。
先聊了聊自己的经历，为什么要来fb之类的问题，因为我有图像处理的背景，就问了一
题相关的。
给一个2D board，上面由 0 和 1 组成，0 背景，1是图像，求里面有多少个连通域，
follow up 是每个连通域的面积是多大。我先写了recursive的做法。后来面试官又要
求了iterative的做法
第一轮：主要谈自己以前做的东西，面试官问得比较细，总之就扯了扯。问了一题
coding，给一个数组，问里面有没有两个数相加等于0，给了 O(n) time O(n) space的
做法，和 O(nlog n ) time和 O(1)space的做法
第二轮：给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个value
，面试官要求 O(1) space和 O(log N) time的解法。
第三轮: regular expression match, leetcode上原题，先写了 dp 的解法，面试官要
求我再写一下recursion的解法，写完后问了两个算法各自的复杂度
第四轮：design，设计手机系统，可以查看周围的好友，饭店，电影院等等
个人感觉fb面得题目的确不难，基本都见过，但是每道题基本上都问了很多种解法，问
得比较细，而且一定要bug free，这个比较难做到。面经就大致这样了，大家加油共勉
第一次是个同胞面试，题目是给出一个数组s和一个值y，找出s当中最长的sub数组的长
度，使sub数组的sum等于某一个值y。磕磕碰碰，同胞提示了两个关键点做出来了。但
由于做的不是很顺畅，F家决定再让我电面一次。
第二轮遇到一个烙印，由于之前没啥准备，突击了一周的数据结构和算法。没想到烙印
一上来第一个问题居然是问我一个概念问题，什么叫Big and Little Endian。我没答
上来，于是烙印就说算了。我奇怪为啥问这个问题，他说所有熟悉C++的人都应该会这
个。我说我没在简历上写我会C++啊，他说他看到第一行写的就是C++。最后随便给我一
个题叫我写了个binary search结束。
我回头再看我的简历，我的确没有写C++，我只说我有些VC#的经验。想起来真有些郁闷
，其实Big and Little Endian的概念也不复杂，回头看wiki几分钟就搞明白了。
1. Level-order traversal of bst
2. Deep clone linked list with random pointer
3. Divide without division
其实没面好，每题都被他找到了bug，而且最后一题的二分法解法是被他提示才做出来
的。最囧的是他提示我可以用二进制来算1/2以后我直接说，对不起啊我二进制实在不
熟。。。
两题都和Longest consecutive sequence相关。第一题秒杀，第二题居然没想到用
HashMap......我当时做LC的时候一下就想出来了。。。这次居然没想到。。。
还好，大哥一直在引导我思路（但没有任何直接的提示），最后我豁然发现了我思维盲
点，马上hashmap秒杀
1. binary addition
2. regex matching
正则表达式那题我哭了，我leetcode刷了147题，这题就在我没写的那7题里面。。。
跟着比较糟糕的思路写了好久，最后发现写不下去了。。。撑到最后姐姐提示我用递归
，于是我大概再重新说了一下这题的算法，但是代码显然是没法写了。。。
1. fib(n)你说这不是放水那啥叫放水
2. 直方图找最大矩形
3. 面试官一直在重复这是附加题。。。
n个数，没排序，怎么找第k个；然后n大的一台机hold不住的时候怎么办
先问了Rotated sorted array，我可能是之前和她聊behavior说得太嗨了，直接和她说
我做过。。。
后来问了一个简单版的Edit distance，给了个O(n)时间O(1)空间的解法。写完了她和
我说有个bug，我自己检查后改了bug，然后她接着问如果我不改的话哪种test case会挂
总体来看我觉得我有两轮面的应该不错，但另外两轮就难说了。Regex没做出来和
HashMap反应太慢始终是我的一个心病啊，觉得我肯定要挂了但是又忍不住不停地找
good signs来麻痹自己。于是来发个面经，求版上众牛bless!!!!!
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
一个题目是关于穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见过这个题目。
判断一堆线段是否相交，3 sum zero, 实现next_permutation，然后一道数学题（无限大棋盘的跳马问题，时间不够，没做出来）。
第二轮的面试官自我介绍完后跟我聊了很多我研究生期间做的东西，以及简历上的一个
项目，然后让我在纸上实现字符串查找函数strstr。这个时候我没马上写代码，而是告
诉他有很多算法可以做这件事情，比如有naive的，或者比较高级的，然后他马上说
naive的就ok了。写完后，他问我刚才提到有比较高级的算法？我就给他解释了下kmp。
之后他又开始扩展这题，说如果待匹配的内容很大并且不会变，但是有很多模式串怎
么办。我给了说了2种算法，一种是把待匹配串的所有后缀都插入到一颗TRIE树种，另
一种是利用RK hash函数（这种算法需要假设模式串的长度都不会很长）。
第三轮大部分时间都在聊项目以及以前的一些经历，最后快结束的时候让我写了2个程
序，一个是数的进制转换，一个是在一个BST中求第k大的数。。
7. 10.11号google onsite，在上海进行的，上午2轮，然后在那边吃午饭，下午再进行
一轮。onsite的题目不便多讲，有一题在昨天的某个帖子中已经提到了(binary tree
max path sum)，另外值得分享的一题是给定一颗完全二叉树的根结点，求这颗树的结
点数。这个题大家可以想下。
电面
1.判断一个树是bst
2.给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个
数组中的节点所构成的树是tree
Onsite
1.介绍background，各种讨论
2.一个有序数组被rotate过，判断rotate的距离。考虑无重复和有重复
3.设计题。设计一个shorten url的service。讨论包括design，scale，各方各面
4.N个数中拿出K个数的组合并打印出来
5.二叉树的Deserializing
面完之后感觉很好，聊的也都很开心，题也不难，答的也很顺利，昨天接到电话还是有
点失望，要move on了。
各位也都加油！
1. Leetcode原题，three sum的变种, 允许3个数字重复，就是起始位置一样就行
2. 给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎么做
3. f家面筋出现很多次的小偷偷钱题，用DP，要求不相邻的数的和最大
4. 给一个tree，用递归变成一个circular doubly linked list
5. 还是f家面筋出现很多次的read4K那题
--
第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
的k个点。k 远小于 n。
开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogk。面完
后问了一下别人，发现是可以用selection做的，更快。
第二道比较tricky给是一个string和一个alphabet，找出包含所有alphabet的最短的substring。
我的方法是用hashset保存alphabet，读string，每遇到一个字母，就从
hashset里面移除对应字母，最后如果hashset为空则string包含所有字母。在面试官提
示下发现可以试着缩短这个string，再check是否包含所有字母这样子做，code写完了
没有多余时间优化，大致讲了一下思路，就结束了。
另外求leetcode 和CC150之外，如何找到这种题练？感觉这个难度还是比leetcode平均
难度高一些啊。
1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
b) 给你n个用户和k,找出发帖数最多的k个用户。
2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
大的那条是什么。
b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*a2*...*an-1.
3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
Characters Given Read4”类似。
第一面system design. 先问怎么求submatrix的和，回答说先预先计算好 (0, 0), (i,
j)的和，然后可以用这个和求其它的和。以为他会顺着这个问数据大了怎么design
system，结果没有，问了个跟这个题毫不相关的，
怎么检测一个程序为什么慢。然后就回答先确定bottleneck是cpu, disk io, 还是 network io. 然后针对每项他都详细问
怎么做。交流的过程中有时候没太明白他的问题吧。反正这一面的结果很不好，当天就
给我加了另外一面system design. 最后还是挂在这一面上。
第二面coding. 先是 best time to buy and sell stock. 因为之前练过，讲了下思路
就直接写了最优代码。然后他又让写返回两个index 的代码，这个时候有点慌了，因为
没练过这个。。。然后慌忙中还写出了一个bug, 他提醒之后才发现的。改完后又让写
另一个链表相关的题，单链表k个k个分组，反转奇数组。比如 link = 0->1->2->3->4-
>5->6->7, k = 3返回 2->1->0->3->4->5->7->6.
当时知道会写不完这个题的，所以就尽量先写构架，
把一些细节用函数代替。最后把构架的代码写完了，留了一个反转单链表的函数没写，
刚开始写这个函数的时候下一个面试官来了，就稍微讲了下思路。
第三面 director. 问了下为什么来facebook, 怎么处理conflict，然后跟项目有关的
技术问题。最后让写sqrt(x)二分算法的代码。
第四面 coding. 先问wildcard matching. 写了个暴力搜索的代码，问怎么优化的时候，说可以记忆化，记住中间结果。
然后下一个题。 实现一个iterator, constructer
传入一个二叉排序树，第一次调用next()返回最小的，第二次返回第二小的，第n次返
回最大的，以后返回null. 刚开始提了几个用O(n)空间的方案，都被他否定了，问他是
否需要O(1)空间时，他说不一定要是O(1), 那必然就是O(logn)了，所以就想到了思路
。其实就是树的中序遍历的非递归实现。把栈存到Interator里面，next的时候改变栈
的状态就好了。写完后有一个细节没考虑到，他提醒后改好了，另外constructor 和
next里面用了同样逻辑的代码，也被他指出来了，他还指出了代码里面一个很小的优化。
两个题目：
1.add binary,lc原题；
2.binary tree, print all paths from root to leaf.
题目都不难。两个题分别分析了一下复杂度，第2题折腾了半天还是弄错了，最后提示
之下改正过来了。
实现 Tree iterator， 接着问，如果要prev咋办。
1. 3sum
Given an array of integers
[1, 2, -3, 4, 0]
To find any 3 numbers in array such that they sum to zero.
eg:
1) 1 , 2, -3
2) 0, 0, 0
2. Q2: Given set of points in 2d grid space. Find a grid point such that sum
of distance from all the points to this common point is minimum.
eg: p1: [0, 0] p2: [3, 0] p3: [0, 3]
ans: r: [0,0]
sum: 0 + 3 + 3 = 6
for every other point sum to this ans greater than 6.
实在不知道是啥，乱说了个找mininum manhattan distance,然后赶紧临时google下，
貌似是找median，然后对方说能不能证明一下。。表示不会。。。
这题正解到底是啥？
给定一些不相交的区间和一个新的区间，要求合并起来
但问题是不让用新的vector/stack，也就是说要用constant additional space
如何不用recuisive的方法preorder遍历一个tree（tree 有多个不同的孩子）
给一堆F的用户，以及朋友关系，朋友之间的关系是双向的。问能否将朋友的关系图分
成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。
电面二面：
leetcode的手机键盘给数字，求各种字母组合的题。但是让给出recursive和iterative
方法。recursive很简单，iterative之前没写过，比较难想，当时卡了一会儿。后来写
出来了。
onsite五轮，每轮45分钟：
第一轮coding为主：先聊了下他的项目和我的research，几分钟的样子，然后写了个二
进制字符串相加的。另外一题是一个直角坐标系，上面和N个点，找出离原点最近的k个
点，就是top k问题
第二轮系统设计：让设计分布式的large scale的producer和consumer问题。就是有一
堆机器是producer，一堆机器是consumer。后来顺便写了一道coding题，范围变成是单
机的producer和consumer，实现produce和consume函数，其实就是相当于fix size的
cache的add和pop问题，不用考虑多线程
第三轮coding为主：写了道regular expression匹配的，leetcode原题。但是让优化，
当时刚开始没想出来，后来经提醒知道用memorize的方法。以前DP的题知道用这个方法
，这题从来没去想过，差点出差子
第四轮culture fit：主要讨论了research。后来写了个简单的题，三个数组，从三个
数组各取一数，找出和为某个值的组合
第五轮coding为主：三个color排序的题，leetcode原题。另一道是平面上一堆点，找
出四个点，使得四边形面积最大。刚开始想不出，后来问题简化成找三个点，使得三角
形面积最大。这题挺难的。后来没有coding这题
1. 国人大哥，问了几个常见题，最难的题具体细节记不清了，大概是01矩阵上的DFS，
随便聊了会儿直接拿到onsite。
Onsite
1. 白女，亚马逊manager出身的女工程师，主问culture fit问题，比如为什么想来FB
。Coding题是恶心的罗马数字。因为鄙视这道题所以没在leetcode上刷过，还好是简单
题，很快写出来了。
2. 一个搞后端处理data的中国哥们，问sort linked list。随手写了个merge sort过
关，merge的时候没用dummy node方法，if语句用的很多，比较蛋疼。讨论了一下具体
的算法复杂度，直接背答案的人估计会被考倒。所以说做面试题的目的主要还是掌握算
法并能灵活用于解题，不太可能所有题都能练到随手就写出最优算法bug free的程度。
4. 一个看上去很强壮的老美，广告组的，问设计题。FB用户每天发非常多的status
update，要求设计一个系统，能够对最近几天内的update进行关键字搜索。我回答建一
个index，每个单词对应一个status update id的列表，查询结果是取列表的交集。我
对大数据处理完全没经验，不清楚这轮会被鄙视到什么程度，反正从结果看是pass了……
5. 又是中国哥们，一看就像技术牛人。有两个长度为n的数组，分别存放螺钉和螺母。
它们之间是一一对应的关系，而没有大小相同的螺钉或大小相同的螺母。现在有个机器
人，它能拿起一个螺钉和一个螺母，试着把它们拧在一起。如果成功，返回0，如果螺
钉大于螺母返回1，小于则返回-1。初始情况下两个数组是shuffle过的，需要设计一个
算法让机器人帮你sort两个数组，使得两边相同index的螺钉和螺母是一对。
这题虽然不是新题但我也没见过，虽然上来就想到肯定得用quick sort的思路，还是一
时纠结住了。经提示才想出正确算法，是两边同时做partition。代码倒是很容易写，
写完后又被要求分析复杂度。
6. 一个亚裔带了一个围观的老美，两人加入FB的时间都不长。题目是在BST里找两个
node的LCA。我当时头脑发昏，写了一个common binary tree的解法，因为要处理各种
edge case，代码十分冗长。后来才发觉得他问的是最简单的变种，二分查找就行了。
快结束时就随便聊了，围观的老美挺能侃，虽然shadow面试理论上不应该说话吧……主
要谈及FB工程师文化，有没有类似于G的20%时间政策。他们说FB还在扩张期，没资源搞
跟主业不太相关的项目，比如自动驾驶汽车，但如果想的话可以参与其它组的项目。还
有就是hackason几天牛人能搞些cool的东西出来。一般都说FB比较辛苦，平时做其它
project的时间不会有多少吧。
面试当天，HR说她临时拉了一个人来面我design，开始以后，他问我准备做F啥项目，
我想了想，自己编了一个项目。。结果这个老哥来劲了。。不停的问我为啥觉得这个项
目可以做，为啥比现在F其他的项目好？对F有啥好处 等等。。。一直聊到最后5分钟，
他估计想起来要面design了。。问了一句，你准备怎么实现？ 我日。。我说了2句话，
第二个面试官就来了。。当时就想，估计要悲剧了！
第二轮又是纯聊天， 面试官是个manager，抓着我研究生做的一个项目不停的问。。还
好是我做的，不然真的被问趴了
第三轮和第四轮是coding， 这2轮我一共只写了 3段coding，
第三轮的coding 是 leetcode 原题，一个数组，输出所有子集，有重复，没重复，迭代和循环都写了，bugfree 没啥问题。
第四轮，我脑抽了，找n个二维点中离原点最近的k个点。我的partition写的有点卡，最后写完以后 时间居然就到了。。而且面试官还抓了一个小错误：本来要输出k个，我输出了k+1个。。。当时我满头黑线。。。
You have two arrays X and Y. Each are having say M and N elements already
sorted increasingly. We have to find the k-th largest one of the whole set
M + N elements.
- Simple regular expression match，可以match的符号只有3种：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
和没用过regex的同学解释一下 例如
a+b 可以match : ab, aab, aaaaaaaaaaab
b.+b 可以match : bb, bab, b12345b
- boggle puzzle 找到里面所有的单词，写code
- Given preorder of a binary tree, print out all the binary trees
Leetcode 原题 decode ways
翻转链表。说实话我还挺意外的，我给出了一个非递归的实现，然后follow
up，他让我写个递归的，我只得另造一个函数。非递归的我应该写的没问题，递归的出
了点小bug，他给我一个用例让我测一下，我看了下发现确实有问题，迅速改对了，他
表示OK。然后又是follow up，问我当链表很大的时候递归方法有什么问题，我告诉他
会导致堆栈溢出。他继续OK。
技术题2. Leetcode的sort color，没什么好说的，只不过leetcode的原题类型是int，
值只有0 1 2，他给的是类型是个对象，然后通过getCategory()获取类型，只会返回1
2 3三种。实际上就是一个题。这个题前两天刚做过，迅速bug free之，他继续表示OK。
技术题一共就两题，完事儿之后常规性让我问问题。我问的跟上回G家问的差不多(懒得
再准备新问题)，一个是F家有没有跟computer graphics相关的组，一个是F家用不用敏
捷开发。他说了挺多。
第一题leetcode原题isPalindrome，只考虑字母。写完了之后题目要求稍微有个改变，
所以我相应改代码，改完有个小bug被指出，但是还是改过来了。
第二题也是原题，Tree Level Travel, 写了DFS的算法，又写了BFS的算法。
原来说好45min的最后到1个多小时，不知道是不是好事。
最后也是惯例问有没有什么问题。
1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
知道描述清楚了没有…这题没写代码，讲了下思路……
3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
议室满足所有会议.注意，(4,5), (5,6)……这个输入返回true……
4. 同样的一堆会议时间，返回最少需要多少间会议室.
0. 给定一个双向链表，以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机，每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间，但不能确定具体容量是多少，现在想通过按这三个可乐
机，达到容量为[D, E]之间的可乐，问能否做到。也就是能否找到非负整数x, y, z使
得x*Amin+y*Bmin+z*Cmin>=D并且x*Amax+y*Bmax+z*Cmax<=E。感觉是个扩展的背包问题
，我给了穷举法和DP的解法，不过面试官最后说有个复杂度不依赖于D和E的解法，现在
也不知道怎么做。
2. 二叉树遍历。每个节点有left/right/parent指针，只允许使用O(1)空间而不用栈。
3. 含有大量URL的文件里查找频率最高的K个URL。先给单机哈希表的解法，内存不够的
情况，给了按哈希值把大文件拆成小文件的解法。接着被问并行化，给了MapReduce的
解法。接着被问哈希表相关的计算题，M个slots的哈希表（哈希值范围是1~M，用链表
处理冲突），往里放了N个元素，假设他们的哈希值是随机的均匀分布，问slots里元素
个数的分布，也就是balls and bins的问题。不用coding。
4. 链表的插入，删除等，基本没算法，而是看coding的细节。
5. 多线程和多进程。包括哪些状态是线程间共享的哪些状态是每个线程自己的等等。
不用coding。
decoding ways 没问题和 sqrt(double).
1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
2 单链表倒序输出
3. Dutch Flag Problem
4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
中出现且仅出现一次，比如两个人，
初始 {}
move(1): {1}
move{2}: {1, 2}
move{1}: {2}
1. code部分题确实比较简单。可能比亚麻还简单。没有任何新题。大多数题在20-30行
之间，有一道可能要写40行。如果leetcode 上某题你需要写很多很多行那种被考倒得
可能性就比较小了。板上加leetcode全覆盖。在这种情况下做题得时候还是稍微激进点
。就是直接以最快得速度做最优得做法。我觉得我已经很快了。不过被问了改进外加额
外得coding,所以每个只能写两道。其实如果直接写最优的话可能能做三道。这样面试
得那张表格看起来会更满一点。电面得时候我做了三道。白板上还是很有压力得。鉴于
题可能会很简单。想脱颖而出可能这是一种方式。
2. behavior question还是要好好准备得。不要问得太肤浅。这个也可能事我挂得原因。
面试我得大概两个烙印，一个毛子和一个老美。感觉上一个老美最不友善。一个烙印比
较友善。另外一个烙印和毛子基本比较温和得态度。看不出来个倾向。当然他们得
feedback怎么样我是完全估计不出来得。
https://github.com/UmassJin/Leetcode/blob/master/Experience/facebook%E9%9D%A2%E7%BB%8F%E9%9B%86%E5%90%88.py
http://www.mitbbs.com/article_t/JobHunting/33003737.html
电面： 中国大叔面的，大叔很nice，遇到我写有bug的时候都会着急的提醒我，题也很
简单。
1： 给n个点找出离远点最近的k个， k<<n。
2: 给三个 api isSmall() isMid() isBig() 给一个array 排序，只要不被迷惑， 知
道其实是lc 上 sort color的变种就很简单了。
large scale下怎么设计一个根据关键词查询status的service。我自然又是一顿瞎扯，神马invert index, consistent hashing, 想到什么扯什么。 然而这并没有什么卵用。。不论扯到什么大哥都要刨根问底，我到最后就完全招架不住了。。大哥的表情也就越来越蛋疼了
http://yuanhsh.iteye.com/blog/2186421
Given an integer array which has the property that all the elements having same value are adjacent to each other..
e,g, {2, 2, 2, 1, 5, 6, 6, ,7, ,7}
Output: Remove duplicate element in place and output the length of the new array. Do it in place and we don't care the elements outside the new length of the array.
e.g. return 5 and the input array will become {2, 1, 5, 6, 7, x, x, x, x} "x" means we don't care its value.
http://www.1point3acres.com/bbs/thread-142450-1-1.html
calculate the dot product of two very large arrays with many 0 elements. Be as efficient as possible
就是指给两个vectors, 例如{0,3,2} 和{1,3,5}。 那么dot product 就是 0*1+3*3+2*5 ＝ 19 。 那么如果每个vector 有millions of elements, 怎样优化 可以让 running time 比 o(n) 小
他只给我提示了 把A,B简化成list of tuple。然后我用two pointer 写的
onsite一般是4轮，2轮coding，1轮design，1轮behavior+coding
校招的话，那轮design也变成coding了
和B
class A {
public void foo (A a) {
...
}
}
class B extends A {
public void foo (B b) {
...
}
}
问这么写会不会有问题
2. 关于Database的题，假如你执行
select * from employee
employee是一个table
但是返回错误说，这个table不存在什么的，但是现在已知存在这个table,问你可能是
什么原因。
完全没有思路，就说我也不知道。。。
3. 一种字母游戏这样的
给定四个位置 _,_,_,_
然后每个位置可以选5个candidates，然后问这些candidates最多可以组成多少个有效的词，字典是给定的。
http://www.weiming.info/zhuti/JobHunting/33055253/
http://www.bbsdigest.com/thread/index?bid=13&tid=33055253
比如，
如果字典是 [cake, bike, fake]
我们可以这样选candidates
第一个位置可以选 b,c,f,e,d
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
那这些可以组成3个有效的词 cake, bike, fake.
但是如果，这样选每个位置的candidates
第一个位置可以选 z,c,v,b,y
第二个位置 i,a,o,p,e
第三个位置 k,m,w,q,a
第四个位置 e,g,h,k,l
只能组成一个有效的词就是bike.
这样就是第一种选candidates的方法比较好。
然后问你怎么选每个位置的candidates，最终可以让能组成的词最多。
没有什么特别好的思路，问是不是brutal search，还有更好的方法吗？答：你如果要
brutal search的话，你估算一下时间。
我就开始算时间，发现很长，然后面试官说，那你想办法优化。。。但是因为算brual
search的时间算了太长时间了，就没什么时间优化了。。。
其他的就不废话了，电话打进来了。一哥们先介绍了一下他做的东西，做API的。然后
说了2min，给我说今天一共45分钟，首先会问5-10分钟简历，然后30分钟左右的coding
，最后的时间提问。
1. 一来就是一道简单题，翻转链表
// Reverse a Singly Linked List
// Example Input: A -> B -> C
// Example Output: C -> B -> A
他先让说思路，然后问时间和空间复杂度，然后写代码。说思路说了半天，这种list的
题，就是画图，英语不好说起来真费劲。。。这道题应该是Leetcode上一道的一个小部
分，所以很快就写完了。
2.第二题直接copy 题目，感觉跟leetcode上面的interval那题很相似，简单一点点。
// Given a array of pairs where each pair contains the start and end time of
a meeting (as in int),
// Determine if a single person can attend all the meetings
// Input array(pair(1,4), pair(4, 5), pair(3,4), pair(2,3))
// Output: False
同样的思路+复杂度。 同样是变种题，还变简单了，很快写完。（主要是考比较器的
override吧）
3. follow up第二题
// determine the minimum number of meeting rooms needed to hold all the
meetings.
// Input array(pair(1, 4), pair(2,3), pair(3,4), pair(4,5))
// Output: 2
我看表还剩下10分钟，然后想了3min钟，面试官就说没时间了，要不你说说思路。然后
说了一下思路，面试官说OK。让我提问题。瞎问了一个问题。面试官还特别详细的解答
了。他说超了一点时，不过没关系。 然后互相感谢了一下，客套了一下。就再见了。
第二天HR说下一轮Onsite了。
Clone graph
onsite
1. 一个manager 先聊behavior， 然后做了一个小题
isOneEditDistance 判断两个string是不是只差一个编辑距离。
2. 3Sum 变体，每个数字可以重复用。
3. System design设计手机上读取photo feeds的app。
功能： 读取好友的最近图片
阅览好友的相册
要求： 满足功能的同时减少对手机的能耗。
4. (1) 一维度向量相乘。每个向量很长，billion个数字。
(2) 多线程 reader 跟 writer 的经典问题。
加面
1. 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
2. search in rotated sorted array LC原题。
decode ways LC原题。
1， valid palindrome, leetcode 原题，但是不能修改String, 所以就不能用s.
toLowerCase(), 当时就急了，因为不知道Character的 toLowerCase的method是什么，
她说写sudo-code就可以了。很快做出来了，然后写test cases
2, Binary Search的变型，Git Bisect, 从某一个版本开始，引入了一个bug, 然后让
我找出引入这个bug的第一个文件。binary search之
Given a list of words，find all palindrome pairs(two words that can build a
palindrome). For example, "ddcba" and "abc"are palindrome pairs, since they
can build "abcddcba" which is palindrome.
Follow up，可以组合任意个单词，怎么找到最长的可能的palindrome.
面的LC 上的 sort color，之后follow up是如果颜色超过三种怎么办？
google安排了两轮电话面试
第一轮是个三姐，LC上的insert interval类似的题，之后各种讨论follow up
第二轮是个美国人，问题是给你一个sorted的长度为N的数组，求所有数组内出现次数
超过N/4次的数字（popular numbers）
我写出了O（N） time O（1）Space，之后面试官问我有没有更好的解法了，我说我想
不出来了
接着问了一道followup， 现在给你一个time complextity O（1）的function， 叫做
findCandidates（A）， return的结果是一个长度为3的数组，popular numbers是这个
数组的一个子集，问如果用这个function，能否改进time complexity。
这道题我写的时候出了个index out of range 的bug，被面试官指出，马上改过来。
最后讨论了如何test我写的这个function
第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
inplace，线性复杂度。这一题做的很顺利。面试官说good enough
我估计得至少两倍空间存在，最惨的情况是字符串上全是a，然后又要求inplace的话。。
我的想法是把字符串先复制到数组的后面，然后再挨个拷回前面
我的做法跟你差不多。区别是先把字符从后往前modify，然后拷回前面去
第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
我试了一下，果断发现bug，修好。
然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂
。然后lz就删了重新用levelorder traversal写了一遍，写完的时候其实就超时了一分
钟左右。面试官没让lz检查，说已经good enough了，不过还是指出一个小错误，然后
自己主动把那个bug改掉了。然后面试官说这题有空间复杂度O(1)的做法，不过lz当时
估计也想不出来这么做。
先问了两道behavior问题都是前一晚上在版上看过了。真是感谢本版
1. 为什么想来facebook
2. 你觉得facebook有什么值得改进的地方
两道技术题。
1.几个数字array，像这样的：
1
11
21
1211
111221
给n，返回第n行的结果。第二行返回前面一行每个number的count。我用的recursive方
法。不知道是不是最优的。
2. 3sum
最后剩了九分钟的样子他说没时间再做一题了 T T，让我问了问题就提前结束了。求
bless！
电面 1
1) fabanacia，期待o(lgn)解法,但O(n)也行
2) generate all possible paretheses, leetcode原题，会让分析最优/平均时间，我
只知道worse case 是O(n^2)
onsite1
behavior: 1)有什么跟同事意见冲突的案例，怎么解决
2) 以前做过的项目如果现在再做会有什么不同/改进
3）divide and mod，但不能用/或者%，基本也是leetcode原题了
onsite2
system desgin: 因为我是kernel背景，让我用mutex,cv实现一个semephor，说先考虑
单核，然后拓展到多核，但我只写了单核的就没时间了，不知道多核的会有什么不同，
要求code compilable，MD三哥从一进来就没好脸色，此轮negative
onsite3:
1) 给你10g文件，1g内存，数总共有多少个不同的数，答案是用bit来记录数字，总共
4b个interger,最多用0.5gb来记录，follow up是如果只有400m怎么办，答案是把数字
hash一下或者说scan文件多次，每次取尾数bits不一样的数，不用code
2) read file up to 4K, 也是老题了
3) 求平方根，基本也是leetcode原题，但给的数是double，这样如果给的n是小于1的
数，初始的right就得取1而不是n
onsite4:
也是kernel组的三哥，先上来问了btree跟bst的区别，btree里放多少个index怎么决定
，答案是disk block size / 每个index的长度，如果是内存的话就用cache line size除
还有vm的，我也不大懂，好像是说如何解决内存的fagement问题，如何把多个分开的小
片段移到一起，用到了madvise这个syscall,还问为什么返回一个新的page之前要清零
，答案是因为page上可能是别的process的内容
code题是decode，比如说1 → 1, 2 -- > 01, 3 → 001, 4 → 0001,....，给你一个
无限的stream，要求输出数字，应该没啥难度，follow up是如何优化，我给的答案是
map，就是依次取char而不是bit，然后把char的值对应到string上，他说cpu还有一个
instruction可以直接查询此个char有多少个leading zero
Given a string with parentheses, return a string with balanced parentheses
by removing the fewest characters possible. You cannot add anything to the
string.
Examples:
balance("()") -> "()"
balance(")(") -> "".
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
注意：balance(")(())(") != "()()"
大概是给一个数组，然后有一些数是重复的，然后找到重
复最多的那个数，比如说 int input[]={3,7,4,3,6,1,3,6}，重复最多的数是3，这些3
的index分别是0 3 6，那么要求程序以相等的概率返回这3个index,
int computeIndex(int[] input);
33.3% return 0
33.3% return 3
33.3% return 6
当时因为叙述的比较绕，所以光题目就理解了半天，最后在他的提示下找到答案：先扫
第一遍，找到出现最多的那个数（比如3），然后写个random函数, 再扫第二遍，每次
遇到3就调用这个Random函数，若Random返回值大于一个阈值就返回当前的index。比如
这个函数可以是
bool ran(int size){
if(random()*size<1)
return true;
return false;
}
Given a sequence of distinct integers, your program must remove as few
elements as possible in order for the elements which are not removed to
appear in ascending order. If there is more than one way to do this, your
program must print one solution, then print the number of all solutions.
Example.
Given 1 2 3 8 10 5 6 7 12 9 11 4 0
Remove 8 10 12 4 0
Remain 1 2 3 5 6 7 9 11 (ascending)
To form an ascending sequence, you must remove at least 5 elements. There is
only one way to do it.
不太理解print the number of all solutions.难道要先找出max length of the
substring，然后再来找solution？
leetcode原题，Valid Panlindrome
"A man, a plan, a canal: Panama" is a palindrome.
这题之前做过，也很简单，但当时太紧张出了一个很sb的bug，还是在面试官提示下找
到的。15行的代码出bug实在是不能犯的错误。另外在判断一个char是否letter的时候
没有另用函数把一堆&&写了两次，被批评不够简洁。
第二题，将1->2->3->4->5->6->7 变成 1->7->2->6->3->5->4，不能用额外空间
第一遍用了recursive很快解决，被指出用了stack额外空间，开始改iterative，最后
因为第一题浪费时间手忙脚乱没改完。说了一下大概思路草草收场，面完就知道不妙。
4天后被通知挂了。
题目好像以前见过，就是给一些不重叠的interval，然后设计一个数据结构来存储，实
现插入interval和find一个value两个函数，前者碰到重叠就return false，后者碰到
所在的interval返回。
Facebook一个：
1 reverse linkedlist (这个我无话可说)
2 decide whether two strings are “similar”, definition of “similar” :
only allow at most one modification, definition of “modification”: insert,
delete, or replace
1。isBST。
2。reverse words in sentence。
面试官非常nice，可能题目也不难，主要考察会不会编程。
最后稍微多聊了一些work相关的东东，超时几分钟。
前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List<String>
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [john@gmail.com]
#2 Mary [mary@gmail.com]
#3 John [john@yahoo.com]
#4 John [john@gmail.com, john@yahoo.com, john@hotmail.com]
#5 Bob [bob@gmail.com]
现在我们知道如果email address相同的话，那么就说明是同一个人，现在要做的是根
据这些email address，把同一个contact给group起来，生成一个List<List<Contact>>
，比如我们就可以知道#1，#3，#4是同一个人。注意不能根据名字来group，因为有可
能有相同名字的人，或者同一个人有可能有不同的名字来注册之类的。我给出了一个类
似graph的解法。时间不够，就没有写code，只是把逻辑解释了一遍。
第二个人也是出了两道题目，第一题是给两个string，判断其中一个string能否对其中
的一个字符通过一次的insertion或者一次deletion或者一次replacement变成另外一个
string，比如
cat cast True #第一个string通过一次insertion可以变成第二个string
cat at True #deletion
cat cot True #replacement
cat dog False
cat cat False #因为这两个string相同，不需要任何的操作，要返回false
第二题是找出factorial(n)中有多少个0，我跟他说我做过
第三个人大部分时间都是问的experience，问为什么Facebook，对Facebook的哪个
feature最喜欢，为什么喜欢，然后这个feature还有什么不足。之后让给他一个非常
specific的例子说当你和同事出现技术上的冲突的时候，应该怎么解决，问的特别细，
特别深入。之后让写一道题，是leetcode上的，linux里面的cd命令那题，就是给定你
当前的系统路径比如/a/b，然后你要cd到另外一个目录，给你cd的输入比如cd ../pq/.
/r，那么最后的路径应该就是/a/pq/r，要求输出最后这个路径
coding：两个大数相加，leetcode原题
onsite：
一共四轮
1. 正则匹配。这个题目从前做过，所以大概有印象，做的比较快
2. 谈我的dissertation， 面试官一直challenge我为什么读博士，说我的论文太
mathematical，为什么不做点实用性强的。然后还有一个coding题目
一个链表 1->2->3->4->5
转换成 1->5->2->4->3
开始的时候，我给了一个递归的方法，然后他让我improve，只说思路就可以，给出了
一个线形的方法。
3. system design
问如何实现 Facebook messenger
给出了一个hierarchical infrascture.
应该能够保证scalable
4. 两个问题，第一个是给了一段python的code，问这个code干什么用的
第二个是实现支持‘*’的ls
这个可以用递归来实现
1 二进制加法
/**
* i.e.
*
* char a[] = "11";
* char b[] = "1";
* char *c = bstradd(a, b); // c is a pointer to "100"
2 分层遍历二叉树
前两题. binary tree level by level，用两种方法来解决。
第三题. 3-Sum，找一个数组里面是否有3个数加起来等于0.
1. Palindrome String (LeetCode)
2. Sum3 (LeetCode)
3. Letter Combinations of a Phone Number (LeetCode)
Sum3还给了排序和HashTable两种解法
Onsite Interview：
一共三轮，每轮45分钟，因为是Master所以没有System Design：
1. 半轮Culture Fit的问题，另外一道Coding，Sort List (LeetCode)，要求In Place
，递归的解法要用到Call Stack，讨论了一下没想到更优化的方法，就写了递归Merge
的解法。
2. 两道Coding题目，一道可以化为普通的Binary Search，另外一道是Anagrams (
LeetCode)，都很快搞定，之后剩下将近20分钟就让我提问题了，随便聊了一下感觉还
挺愉快。
3. 先详细的问了本科的一个项目，之后一道Coding，
要求将Binary Tree以Inorder的
顺序转化为Circular Doubly Linked List，在递归Inorder Traverse的基础上做了些
修改，处理Corner Case的时候稍微花了点时间，
电面， 中国大哥， 问了一题，就是给read4k，实现read any bytes. 读大文件时如何
优化
onsite:
1， 美国人， 给一个词，判断是不是Palindome,
然后扩展问，给一个字典，找出所有对 单词，这两个单词可以组成一个palindom,
然后有问，可以组合任意个单词，怎么找到最长的可能的palindom
2, 中国大哥， 问了 permutation 和几种变体
3, 问现在的项目和resume
4, 美国人， 系统设计，设计各系统能返回 top 10 listened songs from your friends.
Clone graph
1. 一个manager 先聊behavior， 然后做了一个小题
isOneEditDistance 判断两个string是不是只差一个编辑距离。
2. 3Sum 变体，每个数字可以重复用。
3. System design设计手机上读取photo feeds的app。
功能： 读取好友的最近图片
阅览好友的相册
要求： 满足功能的同时减少对手机的能耗。
4. (1) 一维度向量相乘。每个向量很长，billion个数字。
(2) 多线程 reader 跟 writer 的经典问题。
加面
1. 求 LCA 两种情况，有parent结点跟没有parent的结点的情况都要回答。
2. search in rotated sorted array LC原题。
decode ways LC原题。
一个是分层打印二叉树，一个是老式手机键盘数字对应字母，给几个数字，求全部可能的组合
1. Find successor in BST
2. Find minimum number in a rotated sorted array (当时这个题还没在leetcode里，所以写得代码有些繁琐，估计因为这个要再电面一轮）
电面2
1. Insert a node into a sorted circular linked list ( all next element is larger except for the last one), the given head can point to any node
1 -> 3 -> 5 ->7
^ |
| |
| _ _ _ |
如果node的值是2，则插入1和3之间；如果node的值是8或者0，插入7和1之间。
要考虑node值重复的情况，虽然结果一样，但要和面试官讨论新的节点插入的位置，可
能插入在最开始或最后，我不记得了。
例如插入3, 结果是1->3->3'->5->7或者1->3'->3->5->7
2. Clone graph(leetcode)
第一轮：聊research，最后问了一题，
write a function f(x), so that f(x) returns true with x% probability。
第二轮：Given k sorted linked list, n elements in total, merge them into one sorted linked list。
经典题吧，但是居然在复杂度上卡了一下，给出的 log(k)*n的recursion解法。follow
up是如果不允许用recursion如何达到log(k)*n。follow up也没答好，提示是可以用
heap。
第三轮：convert a binary search tree into sorted double-linked list。
implement memcpy.
第四轮：System design。
Given a location (a coordinate), return top 100 nearest places.
Follow up, given a location, return top 100 events within x months in nearest places。follow up 其实就是多加一个时间维度。
提出的方案就是对平面坐标系做grid，每个grid里的locations放到一台机器上。搜索
的时候就是针对input的location找到候选的grids(以某个半径画个圆)，再从中通过
map-reduce找到前100个location。
可以根据grid里location的密度或者访问量决定是不是要再做partition以提高
scalability。
follow up的话就是多加一个dimension代表时间。
1. Palindrome String (LeetCode)
2. Sum3 (LeetCode)
3. Letter Combinations of a Phone Number (LeetCode)
Onsite Interview：
一共三轮，每轮45分钟，因为是Master所以没有System Design：
1. 半轮Culture Fit的问题，另外一道Coding，Sort List (LeetCode)，要求In Place
，递归的解法要用到Call Stack，讨论了一下没想到更优化的方法，就写了递归Merge
的解法。
2. 两道Coding题目，一道可以化为普通的Binary Search，另外一道是Anagrams (
LeetCode)，都很快搞定，之后剩下将近20分钟就让我提问题了，随便聊了一下感觉还
挺愉快。
3. 先详细的问了本科的一个项目，之后一道Coding，要求将Binary Tree以Inorder的
顺序转化为Circular Doubly Linked List，在递归Inorder Traverse的基础上做了些
修改，处理Corner Case的时候稍微花了点时间，感觉上可能栽在这一轮。
1） 国人大哥，culture fit半小时, 花10分钟象征性做了一个非常简单的回文。感觉
大哥人很好。
2） 国人大哥，非常简单的题矩阵相乘，然后follow up,涉及到tree， hashmap,
arraylist，也都很简单。 代码也得也都很顺利，感觉大哥人很好。
3）老印，最长的括号子序列。题不难，感觉这轮做得很差，老印提醒了2次，代码改了
几次， 虽然写出来了，老印最后照了相，知道挂了。
5）白人，设计一个在线图片编辑系统，完全没有经验，只能按版上的partition,
backup, cache等瞎说。边引导边回答。当面给的feedback都还算positive。
先聊了聊自己的经历，为什么要来fb之类的问题，因为我有图像处理的背景，就问了一
题相关的。
给一个2D board，上面由 0 和 1 组成，0 背景，1是图像，求里面有多少个连通域，
follow up 是每个连通域的面积是多大。我先写了recursive的做法。后来面试官又要
求了iterative的做法
第一轮：主要谈自己以前做的东西，面试官问得比较细，总之就扯了扯。问了一题
coding，给一个数组，问里面有没有两个数相加等于0，给了 O(n) time O(n) space的
做法，和 O(nlog n ) time和 O(1)space的做法
第二轮：给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个value
，面试官要求 O(1) space和 O(log N) time的解法。
第三轮: regular expression match, leetcode上原题，先写了 dp 的解法，面试官要
求我再写一下recursion的解法，写完后问了两个算法各自的复杂度
第四轮：design，设计手机系统，可以查看周围的好友，饭店，电影院等等
个人感觉fb面得题目的确不难，基本都见过，但是每道题基本上都问了很多种解法，问
得比较细，而且一定要bug free，这个比较难做到。面经就大致这样了，大家加油共勉
第一次是个同胞面试，题目是给出一个数组s和一个值y，找出s当中最长的sub数组的长
度，使sub数组的sum等于某一个值y。磕磕碰碰，同胞提示了两个关键点做出来了。但
由于做的不是很顺畅，F家决定再让我电面一次。
第二轮遇到一个烙印，由于之前没啥准备，突击了一周的数据结构和算法。没想到烙印
一上来第一个问题居然是问我一个概念问题，什么叫Big and Little Endian。我没答
上来，于是烙印就说算了。我奇怪为啥问这个问题，他说所有熟悉C++的人都应该会这
个。我说我没在简历上写我会C++啊，他说他看到第一行写的就是C++。最后随便给我一
个题叫我写了个binary search结束。
我回头再看我的简历，我的确没有写C++，我只说我有些VC#的经验。想起来真有些郁闷
，其实Big and Little Endian的概念也不复杂，回头看wiki几分钟就搞明白了。
1. Level-order traversal of bst
2. Deep clone linked list with random pointer
3. Divide without division
其实没面好，每题都被他找到了bug，而且最后一题的二分法解法是被他提示才做出来
的。最囧的是他提示我可以用二进制来算1/2以后我直接说，对不起啊我二进制实在不
熟。。。
两题都和Longest consecutive sequence相关。第一题秒杀，第二题居然没想到用
HashMap......我当时做LC的时候一下就想出来了。。。这次居然没想到。。。
还好，大哥一直在引导我思路（但没有任何直接的提示），最后我豁然发现了我思维盲
点，马上hashmap秒杀
1. binary addition
2. regex matching
正则表达式那题我哭了，我leetcode刷了147题，这题就在我没写的那7题里面。。。
跟着比较糟糕的思路写了好久，最后发现写不下去了。。。撑到最后姐姐提示我用递归
，于是我大概再重新说了一下这题的算法，但是代码显然是没法写了。。。
1. fib(n)你说这不是放水那啥叫放水
2. 直方图找最大矩形
3. 面试官一直在重复这是附加题。。。
n个数，没排序，怎么找第k个；然后n大的一台机hold不住的时候怎么办
先问了Rotated sorted array，我可能是之前和她聊behavior说得太嗨了，直接和她说
我做过。。。
后来问了一个简单版的Edit distance，给了个O(n)时间O(1)空间的解法。写完了她和
我说有个bug，我自己检查后改了bug，然后她接着问如果我不改的话哪种test case会挂
总体来看我觉得我有两轮面的应该不错，但另外两轮就难说了。Regex没做出来和
HashMap反应太慢始终是我的一个心病啊，觉得我肯定要挂了但是又忍不住不停地找
good signs来麻痹自己。于是来发个面经，求版上众牛bless!!!!!
1. 9月中旬进行了一轮facebook电话面试，一开始问了一些behaviour question，主要
是why do you want to work in fb? 这是我第一次面试，还是英文，没准备过，于是
随口乱说了一通。然后让我在colledit上写程序，其实就是拓扑排序，不到5分钟就写
完了，面试官在那边沉默了一段时间，然后说ok。然后就问了下简历上的一个项目，整
个过程不到30分钟。
fb电面完后第二天hr说10.1进行onsite，并告诉我why do you want to work in fb?这
个问题该怎么回答，另外还要我要好好练习英语口语。
一个题目是关于穿线二叉树的，另外一个题目是copy a link list with a random ptr，相信大家都见过这个题目。
判断一堆线段是否相交，3 sum zero, 实现next_permutation，然后一道数学题（无限大棋盘的跳马问题，时间不够，没做出来）。
第二轮的面试官自我介绍完后跟我聊了很多我研究生期间做的东西，以及简历上的一个
项目，然后让我在纸上实现字符串查找函数strstr。这个时候我没马上写代码，而是告
诉他有很多算法可以做这件事情，比如有naive的，或者比较高级的，然后他马上说
naive的就ok了。写完后，他问我刚才提到有比较高级的算法？我就给他解释了下kmp。
之后他又开始扩展这题，说如果待匹配的内容很大并且不会变，但是有很多模式串怎
么办。我给了说了2种算法，一种是把待匹配串的所有后缀都插入到一颗TRIE树种，另
一种是利用RK hash函数（这种算法需要假设模式串的长度都不会很长）。
第三轮大部分时间都在聊项目以及以前的一些经历，最后快结束的时候让我写了2个程
序，一个是数的进制转换，一个是在一个BST中求第k大的数。。
7. 10.11号google onsite，在上海进行的，上午2轮，然后在那边吃午饭，下午再进行
一轮。onsite的题目不便多讲，有一题在昨天的某个帖子中已经提到了(binary tree
max path sum)，另外值得分享的一题是给定一颗完全二叉树的根结点，求这颗树的结
点数。这个题大家可以想下。
电面
1.判断一个树是bst
2.给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个
数组中的节点所构成的树是tree
Onsite
1.介绍background，各种讨论
2.一个有序数组被rotate过，判断rotate的距离。考虑无重复和有重复
3.设计题。设计一个shorten url的service。讨论包括design，scale，各方各面
4.N个数中拿出K个数的组合并打印出来
5.二叉树的Deserializing
面完之后感觉很好，聊的也都很开心，题也不难，答的也很顺利，昨天接到电话还是有
点失望，要move on了。
各位也都加油！
1. Leetcode原题，three sum的变种, 允许3个数字重复，就是起始位置一样就行
2. 给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎么做
3. f家面筋出现很多次的小偷偷钱题，用DP，要求不相邻的数的和最大
4. 给一个tree，用递归变成一个circular doubly linked list
5. 还是f家面筋出现很多次的read4K那题
--
第一道是经典题给很多（millions以上）个点，以（x，y）坐标表示，找出离原点最近
的k个点。k 远小于 n。
开始还想了一会儿，后来想到用priority queue来做，问了时间复杂度是nlogk。面完
后问了一下别人，发现是可以用selection做的，更快。
第二道比较tricky给是一个string和一个alphabet，找出包含所有alphabet的最短的substring。
我的方法是用hashset保存alphabet，读string，每遇到一个字母，就从
hashset里面移除对应字母，最后如果hashset为空则string包含所有字母。在面试官提
示下发现可以试着缩短这个string，再check是否包含所有字母这样子做，code写完了
没有多余时间优化，大致讲了一下思路，就结束了。
另外求leetcode 和CC150之外，如何找到这种题练？感觉这个难度还是比leetcode平均
难度高一些啊。
1. a) 给出加密的方法'a'->1, ……, 'z'->26. 给一个数，问有多少种解密的方法。
b) 给你n个用户和k,找出发帖数最多的k个用户。
2. a) 给你棵二叉树，节点上有权值，问从一个叶子走到另外一个叶子的路里面权值最
大的那条是什么。
b) 给你数组a1,a2,...,an。输出数组a2*a3*...*an, a1*a3*a4*...*an, ..., a1*a2*...*an-1.
3. 问简历，问来想做什么工作。一道coding题：Read4k，leetcode上那道“Read N
Characters Given Read4”类似。
第一面system design. 先问怎么求submatrix的和，回答说先预先计算好 (0, 0), (i,
j)的和，然后可以用这个和求其它的和。以为他会顺着这个问数据大了怎么design
system，结果没有，问了个跟这个题毫不相关的，
怎么检测一个程序为什么慢。然后就回答先确定bottleneck是cpu, disk io, 还是 network io. 然后针对每项他都详细问
怎么做。交流的过程中有时候没太明白他的问题吧。反正这一面的结果很不好，当天就
给我加了另外一面system design. 最后还是挂在这一面上。
第二面coding. 先是 best time to buy and sell stock. 因为之前练过，讲了下思路
就直接写了最优代码。然后他又让写返回两个index 的代码，这个时候有点慌了，因为
没练过这个。。。然后慌忙中还写出了一个bug, 他提醒之后才发现的。改完后又让写
另一个链表相关的题，单链表k个k个分组，反转奇数组。比如 link = 0->1->2->3->4-
>5->6->7, k = 3返回 2->1->0->3->4->5->7->6.
当时知道会写不完这个题的，所以就尽量先写构架，
把一些细节用函数代替。最后把构架的代码写完了，留了一个反转单链表的函数没写，
刚开始写这个函数的时候下一个面试官来了，就稍微讲了下思路。
第三面 director. 问了下为什么来facebook, 怎么处理conflict，然后跟项目有关的
技术问题。最后让写sqrt(x)二分算法的代码。
第四面 coding. 先问wildcard matching. 写了个暴力搜索的代码，问怎么优化的时候，说可以记忆化，记住中间结果。
然后下一个题。 实现一个iterator, constructer
传入一个二叉排序树，第一次调用next()返回最小的，第二次返回第二小的，第n次返
回最大的，以后返回null. 刚开始提了几个用O(n)空间的方案，都被他否定了，问他是
否需要O(1)空间时，他说不一定要是O(1), 那必然就是O(logn)了，所以就想到了思路
。其实就是树的中序遍历的非递归实现。把栈存到Interator里面，next的时候改变栈
的状态就好了。写完后有一个细节没考虑到，他提醒后改好了，另外constructor 和
next里面用了同样逻辑的代码，也被他指出来了，他还指出了代码里面一个很小的优化。
两个题目：
1.add binary,lc原题；
2.binary tree, print all paths from root to leaf.
题目都不难。两个题分别分析了一下复杂度，第2题折腾了半天还是弄错了，最后提示
之下改正过来了。
实现 Tree iterator， 接着问，如果要prev咋办。
1. 3sum
Given an array of integers
[1, 2, -3, 4, 0]
To find any 3 numbers in array such that they sum to zero.
eg:
1) 1 , 2, -3
2) 0, 0, 0
2. Q2: Given set of points in 2d grid space. Find a grid point such that sum
of distance from all the points to this common point is minimum.
eg: p1: [0, 0] p2: [3, 0] p3: [0, 3]
ans: r: [0,0]
sum: 0 + 3 + 3 = 6
for every other point sum to this ans greater than 6.
实在不知道是啥，乱说了个找mininum manhattan distance,然后赶紧临时google下，
貌似是找median，然后对方说能不能证明一下。。表示不会。。。
这题正解到底是啥？
给定一些不相交的区间和一个新的区间，要求合并起来
但问题是不让用新的vector/stack，也就是说要用constant additional space
如何不用recuisive的方法preorder遍历一个tree（tree 有多个不同的孩子）
给一堆F的用户，以及朋友关系，朋友之间的关系是双向的。问能否将朋友的关系图分
成两个partition。使得任何有直接朋友关系的两个人必须处在不同的partition里。
电面二面：
leetcode的手机键盘给数字，求各种字母组合的题。但是让给出recursive和iterative
方法。recursive很简单，iterative之前没写过，比较难想，当时卡了一会儿。后来写
出来了。
onsite五轮，每轮45分钟：
第一轮coding为主：先聊了下他的项目和我的research，几分钟的样子，然后写了个二
进制字符串相加的。另外一题是一个直角坐标系，上面和N个点，找出离原点最近的k个
点，就是top k问题
第二轮系统设计：让设计分布式的large scale的producer和consumer问题。就是有一
堆机器是producer，一堆机器是consumer。后来顺便写了一道coding题，范围变成是单
机的producer和consumer，实现produce和consume函数，其实就是相当于fix size的
cache的add和pop问题，不用考虑多线程
第三轮coding为主：写了道regular expression匹配的，leetcode原题。但是让优化，
当时刚开始没想出来，后来经提醒知道用memorize的方法。以前DP的题知道用这个方法
，这题从来没去想过，差点出差子
第四轮culture fit：主要讨论了research。后来写了个简单的题，三个数组，从三个
数组各取一数，找出和为某个值的组合
第五轮coding为主：三个color排序的题，leetcode原题。另一道是平面上一堆点，找
出四个点，使得四边形面积最大。刚开始想不出，后来问题简化成找三个点，使得三角
形面积最大。这题挺难的。后来没有coding这题
1. 国人大哥，问了几个常见题，最难的题具体细节记不清了，大概是01矩阵上的DFS，
随便聊了会儿直接拿到onsite。
Onsite
1. 白女，亚马逊manager出身的女工程师，主问culture fit问题，比如为什么想来FB
。Coding题是恶心的罗马数字。因为鄙视这道题所以没在leetcode上刷过，还好是简单
题，很快写出来了。
2. 一个搞后端处理data的中国哥们，问sort linked list。随手写了个merge sort过
关，merge的时候没用dummy node方法，if语句用的很多，比较蛋疼。讨论了一下具体
的算法复杂度，直接背答案的人估计会被考倒。所以说做面试题的目的主要还是掌握算
法并能灵活用于解题，不太可能所有题都能练到随手就写出最优算法bug free的程度。
4. 一个看上去很强壮的老美，广告组的，问设计题。FB用户每天发非常多的status
update，要求设计一个系统，能够对最近几天内的update进行关键字搜索。我回答建一
个index，每个单词对应一个status update id的列表，查询结果是取列表的交集。我
对大数据处理完全没经验，不清楚这轮会被鄙视到什么程度，反正从结果看是pass了……
5. 又是中国哥们，一看就像技术牛人。有两个长度为n的数组，分别存放螺钉和螺母。
它们之间是一一对应的关系，而没有大小相同的螺钉或大小相同的螺母。现在有个机器
人，它能拿起一个螺钉和一个螺母，试着把它们拧在一起。如果成功，返回0，如果螺
钉大于螺母返回1，小于则返回-1。初始情况下两个数组是shuffle过的，需要设计一个
算法让机器人帮你sort两个数组，使得两边相同index的螺钉和螺母是一对。
这题虽然不是新题但我也没见过，虽然上来就想到肯定得用quick sort的思路，还是一
时纠结住了。经提示才想出正确算法，是两边同时做partition。代码倒是很容易写，
写完后又被要求分析复杂度。
6. 一个亚裔带了一个围观的老美，两人加入FB的时间都不长。题目是在BST里找两个
node的LCA。我当时头脑发昏，写了一个common binary tree的解法，因为要处理各种
edge case，代码十分冗长。后来才发觉得他问的是最简单的变种，二分查找就行了。
快结束时就随便聊了，围观的老美挺能侃，虽然shadow面试理论上不应该说话吧……主
要谈及FB工程师文化，有没有类似于G的20%时间政策。他们说FB还在扩张期，没资源搞
跟主业不太相关的项目，比如自动驾驶汽车，但如果想的话可以参与其它组的项目。还
有就是hackason几天牛人能搞些cool的东西出来。一般都说FB比较辛苦，平时做其它
project的时间不会有多少吧。
面试当天，HR说她临时拉了一个人来面我design，开始以后，他问我准备做F啥项目，
我想了想，自己编了一个项目。。结果这个老哥来劲了。。不停的问我为啥觉得这个项
目可以做，为啥比现在F其他的项目好？对F有啥好处 等等。。。一直聊到最后5分钟，
他估计想起来要面design了。。问了一句，你准备怎么实现？ 我日。。我说了2句话，
第二个面试官就来了。。当时就想，估计要悲剧了！
第二轮又是纯聊天， 面试官是个manager，抓着我研究生做的一个项目不停的问。。还
好是我做的，不然真的被问趴了
第三轮和第四轮是coding， 这2轮我一共只写了 3段coding，
第三轮的coding 是 leetcode 原题，一个数组，输出所有子集，有重复，没重复，迭代和循环都写了，bugfree 没啥问题。
第四轮，我脑抽了，找n个二维点中离原点最近的k个点。我的partition写的有点卡，最后写完以后 时间居然就到了。。而且面试官还抓了一个小错误：本来要输出k个，我输出了k+1个。。。当时我满头黑线。。。
You have two arrays X and Y. Each are having say M and N elements already
sorted increasingly. We have to find the k-th largest one of the whole set
M + N elements.
- Simple regular expression match，可以match的符号只有3种：
a-z : match a-z
a+ : match any numbers of a
.+ : repeat 1 - arbitrary times
和没用过regex的同学解释一下 例如
a+b 可以match : ab, aab, aaaaaaaaaaab
b.+b 可以match : bb, bab, b12345b
- boggle puzzle 找到里面所有的单词，写code
- Given preorder of a binary tree, print out all the binary trees
Leetcode 原题 decode ways
翻转链表。说实话我还挺意外的，我给出了一个非递归的实现，然后follow
up，他让我写个递归的，我只得另造一个函数。非递归的我应该写的没问题，递归的出
了点小bug，他给我一个用例让我测一下，我看了下发现确实有问题，迅速改对了，他
表示OK。然后又是follow up，问我当链表很大的时候递归方法有什么问题，我告诉他
会导致堆栈溢出。他继续OK。
技术题2. Leetcode的sort color，没什么好说的，只不过leetcode的原题类型是int，
值只有0 1 2，他给的是类型是个对象，然后通过getCategory()获取类型，只会返回1
2 3三种。实际上就是一个题。这个题前两天刚做过，迅速bug free之，他继续表示OK。
技术题一共就两题，完事儿之后常规性让我问问题。我问的跟上回G家问的差不多(懒得
再准备新问题)，一个是F家有没有跟computer graphics相关的组，一个是F家用不用敏
捷开发。他说了挺多。
第一题leetcode原题isPalindrome，只考虑字母。写完了之后题目要求稍微有个改变，
所以我相应改代码，改完有个小bug被指出，但是还是改过来了。
第二题也是原题，Tree Level Travel, 写了DFS的算法，又写了BFS的算法。
原来说好45min的最后到1个多小时，不知道是不是好事。
最后也是惯例问有没有什么问题。
1. median of integer stream. 没写代码，讲了下思路和数据结构……这题版上有讨
论过，非常感谢！ http://www.ardendertat.com/2011/11/03/programming-interview-que
2. 在一个x轴上，有很多矩阵，这些矩阵下面的那条横线跟x轴是重叠的……矩阵之间
可以部分重叠或者一个矩阵被另一个矩阵完全覆盖……要求输出最后图像的轮廓……不
知道描述清楚了没有…这题没写代码，讲了下思路……
3. 给了一堆开会时间, (si, ei), 开始时间和结束时间……判断是否可以只用一个会
议室满足所有会议.注意，(4,5), (5,6)……这个输入返回true……
4. 同样的一堆会议时间，返回最少需要多少间会议室.
0. 给定一个双向链表，以及一个数组。数组里存着一部分链表节点的指针。问数组里
的指针们指向的节点在双向列表中可以分成几个连续的blocks。接着问如果是单向链表
怎么做。算法复杂度分别是什么。
1. coke machines。大中小三个可乐机，每按一次出可乐量分别在[Amin,Amax], [Bmin
, Bmax], [Cmin, Cmax]之间，但不能确定具体容量是多少，现在想通过按这三个可乐
机，达到容量为[D, E]之间的可乐，问能否做到。也就是能否找到非负整数x, y, z使
得x*Amin+y*Bmin+z*Cmin>=D并且x*Amax+y*Bmax+z*Cmax<=E。感觉是个扩展的背包问题
，我给了穷举法和DP的解法，不过面试官最后说有个复杂度不依赖于D和E的解法，现在
也不知道怎么做。
2. 二叉树遍历。每个节点有left/right/parent指针，只允许使用O(1)空间而不用栈。
3. 含有大量URL的文件里查找频率最高的K个URL。先给单机哈希表的解法，内存不够的
情况，给了按哈希值把大文件拆成小文件的解法。接着被问并行化，给了MapReduce的
解法。接着被问哈希表相关的计算题，M个slots的哈希表（哈希值范围是1~M，用链表
处理冲突），往里放了N个元素，假设他们的哈希值是随机的均匀分布，问slots里元素
个数的分布，也就是balls and bins的问题。不用coding。
4. 链表的插入，删除等，基本没算法，而是看coding的细节。
5. 多线程和多进程。包括哪些状态是线程间共享的哪些状态是每个线程自己的等等。
不用coding。
decoding ways 没问题和 sqrt(double).
1. BTree求高度，宽度，某节点中序遍历下的Next，有parent节点
2 单链表倒序输出
3. Dutch Flag Problem
4. 给出一个排序好的字符串数组，给prefix，求所有前缀为prefix的字符串
5. 初始N个人，站在ROOM外，给一个move(i)函数，如果i在外面，move以后就到room里
，如果在里面，就移动到外面，要你给出一个move函数，使得N个人的所有子集在房间
中出现且仅出现一次，比如两个人，
初始 {}
move(1): {1}
move{2}: {1, 2}
move{1}: {2}
1. code部分题确实比较简单。可能比亚麻还简单。没有任何新题。大多数题在20-30行
之间，有一道可能要写40行。如果leetcode 上某题你需要写很多很多行那种被考倒得
可能性就比较小了。板上加leetcode全覆盖。在这种情况下做题得时候还是稍微激进点
。就是直接以最快得速度做最优得做法。我觉得我已经很快了。不过被问了改进外加额
外得coding,所以每个只能写两道。其实如果直接写最优的话可能能做三道。这样面试
得那张表格看起来会更满一点。电面得时候我做了三道。白板上还是很有压力得。鉴于
题可能会很简单。想脱颖而出可能这是一种方式。
2. behavior question还是要好好准备得。不要问得太肤浅。这个也可能事我挂得原因。
面试我得大概两个烙印，一个毛子和一个老美。感觉上一个老美最不友善。一个烙印比
较友善。另外一个烙印和毛子基本比较温和得态度。看不出来个倾向。当然他们得
feedback怎么样我是完全估计不出来得。
http://www.mitbbs.com/article_t/JobHunting/33003737.html
电面： 中国大叔面的，大叔很nice，遇到我写有bug的时候都会着急的提醒我，题也很
简单。
1： 给n个点找出离远点最近的k个， k<<n。
2: 给三个 api isSmall() isMid() isBig() 给一个array 排序，只要不被迷惑， 知
道其实是lc 上 sort color的变种就很简单了。
large scale下怎么设计一个根据关键词查询status的service。我自然又是一顿瞎扯，神马invert index, consistent hashing, 想到什么扯什么。 然而这并没有什么卵用。。不论扯到什么大哥都要刨根问底，我到最后就完全招架不住了。。大哥的表情也就越来越蛋疼了
http://yuanhsh.iteye.com/blog/2186421
1. There are n trees in a circle. Each tree has a fruit value associated with it. A bird can sit on a tree for 0.5 sec and then he has to move to a neighbouring tree. It takes the bird 0.5 seconds to move from one tree to another. The bird gets the fruit value when she sits on a tree. We are given n and m (the number of seconds the bird has), and the fruit values of the trees. We have to maximise the total fruit value that the bird can gather. The bird can start from any tree.
2. You are given the encoding for a base 58 number. You have to convert all the numbers from 1 to n to a base 58 number using the encoding given.
1st telephonic round
Introduce yourself and tell me about your projects. Then he asked me 2 algorithmic questions.
1. You are given the start time and finish time of n intervals. You have to write a a function that returns boolean value indicating if there was any overlapping interval in the set of existing intervals. (Sort and check, time complexity O(nlogn))
2. You have 2 sparse vectors (large number of 0’s). First tell me a way to represent and store them, and then find the dot product.(To store them, we should store the value and index of those indexes that have a non-zero value, and then finding the dot product is very straight forward).
2nd telephonic round
1. You have an array of n elements, and a sum. Check if any 2 elements in the array sum to the given sum. ( Expected time complexity O(n). Use hashing)
2. Extended the previous problem to sum of 3 elements in the array summing up to the given sum.
A few pointers:
? Always explain what you’re doing and why.
? First explain the algorithm and then start coding.
? If he gives a hint, take it and use it.
http://www.1point3acres.com/bbs/thread-125284-1-1.html? Always explain what you’re doing and why.
? First explain the algorithm and then start coding.
? If he gives a hint, take it and use it.
Given an integer array which has the property that all the elements having same value are adjacent to each other..
e,g, {2, 2, 2, 1, 5, 6, 6, ,7, ,7}
Output: Remove duplicate element in place and output the length of the new array. Do it in place and we don't care the elements outside the new length of the array.
e.g. return 5 and the input array will become {2, 1, 5, 6, 7, x, x, x, x} "x" means we don't care its value.
http://www.1point3acres.com/bbs/thread-142450-1-1.html
calculate the dot product of two very large arrays with many 0 elements. Be as efficient as possible
就是指给两个vectors, 例如{0,3,2} 和{1,3,5}。 那么dot product 就是 0*1+3*3+2*5 ＝ 19 。 那么如果每个vector 有millions of elements, 怎样优化 可以让 running time 比 o(n) 小
他只给我提示了 把A,B简化成list of tuple。然后我用two pointer 写的
首先是遍历array是必须的，我觉得面试官的意思是如何预处理完array后变得更efficient
A,B化简成list of tuples
(non-zero index, non-zero value)
然后two pointer扫就行
这个题应该还有一个follow up是如果A中有10000个non-zero, B中只有100个non-zero，这个时候就是binary search
http://www.1point3acres.com/bbs/thread-148865-1-1.html
求minimum cost的涂法，每个颜色有cost。。。问每个house涂什么颜色
BFS做的。。。不过给了hint
看做一个graph。然后分组。初始所有house都为group 0
用bfs遍历这个图。然后根据相邻house颜色不一样改变组号。。。
最后颜色根据cost排序，然后最大group的house涂cost最小的颜色，以此类推
2. consistent hashing
3. assign task with a random delay
http://www.40jy.com/archives/96
http://yuanhsh.iteye.com/blog/2186419
1. Code LRU cache (Lease Recent Cached) class.
2. Check if string is palindrome. Avoid using memory buffer
3. Use pattern in dictionary. Pattern may have * which means any character
4. Design Facebook feed system
5. Reverse a linked list in place
6. Merge two sorted arrays
7. Semantics
8. A^B (A carrot B)
9. Scripting Language Test
10. Intersect n Sorted Arrays
11. Remove all elements equal to a value in an array compacting the array
12. Dot product of Spare Vectors
13. Phone Permutations
14. Dutch Flag
15. Insert +get_median
16. Find 3 numbers in an array summing to 0
17. Max non-overlapping meetings (+ in K Rooms as well)
18. Binary Trees
19. Graph problems
20. Dijkstra’s algorithm (Daikstra’s algorithm)
Note: Dynamic Programming questions may also appear which are traditionally more difficult e.g. -"building bridges" (given pairs of cities lie on opposite sides of a river, what is the maximum number of "uncrossing" bridges that you can build).
Performance &Design Problems
Key Areas To Study (There is no coding in this interview, it’s purely discussion based)
NB: Engage in discussion with the interviewer, don’t simply answer the questions.
• Concurrency
• Networking
• Databases
• Systems Architecture
• Scale – think about big data problems you might face and solutions for them
Note:
Sample Questions
1. Sharding Solutions (CPU vs. memory scaling on the leaves, document vs term sharding)
2. Distributed Systems
3. How would you design a Facebook chat or a private search feature
4. Compute/publish real-time aggregates on ad impressions
5. Identify event subscribers based on registered predicates
Useful website to review for this interview: http://highscalability.com/
http://www.1point3acres.com/bbs/thread-130982-1-1.html
http://www.1point3acres.com/bbs/thread-148865-1-1.html
1. ninja: paint house大变种. n houses, k colors. neighboring houses cannot be painted with the same color.
NOTICE: neighboring relationship is given by adjacent list which means a house may have multiple neighbors.
求minimum cost的涂法，每个颜色有cost。。。问每个house涂什么颜色
BFS做的。。。不过给了hint
看做一个graph。然后分组。初始所有house都为group 0
用bfs遍历这个图。然后根据相邻house颜色不一样改变组号。。。
最后颜色根据cost排序，然后最大group的house涂cost最小的颜色，以此类推
2. ninja: 放水。 reverse Linkedlist (both recursive and iterative). buy and sell stock I, II (output transaction)
3. Jedi. behavior questions/research. coding: clone graph. give a class Graph, return 一个clone的
4. Pirate. Design Wikipedia crawler.
followup 1: No global status.
followup 2: deal with machine failure
followup 3: make the wiki site unaware of this crawler.
1. distributed bfs2. consistent hashing
3. assign task with a random delay
http://www.40jy.com/archives/96
第一轮，系统设计，不过这次的设计比较简单，是一个网站系统的设计，讲讲基础架构，搞搞分表，哈希，索引，负载均衡啥的关键字忽悠，然后过一过大致工作流程就算过关啦。还稍微比较了正索引和逆索引的优劣。
第二轮，coding，与LC的原题很类似的一题，不幸的是我想偏了，其实挺简单的，结果花了好长时间，不过最终还是搞出来了。算复杂度也是算不出来，在一顿提醒之后终于是搞了出来。唉，不是科班出身理论方面就是比较弱啊。。。
第三轮，行为问题，和领英差不多，为啥来脸书，为啥要离开原公司，之前干了啥，有啥比较自豪的项目，等等。最后来了一个coding，实在比较简单，略过。
第四轮，coding，LC的原题两题，外加一个引申题，算是三题，继续秒之。稍微问了下复杂度。
http://yuanhsh.iteye.com/blog/2186419
1. Code LRU cache (Lease Recent Cached) class.
2. Check if string is palindrome. Avoid using memory buffer
3. Use pattern in dictionary. Pattern may have * which means any character
4. Design Facebook feed system
5. Reverse a linked list in place
6. Merge two sorted arrays
7. Semantics
8. A^B (A carrot B)
9. Scripting Language Test
10. Intersect n Sorted Arrays
11. Remove all elements equal to a value in an array compacting the array
12. Dot product of Spare Vectors
13. Phone Permutations
14. Dutch Flag
15. Insert +get_median
16. Find 3 numbers in an array summing to 0
17. Max non-overlapping meetings (+ in K Rooms as well)
18. Binary Trees
19. Graph problems
20. Dijkstra’s algorithm (Daikstra’s algorithm)
Note: Dynamic Programming questions may also appear which are traditionally more difficult e.g. -"building bridges" (given pairs of cities lie on opposite sides of a river, what is the maximum number of "uncrossing" bridges that you can build).
Performance &Design Problems
Key Areas To Study (There is no coding in this interview, it’s purely discussion based)
NB: Engage in discussion with the interviewer, don’t simply answer the questions.
• Concurrency
• Networking
• Databases
• Systems Architecture
• Scale – think about big data problems you might face and solutions for them
Note:
Sample Questions
1. Sharding Solutions (CPU vs. memory scaling on the leaves, document vs term sharding)
2. Distributed Systems
3. How would you design a Facebook chat or a private search feature
4. Compute/publish real-time aggregates on ad impressions
5. Identify event subscribers based on registered predicates
Useful website to review for this interview: http://highscalability.com/
http://www.1point3acres.com/bbs/thread-130982-1-1.html
1 sort colors, O(n)时间, O(1)空间. https://leetcode.com/problems/sort-colors/
2 One Edit Distance, Given two strings S and T, determine if they are both one edit distance apart. https://leetcode.com/problems/one-edit-distance/
3 A set of points(x, y), 返回前k个离原点最近的点, 用k-selection 或者堆（代码见附件）
4 Flatten Binary Tree to Linked List https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
5 Remove Element 将一个01随机数列中，把1全部移到左边，要求移动次数最少
