在之前的公司干了两年多，想要寻求新的挑战，所以两个月前向Twitter投了简历。半个月后得到Twitter的反馈，然后开始了为期一周的面试。
这次面试一共经历三轮电面和七轮onsite。中间各种忐忑，但好在最后拿到了offer，也算没有白费力气。
电面1:
首先面试官做了简单的自我介绍，然后问了之前做过的项目的基本内容。之后就进行了coding。
1.斐波纳契系列不使用数组 - 这是一个典型的最喜欢的问题，比如：动态规划，要求不使用记忆化或任何额外的空间来存储上一次迭代的值。
（更复杂的版本的同样的问题：使用二维数组N x N生成pascal三角形的第n行）
2.N元树：查找树中是否存在值为x的节点。如果存在，返回true，否则返回false。
电面2:
这一面的面试官主要对项目进行了深入探讨，考察之前完成项目过程中用到的技术，更为强调技术的深度。之后依旧是进行coding。
LintCode - 找到二叉树的最近共同祖先
LintCode原题链接：
http://www.lintcode.com/zh-cn/problem/lowest-common-ancestor/
参考答案：
http://www.jiuzhang.com/solutions/lowest-common-ancestor/
LintCode - 克隆一个图并分析时间和空间的复杂度
LintCode原题：
http://www.lintcode.com/en/problem/clone-graph/
参考答案：
http://www.jiuzhang.com/solutions/clone-graph/
public class Node {
public int data;
List neighbhors;
public Node (int data) {…}
setNeighbors(List neighbhors) {…}
}
// HashMap created = new HashMap();
public Node clone(Node oldGraph) {
if (created.get(oldGraph))
return created.get(oldGraph);
Node newGr = new Node(oldGraph.data);
List nbors = new ArrayList();
created.put(oldGraph, newGr);
List adj = oldGraph.getNeighbhors();
for (Node n : adj) {
nbors.add(clone(n));
}
newGr.setNeighbors(nbors);
return newGr;
}
电面3:
设计一个bloom过滤器，以从未排序的数组中删除重复项！
Onsite 1:
自我介绍之后简单进行一些询问，问了一些基础性问题，之后开始coding。最后探讨了程序的优化方案。
1.在数组中的2D数组（M×N，给定例子3×3）中，找到从指定原点（1,0）到指定目的单元（0,2）的严格增加的路径。数组可能包含重复元素，解决方案应该与dups配合使用。
Onsite 2:
这一轮主要考察 Coding能力，直接上来两道题。
1.为Twitter中的每个tweet设计一个唯一的哈希函数，将用作服务的一部分。
2.查找有向图是否有环。写一个函数，返回boolean，实现这个功能。
Onsite 3:
严格来说可能不能算正式面试，只是在午餐时间进行了简单闲谈，主要是谈过去的工作经历及对程序员这一岗位的看法。
Onsite 4:
对之前工作中遇到的问题的解决方案进行了询问，主要是针对问题解决能力的考察。
1.LintCode - 通配符匹配：使用包含字符（a至z）和“*”，“？”和“”的模式进行正则匹配。
LintCode原题：
http://www.lintcode.com/en/problem/wildcard-matching/
参考答案：
http://www.jiuzhang.com/solutions/wildcard-matching/
Onsite 5:
首先一上来就进行了算法编程，做完之后问了问之前在团队中和其他成员的相处情况，感觉是在考察交流和相处能力。
1.系统设计 - 如何进行外部排序，每台机器有10M的数（总共100M），10台机器。每个m / c具有20MB RAM和50GB内存。最后要求提供一个 map-reduce 的解决思路。
2.LintCode - N皇后问题：找到并打印皇后的所有可能的不相冲突的位置。
LintCode原题链接：
http://www.lintcode.com/zh-cn/problem/n-queens/
参考答案：
http://www.jiuzhang.com/solutions/n-queens/
Onsite 6:
这一轮主要是Coding，一共2道算法题，都有follow up.
1.LintCode - 二叉树查找树中序后继：给定输入二叉树和对树中的节点的引用，找到输入节点的下一个中序后继。如果没有，则输出null。
LintCode原题链接：
http://www.lintcode.com/zh-cn/problem/inorder-successor-in-binary-search-tree/
参考答案：
http://www.jiuzhang.com/solutions/inorder-successor-in-binary-search-tree/
2.进行k排序数组的最佳方式是什么？优化时间复杂性。
Onsite 7:
主要问的是系统设计方面的。
1.设计一个服务器。a.耐用性 b.一致性
2.解释C ++的多重继承问题。
之后问了对公司的看法、平时的业余爱好等。
