timeline:
Oct23 内推提交申请
Oct24 收到Hello from fb的邮件
Oct28 预约第一轮电面
Oct28 发邮件希望延长电面时间，答复可延长一天
Nov7 第一轮电面
Nov8 悲剧
电面过程如下：
面试开始，面试官先做了个十分简短的自我介绍，然后就直接开始Code了。
第一题：
Diameter of Binary Tree
感觉沟通比较顺畅， 先询问细节，然后说自己思路，然后Code，边Code边解释，最后过了变Test Case.
面试官问了时间和空间复杂度。时间复杂度O(N)，因为遍历了每个Node一遍。空间复杂度最坏情况O(N)，每个Node只有一个child。
class Solution {
int longestPath;
public int diameterOfBinaryTree(TreeNode root) {
longestPath = 1;
height(root);
return longestPath - 1;
}
private int height(TreeNode root) {
if (root == null) return 0;
int left = height(root.left);
int right = height(root.right);
longestPath = Math.max(longestPath, left + right + 1);
return Math.max(left, right) + 1;
}
}
第二题：
给一个Integer的array和一个Integer K, K <= N,要求均等概率下从Array中选择K个Integer返回一个List。
因为题目似曾相识，但是一下对均等概率下怎么实现有点儿懵，想了一会儿，问了下面试官可不可以给些tips。
面试官说：选第一个数，你要怎么选？我：随机产生一个（0，2）的整数作为Index，返回。
[1, 2, 3] K =2
面试官说：比如第一个数你选的是2，那第二个数，你怎么选？肯定不能重复选2了吧？我：把2和数组第一个数交换一下，随机产生一个（1，2）之间的整数作为Index。
这时候我基本想到了solution，开始写代码了，code如下。但是期间面试官一直在敲键盘，没有第一题听得那么认真了。
public List<Integer>randomSelect<int[] array, int k> {
int index = 0;
List<Integer> ans = new Arraylist<>();
While(index < k){
int random = new random(index, array.length);
ans.add(array[random]);
swap(array, index, random)
index++;
}
return ans;
}
之后不知道是因为快到时间了，还是什么其他原因，这题没有过test case。面试官问过还有没有其他解法，我说没想到。
这题时间和空间复杂度都是O（K）
最后，面试官说还有几个小问题。就具体问了一下两个题的时间和空间复杂度为什么是那样，也都解释清楚了。