Facebook的算法题目难度中等，大多出自LC原题及其变形，并且相当大比例出在题号前300的范围之内。面试过程中注重代码的速度和bug free，通常会要求面试者自己想一些 test case。
1. Two pointers
常见于String和Array相关题目, 相对来说比较容易，通常放在面试第一题作为开胃菜（楼主店面就碰到过valid palindrome这题，写循环的时候还卡了一下= =），建议练熟速战速决
Longest Substring Without Repeating Characters, 3 Sum, 4 Sum, Sort colors, Minimum Window Substring, Merge Sorted Array, Valid Palindrome, Move Zeroes, Is Subsequence
2. Binary Search
如果在给出线性时间解之后被要求进一步优化复杂度，二分查找是一个通常需要考虑的方向（楼主上个月店面被问到一题Find Peak Element 的变形，从开始的linear scan 优化到了recursive binary search)
Divide Two Integers, Pow(x, n), Search in Rotated Sorted Array II, Kth Largest Element in an Array, First Bad Version, Intersection of Two Arrays, Intersection of Two Arrays II, Custom Sort String
3. Binary Tree / Binary Search Tree
tree相关的题目也是FB常考的，其中一大类是关于_tree traversal_的：
Binary Tree Inorder Traversal， Binary Tree Vertical Order Traversal，Serialize and Deserialize Binary Tree， Binary Search Tree iterator, Inorder Successor in BST
还有一类是关于_path/path sum in the tree_的：
Binary Tree Paths，Binary Tree Maximum Path Sum
找特殊的 node / node value：
LCA of binary tree, Closest Binary Search Tree Value
需要自己建BST进行binary search:
Count of Smaller Numbers After Self
对binary tree 进行转换：
Convert Binary Search Tree to Sorted Doubly Linked List，Invert Binary Tree
平衡树：
Balanced Binary Tree
4. Intervals
高频面经题包括 Merge Intervals, Meeting Rooms II
5. 若干超级高频题
Subarray Sum Equals K，用preSum的技巧结合hashmap的方法去做。
Integer to English Words，对不同数值范围分类讨论，注意边界条件。
Remove Invalid Parentheses，可以用DFS做，注意删去多余的右括号以后需要将String反转将多余的左括号也删去。
Serialize and Deserialize Binary Tree， DFS和BFS都行，空间和时间复杂度相同。
Next Permutation, 从末尾往前沿着数字逐渐变大的序列到第一个减小的数（记为a）停下来，再从末尾往前找第一个比a大的数（记为b），交换a和b，再将b后面的数逆序排列。
6. Graph
作为一家社交网络公司，FB也很偏好考察图一类的题目。经典的题目包括Alien Dictionary, Clone Graph, Course Schedule, 等等。但这一类题目在店面中出现频率不高（毕竟短时间内很难写出来）
7. DP
动态规划一直是算法题中偏难的一类，但同时也是套路性最强的一类（initialization，deduction formula, space improvement 三部曲). 比较高频的题目有：
Continuous Subarray Sum，Maximum Sum of 3 Non-Overlapping Subarrays，Regular Expression Matching， Decode Ways， Range Sum Query 2D - Immutable，Longest Increasing Subsequence，Is Subsequence
8. BFS, DFS
两种最常见的遍历算法（题目和上面的板块会有部分重合）
与tree相关 :
Symmetric Tree，Flatten Binary Tree to Linked List，Binary Tree Maximum Path Sum, Binary Tree Paths
与graph相关：
Walls and Gates, Is Graph Bipartite?
其他：
Remove Invalid Parentheses
9.
一共四轮，两轮算法，一轮设计，一轮behavior。第一轮算法，中国小哥，先问了一个题目热身。如何判断一个字符串是否可以转换成为回文？热身过后，问了嘶迩馏原题。
第二轮系统设计，有许多的点(x,y,data)，x,y是经度和纬度。设计一个系统来查询一个位子和半径内所有的点。问题有点像Uber。完全是在扯。
第三轮是算法，中国小哥，给的都是标准的题目。一个树，给一个目标节点，找到所有到目标节点的距离小于K的节点。给了提示，太感谢了。还有一个是设计所有的数据结构，插入，删除，查询，最后一个都是O（1）的系统。
10
two sorted array intersection, 本能反应说了hash map, 然后小哥说constant space, 改成了 two pointer。 follow up，降低时间复杂度，用的binary search。follow up, 如果输入有重复的，要求输出无重复。然后再follow up, 输入有重复，输出无重复，然后分析了一下复杂度。
11 (SDE Intern, master)
第一题，栗叩680
第二题，给定26小写字母自定义排序，判断字符串（只含小写）是否已根据此排序sorted。
12
三轮店面(pass)：
LC一流儿 但是是找max，后续问怎么证明你这个bs的正确性，再问了如果是strict max呢（必须比左右两边都大，等于不行, 后面找strict max的时候想着找O（log n），面试官看我折腾了半天没出来，说只有O（n），必须全走一遍，谢谢放我过TT。
LC流散 不是这一题，但是是一个极端变种，我感觉我看过有人做过但是找不到了，大概就是长方形格子，里面有各种block，能上下左右移动，找（从任意位置开始能达到的最远距离）里面的最小的. 完全没做出来，就搞了个最次的暴力流+dfs，但是没写完时间不够了，中间写错了几个地方，面完感觉已经move on了
LC儿吾儿 但是先问的是给一串intervals和一个新的interval，怎么判断新的interval和前面的有没有交集，假设前面的都没有交集
LC一散散 原题
13
电面： 中国大哥，找第k大数字，follow up，如果是数据流怎么办？
onsite三轮，
第一轮： 美国小哥， 第一题，找到第一个坏掉的版本。 第二题， 一堆杂七杂八的括号不成样子，请把他们删一删，变成一个合法的括号序列（只要一个就可以）
第二轮： 美国大光头老哥， 问了bq，请你手写一个比较器， 比较规则是啥？大方向是字母排在数字前， corner case讨论着写。
第三轮： 美国nerdy小哥， 给了俩排好序的数组，一个的长度恰好是另一个两倍，长的那个数组后面一半都是null， 让把两个数组合并到长的里面去。 第二题，同样的问题，变成了k个数组。
14
两轮店面
第一轮两道题，第一道diameter of binary tree, 第二道是k nearest points to the original point.
第二轮 第一道return starting index and length of the longest non duolicated consecutive substring in a string, 第二道是判断 ‘{}()]’ 类似这样的字符的括号是否valid.
15 (SDE fulltime, master)
设计一个class来 计算稀疏矩阵乘法
16 (ML intern, PhD)
- 要求判断一个BST是否balanced，如果不是转化成balanced的。
- 第二轮是经典题，intersection of two arrays，讨论了一下two pointer和binary search的优缺点。
- 加面只有一道，没follow up倒是：利口齐尔腰。
17 (OA, Solution Engineer)
蠡口亮散吧原题，不过题意描述和给的boilerplate有很多不符的地方，比如题中要求返回vector，但是boilerplate给的返回类型却是int，尽量根据题意改了改，写了一堆comment和test case。
18 (SDE intern, Undergrad)
一面11.26
Task Scheduler简化版 cooldown一定并且只在相同的task之间有
Trapping Rain Water
二面12.13
Subarray equals k
Open the lock
19 (SDE fulltime, master)
跟wildcard matching 差不多
檢查P 在不在L 裡
其中 * 在p代表任何字符
L: [“foo”, “bad”, “boy”]
p: "fo" -> true
. 1point3acres
p: fi -> false
20 (5-31 Onsite)
类似LC62, 但要求枚举所有路径([‘DDRR’, ‘RDDR’, ‘DRDR’…])并分析run time
21 TopK Closest Points (5-30 Phone interview)
LC973
22 Shortest Path with Obstacles (5-29 Phone interview)
Given a 2D matrix where some of the elements are filled with 1 and the rest of the elements are filled with X, except 2 elements, of which one is S (start point) and E (endpoint). Here X means you cannot traverse to that particular point. From a cell you can either traverse to left, right, up or down. Given two points in the matrix find the shortest path between these points.
For example, if the matrix is
1 1 1 1 1
S 1 X 1 1
1 1 1 1 1
X 1 1 E 1
1 1 1 1 X
One of the shortest paths (from E to S both exclusive) is: [(3, 2), (3, 1), (2, 1), (2, 0)]. Return null if there is no path between S and E.
23 Possibility of user moving from one page to another (5-24 Data Engineer Onsite)
Given a log file with data like:
USER FROM_PAGE TO_PAGE
A url1 url2
A url1 url3
B url1 url3
A url2 url3
…
…
url can be string like www.leetcode.com/activity/xyz
Return the possiblity of any user moving from one page to another page
Ex ouput should be like:
user A:
url1 —> url2: 50%
url1 —> url3: 50%
url2 —> url3 : 100%
user B:
url1 —> url2 : 100%
24 (5-9)
Given an integer n , create an array such that each value is repeated twice.
Input: n = 3
Output: [1, 1, 2, 2, 3, 3]
Follow up 1: After creating it, find a permutation such that each number is spaced in such a way, they are at a “their value” distance from the second occurrence of the same number. Return any 1 permutation if it exists. Empty array if no permutation exists.
Input: n = 3 --> This is the array - [1, 1, 2, 2, 3, 3]
Output: [3, 1, 2, 1, 3, 2]
Explanation:
The second 3 is 3 digits away from the first 3.
The second 2 is 2 digits away from the first 2.
The second 1 is 1 digit away from the first 1.
（未完待续）