Monday, December 22, 2014

FB

Why Facebook?

12月9
Facebook onsite 问到的几个题目

1. moving all 0s to the beginning of the array， 直接答出 constant space 的解法

2. strstr()
KMP
3. wordbreak
告诉面试官有DP 解法, 告知我写递归.

12月4
Facebook onsite一周，HR说明天约电话，好紧张。面经：
1. Word Break.
2. Merge K sorted list
3. Word Search(可以斜着走)
12月2
1. is valid palindrome
2. find the maximum number in an integer array. The numbers in the array increase first, then decreases. Maybe there’s only increase or decrease. 先说了直接扫一遍，是O(n), 然后用binary search 就是O(log n).最后时间不够，没写完，应该是挂了。

1. behaviour question， 然后coding， strstr 还有
    直接上代码，然后讨论了两句结束。

2. 3 sum 还有 Letter Combinations of a Phone Number ，
    写完被要求对代码进行精简。

3. Edit distance，询问如何判断两个string 的edit distance 是否等于1，
当时第三轮脑子有点麻了。。。居然说先用dp算出distance在判断，
最后在面试官循循诱导下，想到其实只要扫一遍就行了。。。
呵呵，蠢起来我自己都怕。说完算法，还剩下不到5分钟，叫我赶紧写代码出来，
写得太赶被指出了有bug。。。估计就死在这上面了。。。诶，心塞。。

Facebook:
我觉得Facebook是有题库的, 因为当我面试完的时候, 回去看网上的面经和问其他onsite的同学, 重复度相当高. FB的题目都不难, 关键是代码要bug-free, optimal, 然后能多写一种解法就多写一种.
1.anagram, 输出一个句子, 里面的单词是空格隔开, 输出list of anagram in this sentence. 就是List<List<String>>.

2.sort colors, 三色旗问题, 用swap, O(n)时间, O(1)空间.

3.Pow

4.给一堆point(x, y), 返回前k个离远点最近的点, 用k-selection算法, 
核心就是那个partition, 平均时间复杂度可以做到O(n).

5.实现哈希表, 只实现lookup()和add()
//插入，这里假设是数组未满，即不能插入大于arraySize的数据数
14.public void insert(Item item){
15.int key = item.getKey();
16.int hashCode = hash(key);
17.//若已存在同样的数据，则向下进一位，直到找到空的位置
18.//为了简单，也可要求不准有重复数据
19.while(hashArray[hashCode] != null){
20.++hashCode;
21.hashCode %= arraySize;
22.}
23.hashArray[hashCode] = item;
24.}
//查找
40.public Item find(int key){
41.int hashCode = hash(key);
42.while(hashArray[hashCode] != null){
43.if(hashArray[hashCode].getKey() == key)
44.return hashArray[hashCode];
45.++hashCode;
46.hashCode %= arraySize;
47.}
48.return null;
49.

}

6.树的中序遍历和前序遍历的iterative代码.

7.二叉树的traverse by level和print in vertical order. 前面那个简单, 就是BFS, 后面这个要先遍历, 边遍历边给每个节点一个index, 比如root为0, 做left减1, right加1. 然后建立一个HashMap, key是index, value是list<TreeNode>

8.检测一个图是否是二分图, 就是BFS, 然后给每个节点上色.

9.找名人问题.

10.会议室问题, 给一堆会议室的schedule(starTtime, endTime), 算出需要几个会议室才能满足要求. 解法就是新建一个class{time, isStart}, 把schedule转化成这个class, 然后对这些时间进行排序, time相同时,end排在start前面, 然后对这个排序好的list进行遍历, 需要start, meeting_room_num++, 遇到end --. 得到max

11.给一个每行和每列都排序好的矩阵, 求第k大的数值. 可以用heap做.

12.Lowest common ancestor, 注意要写CTCI上面那个代码, 输入可能不来自同一棵树.

13.给一个span(min, max)和BST, 返回一个子树, 子树里面的节点都在这个span里面.

14.jump river的题目, 给一个数组[1,0,1,0,1], 1代表可以站, 0不可以站. 从速度为1开始往前跳, 每次跳的时候, 可以跳当前速度那么多格, 也可以跳当前速度+1那么多格. 问最少跳几次可以跳过河(即跳出数组), 或者跳不过河. 解法直接递归+cache就可以. 上面的例子跳2次就能跳过河了, 第一次从index=0, 速度为1跳到2, 然后速度为2刚好跳出去.

Facebook onsite的时候还有一轮Culture Fit面试, 除了讲讲你的简历, 下面几个问题经常会问到:
1.为什么选Facebook?
2.给FB的一个产品提点改进意见.
3.当你和你的同事有冲突了, 怎么解决? (focus on "let the code talk")
4.最近在读什么书?

8月
facebook一面，一个印度哥们，问了一个很简单的问题，从矩阵一段走对角线多少种走法，然后用组合数写了，然后加入障碍，然后用动态规划写了
二面也很简单，问了一道一堆数据，从一个开始之后是另外一个类型，然后binary search轻松搞定
然后onsite，一共3轮
第一轮，一个美国小哥，树的遍历，当然顺序是反向的，然后要求用另外一种实现（空间换时间），还有直接打印树中第n个节点
第二轮，还是一个美国小哥，打印所有树的path 使得sum为一个给定的树
第三轮，一个美国大叔，是manager，问了behavior，why facebook等等，然后coding写了roman number to integer. 
总结一下，问的都不难，但对coding要求很高，让你道OPTimize到极限，比如第一题，最后改成了4行。

只让用白色和红色两种颜色  好像是三块板子不能连着一个颜色吧。。。给一个栅栏上颜色，挨着的两个板子不能有相同的颜色，有几种染色方法，大概意思是这样

跑去脸谱家面试。搜集不少题目现在列下
1：print all path from root to leaf.  
2:  power set
3:  given a list of words, find palindrome pairs
4:  implement  BufferRead
还有一些简单题估计人家随便找的，祝好运。

11月21：
http://www.mitbbs.com/article_t1/JobHunting/32834537_0_2.html
三轮
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”类似。

前两轮基本bug free.第三轮被抓出些bug。

第二天得知面挂，觉得有点不可思议。


11月18：
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
（1，3）（2，6），（4，5）
1 2 3 4 5 6
1 2 1 2 1 0   <-- 走的过程中最大值就是解

11月16：
各种behavior question：
1. tell me about yourself
我就说了下intern的经历啊
2. what do you learn from your internship
我就说我学到很多啊，比如ownership啊，怎么把自己coding style fit in the team啊，怎么快速学习问题啊等等。
3. why facebook-google 
我就说两个，一个是facebook很牛逼啊make impact啊，之前那个facebook app在2012年之前还是很慢的因为是web base的
跟着后来就变得很快啊说明facebook一直都在进步啊，这时候jedi就说“哦！我当时也在那个组里面，我做的是那个阅览图
片那个模块。” 跟着我说第二个就是facebook的open culture很适合我，我之前的那个实习公司也很open，员工卡上没有title
大家的idea都能够交流。

总体来说我觉得behavior基本是秒他的，因为我觉得我准备了他可以问的所有问题了哈哈。跟着coding问题
字母和数字的转换 A = 1 B = 2 AA = 27 基本是26进制的转换， 他要我写了两个边的转换。 我写出来了不过最后我用的是
(char)('a'-1+i) 的方式来转换字母的，不过我用的是i%26，也就是z的时候会变成(char)(-1)。这个bug被他看出来了，跟着
他一个箭步上来帮我改了！！！加了个if。。。。跟着就说好然后走了。。。

第二轮ninja
一上来直接code，找小偷问题，有n个房间，其中一个房间有小偷。早上我们可以打开一个房间的门看小偷在不在里面，晚上小偷会向左边或者右边的房间走。现在给你一个开门的sequence，你输出这个sequence能不能保证找到小偷。
比如：如果只有三个房间那么如果打开房间的sequence是{1，1}那么一定会找到小偷。因为如果小偷在中间那么第一天就会被找到，
如果小偷在两边那么第二天一定回来到中间也会被找到。房间数为n，sequence长度为k
跟着我开始brute force假设小偷在某个房间然后dfs所有路径，大概是O（n*n^k）。 考官说好，如果考虑cut branch呢？跟着我就说可以.
拿一个n*k的matrix跟着根据sequence来cut branch，reduce到O（n*n*k）。他说有没有可能同时从所有房间开始呢？我说可以跟着直接
在那个n*kmatrix上做一个类似dp的东西。跟着reduce 到 O（n*k）。他说有没有可能把space reduce呢？我说可以我只要O（n）的space.
跟着他就让我再写一个叫nextRow的function来实现O（n）space。 我觉得这题我基本是答得非常漂亮的而且思路很清晰，考官也很开心。

CanSurvive[k][n] : 第k天，第n个房间小偷是否可以survive
CanSurvive[i][j] = CanSurvive[i-1][j-1] or CanSurvive[i-1][j+1] && sequence[i] != j

第三轮ninja
word ladder变型，叫我随便找一个可以的path出来，基本我写的每一步她都要我说这样写的理由，跟着做笔记。我用dfs+hashset写完之后，
被她发现了一个bug，就是在找到path之后我没有完全return导致答案没有了最后一个word，跟着我马上改了。之后她问我能不能cut 
branch-google我看不出来。。。。她提示其实放进hashset的可以不再remove，因为如果走过一个word发现这个word不行那么以后就没有必要再走这个word了。
跟着问我如果word可以从abc变道abcd 就是变一个或者加一个letter我应该怎么改。我就说加点东西就好，跟着就写出来了。跟着这轮就大概没了。

11月7
两个题目：
1.add binary,lc原题；
2.binary tree, print all paths from root to leaf.
题目都不难。两个题分别分析了一下复杂度，第2题折腾了半天还是弄错了，最后提示之下改正过来了。

1. Given an integer array, place all the zeros to the end.
{4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}

follow up：不care顺数的话尽量少用write，swap就行

2.The number of valid combinations of a strings for given input array a[], 
where a=>1, z => 26, and 0 <= a[i] <= 9

{1,1,1} => { aaa, ak, ka} => 3

{1,1,0} => {aj} => 1

follow up: O(1) memory

Iterator for in-order traversal of binary tree.  开始以为是iterative traverse in-order binary tree...还暗喜了一会。。 

class Iterator
{
    Iterator(Node *root){ }
    int value(){ }
    void next(){ }
}

11月3
Print a binary tree level per level.: use a null as level stopper: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/ 

Calculate the average of each level of a tree.   View Answers (3
level order traverse + average


how do you find the lowest common ancestor of two nodes in a binary tree.   View Answers (2)


you have a longggg list of words, return a list of distinct words along with the count of how many occurred using only 16gb of memory:  HashMap

  • K nearest points to the origin on a 2D plane; 
  • one-pass reverse linked list with constant space.   View Answers (3)

10月31：
Edit distance 
10月：
另外听说有同学面了 sorted color
还有二叉树转链表。

1st: Given a m * n grid and the coordination of left bottom cell is (1, 1) and the one of right top cell is (m, n). At each cell say (x, y), you have to choice to move, going up or right. If you go up, the destination is (x, x+ y). Otherwise your destination is (x + y, y). Find the minimum number of steps to reach the cell (m, n) from (1, 1).

2nd: Find k closest number in an array of a given value

Sorted Array: O(logn) + O(k)

3rd: Leecode minimum window

4th: Check if a tree is BST.

string 有多少palindrome substring。

single number，数组有序，要log(n)
行升序矩阵，找kth，分析多种方法
flatten二叉树
bfs遍历二叉树，从左到右返叶子节点

. 1point 3acres 璁哄潧
补充内容 (2014-10-13 20:34):
delete"bfs遍历二叉树"，post or pre order遍历多叉树都行吧

FB:
1. Fib数列＝ ＝｜
2. LC上那个phone number对应字符串那个
电面就问了一道题目，给了一棵二叉搜索树和一个数n返回树中的第n个元素。
1: find a maximum sum of subsets in an array, it is in CC150

他问的题是Dynamic Programming中最经典的问题coin change, 就是给定一个面额(比如100), 以及一些不同面额的硬币(2,3,5), 求所有的硬币组合, 使得他们的面额之和为100.

1. 三色排序，保持同类间相对次序。
2. plus one，输入输出都是int，不能用＋和－。

第一题先是用两次partition来做，代码，测试，big o都很满意，被要求只用一次for loop，想了一下引入第二个ptr，没有改代码就进入下一题了。

第二题只准备了输入输出是list的情况，于是主动把问题引到自己准备过的算法。很快描述过思路以后，考官说他是想考我bitwise operation，但是如果我不是很comfortable的话，加上我的解法和他心中的答案其实很接近，可以move on。写完代码后，他很开心的说没有问题，只是因为不能用＋，所以相应的操作只能用一个0－9的map饶了过去，代码长了点。
10月31：
1. longest common substring



2. OO Design, 把一个iterator的iterator转换成iterator
constructor:
List<Iterator> its = new ArrayList<>();
while(iteratorOfIterator.hasNext()){
   its.add(iteratorOfIterator.next());
}


hasNext():
while (its.size()>0 && !its.get(0).hasNext() ){
    its.remove(0);
}
return its.size()>0;

next():
if(hasNext()){
    its.get(0).next();
}
else{
    //error out or return null
}

1. Manager聊经历半小时 然后半小时coding: 给你一个read_buffer(char*buffer, 
int len)，用这个实现read_line()，完全设计这个interface. 
2. 给个数组，找出所有的三个数字trio, 加起来等于目标数字
3. 设计tinyurl
4. 给一个dict，然后一个长字符串，和长度len，找出所有长字符串里长度为len的在
字典内的子串。

10月30：
电面：美国男
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题里面。。。
跟着比较糟糕的思路写了好久，最后发现写不下去了。。。撑到最后姐姐提示我用递归
，于是我大概再重新说了一下这题的算法，但是代码显然是没法写了。。。

三面：国人男+shadow。而且他绝对给我放了水。。。
1. fib(n)你说这不是放水那啥叫放水
2. 直方图找最大矩形
3. 面试官一直在重复这是附加题。。。n个数，没排序，怎么找第k个；然后n大的一台机hold不住的时候怎么办
quick select
Jedi：亚洲女Manager，后来查了查姓氏，应该是印尼人
先问了Rotated sorted array，我可能是之前和她聊behavior说得太嗨了，直接和她说
我做过。。。
后来问了一个简单版的Edit distance，给了个O(n)时间O(1)空间的解法。写完了她和
我说有个bug，我自己检查后改了bug，然后她接着问如果我不改的话哪种test case会挂

总体来看我觉得我有两轮面的应该不错，但另外两轮就难说了。Regex没做出来和
HashMap反应太慢始终是我的一个心病啊，觉得我肯定要挂了但是又忍不住不停地找
good signs来麻痹自己。于是来发个面经，求版上众牛bless!!!!!

10月24：
电面：

1. 给一个2D board，上面由 0 和 1 组成，0 背景，1是图像，求里面有多少个连通域， 
follow up 是每个连通域的面积是多大。我先写了recursive的做法。后来面试官又要
求了iterative的做法：对每个没有visited的点进行dfs, visited 数组



Onsite
1. 给一个数组，问里面有没有两个数相加等于0，给了 O(n) time O(n) space的做法，和 O(nlog n ) time和 O(1)space的做法：Two Sum, hashtable (查找为O(1)) 或者排序+ 重新找index

2.给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个value，面试官要求 O(1) space和 O(log N) time的解法。：需要树有Parent指针。 如果结点有右孩子，找右子树最左结点，else, 找第一个把该节点当作左孩子的父节点


3. regular expression match, leetcode上原题，先写了 dp 的解法，面试官要
求我再写一下recursion的解法，写完后问了两个算法各自的复杂度

4. design，设计手机系统，可以查看周围的好友，饭店，电影院等等

10月23：



10月21：
就是两个超大的array, 有很多是0，求他们的点乘。

10月6：
  • Read4K
    二叉树转双向循环链表
Talk something about yourself, your project, your interests. And then moved forward to the code interview on Collabedit. The question is the simple 3 sum and pow().

Techical Question: Check to see if one array is a subset of another
Reverse a doubly linked list 


9月28：
1. Facebook电面
浪费了大几分钟开始第一题，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，不能用额外空间
Reorder list

第一遍用了recursive很快解决，被指出用了stack额外空间，开始改iterative，最后
因为第一题浪费时间手忙脚乱没改完。说了一下大概思路草草收场，面完就知道不妙。
4天后被通知挂了。



8月16：
电面：Clone graphonsite
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原题。

8月15：
  • Retrieve words from a dictionary that are made up of a subsequence of characters in an input string.
    i.e. given an input "ABAT", matching words may include "BAT", "TAB", non-matching words may be "BART" or "BAR".       View Answer
  • What is a memory-efficient way to store a vector of integers? Follow-up question: using your proposed data structure, find an algorithm with constant memory usage to calculate the dot product of two vectors.   View Answers (3)

8月1
给定一些不相交的区间和一个新的区间，要求合并起来
但问题是不让用新的vector/stack，也就是说要用constant additional space
  • Print a binary tree by vertical level order

    like

          1
       2 4
    3 5

    print :
    3
    2
    1 5
    4       View Answers (6)

7月11：
F:
1. Reverse linkedlist2. Tree => double linked list
3. Two sum, 考虑重复

6月29：
Print all paths of a binary tree
一个数组,一个target,求所有的pairs, array[i] - array[j] = k.

6月27：
面试的是个烙印，开始惯例问了project之类的。
第一题leetcode原题isPalindrome，只考虑字母。写完了之后题目要求稍微有个改变，
所以我相应改代码，改完有个小bug被指出，但是还是改过来了。
第二题也是原题，Tree Level Travel, 写了DFS的算法，又写了BFS的算法。
原来说好45min的最后到1个多小时，不知道是不是好事。
最后也是惯例问有没有什么问题。
烙印面试过程中一直没有feedback。没收到消息，还是很忐忑的。


6月23：
F 家 - offer 已从。

电面1： 国人大哥。题目记不清了。应该是leetcode。

电面2： 法国人。
Question 1: Merge two sorted single linked list -> leetcodeQuestion 2: Leetcode Regular expression matching变种: ".", "*", "?" 

On-site - 签了DNA 题目就不具体说了。
接待： 三哥HM, 白人shadow
behavior + leetcode

Ninja：白男
上来不废话，直接code。leetcode + 板上讨论过的题目

Design: 三哥 煮面， 白人 shadow （没来。。。）
基本上和准备的差不多，但是没见过。最后发现和面试官讨论出来的解法跟F家现在用
的基本一致。

（？）： 白男， HM (不知道为什么临时换人)
behavior + leetcode变种

加面： 亚裔，director level
behavior + leetcode

6月17：
1. 3sumGiven 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.  

6月15：
Leetcode 原题 decode ways

6月8：
阿三 男

1. 轮流介绍背景

2. 为何F,来了想干啥

3. 输入一字符串，输出一最长重复串 (比如AxyxyxA中xyx就是), 分析一般复杂度及最
坏情况下复杂度

4.（后缀词排序？）输入一字符串s，输出一整数组A。复杂度分析。
输入：s = "zxy"
0: zxy
1: xy
2: y
输出：[1,2,0]  

5. 提问环节


方法：两题都直接暴力之，每题到最后都被阿三叫停说可以了，不用编了。

反馈：三小时后通知onsite。


6月5：
刚面完,题是作出来了,但是开始的时候思路不是特别清楚,想这么做也想那么做,搞得面
试官有点糊涂.

题目很简单, 就是繁琐,career cup上有一道类似的,但是这个比那个更麻烦点

输入一个整数,输出他的英文读法
1 -> one
100 -> one hundred
500234 -> five hundred thousand two hundred thirty four
1232232 -> 1 million two hundred .....

说实话,有些大的数字应该怎么读,我都忘了, 问了面试官才知道million 后面是b, t, 
q

然后思路就是把这个数3位一组分好,然后写了一个function来读3位以内的数,读完以后
看他是第几组,然后就在后面加thousand, m, b 的之类的

5月22：
攒RP先,刚出炉的面经.面试官烙印,已经在里面工作5+年了.
寒暄5分钟
Q1.一个数组,一个target,求所有的pairs, array[i] - array[j] = k.Q2.降低时间开销,怎么搞?
头两个问题,写完烙印面试官直接粘贴代码本地跑,说没问题
Q3.一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] ->  a, b, c, ab, abb, bbc, bb, bc
Q3不用写代码,谈思路,然后把他的例子按思路走一边,走完他问时间开销.
问问题.
再见


4月8：
double sqrt(double d)

电面
1.判断一个树是bst2.给一个含有节点的数组，每个节点指向数组其他节点，或者数组外的节点，判断这个
数组中的节点所构成的树是tree

Onsite
1.介绍background，各种讨论
2.一个有序数组被rotate过，判断rotate的距离。考虑无重复和有重复
3.设计题。设计一个shorten url的service。讨论包括design，scale，各方各面
4.N个数中拿出K个数的组合并打印出来
5.二叉树的Deserializing

3月10日：
F onsite 有4轮，全是白人：
1. 问了一些behavior的问题，比如简历里写的项目什么的，然后还问了最喜欢
facebook app的哪个功能，有什么可以改进的地方，怎么改进。还有为什么想去
Facebook。这些问题我基本都已经准备过，所以应该都答得不错。最后给了一个简单的（和递归也差不多），还有就是先反转链表，按顺序打印，然后再反转一次恢复原状。面试官好像很满意，让我选一个方法写code。我说前两个方法都很容易写，所以我就选第三个方法。总体感觉这轮面得不错。

2. 这轮开始的时间完了5分钟，所以只面了40分钟，要求设计facebook iOS app的newsfeed，不需要考虑服务器端的情况，只需要说app端的实现方法。这个我之前稍微准备了一些，可是从来没有面过系统设计题，实在不知道应该怎么说，而且不知道会被问得多深入，所以基本上一直是很被动的跟着面试官的指示走。画了几个框框以后就开始被问各种细节，比如从服务器读数据的格式是什么，写一下json的example，界面和后台怎么传输数据，等等。总体感觉这轮答得不好。回去后想了一下，感觉回答的方式有些问题。比如说实现一个功能有两种方法A和B，他问我用哪种方法，我就直接说我倾向于用A。这种答法很不好。应该先说清楚A和B各有什么优缺点，然后我选A是因为什么。这样的话就会让人感觉我对于A和B都了解的比较多。

然后中午吃午饭，我跟recruiter说了第一轮不错，第二轮的设计不好。他说没关系，只要下午的两轮都答好了就没问题。不过现在看来，设计题还是非常重要的，因为问设计题的一般都是比较senior的人，所以估计他们的意见比较重要。（这只是我的想法。）

3. 又问了一些最近的项目的问题。这些都是warm－up questions，所以都只需简短的回答。然后出了一个编程题：有两个一样的树A和B，每个节点都有父指针，要求写一个函数，参数是A的一个子节点x，和B的根节点，要求返回B中对应x的那个节点。也就是说A的根节点未知。这题挺简单，所以我没怎么想就说了先找到A的根节点，然后同时对A和B做一个DFS或者BFS来找出B中对应x的节点。面试官说可以，让我写代码，写完以后分析了一下复杂度。然后就问有没有更好的方法，我马上就意识到不需要用DFS或者BFS，只需要在找A的根节点时记录下当前路径就行了（只需记录每个子结点是父节点的第几个孩子），然后按同样的路径扫一下B树。复杂度只有O（height），面试官好像还很满意。这轮面试没有一下就想到最优解，所以我还比较担心会不会结果negative。

4. 上来又是先问了一些项目的问题，然后拿出电脑来让我看一段程序，找出里面的不合理或者有错误的地方。我说了10分钟，每说一个错误他都记下来，最后他说可以了，已经写满一页了。然后出了一个编程题，要求用trie tree进行字符串匹配，字符串里有可能有‘？’，代表任意一个字符，trie的结构是面试官给的，也不需要构造tree，只需要使用就行了，所以还是比较简单的。写的时候有一个小错误，在测试时候发现了就改正了。总体感觉还不错，应该比第3轮答得好一些。

3月：

Intereleaving 2 linkedlist


2013：
1. 白女，亚马逊manager出身的女工程师，主问culture fit问题，比如为什么想来FB。Coding题是恶心的罗马数字。因为鄙视这道题所以没在leetcode上刷过，还好是简单题，很快写出来了。
2. 一个搞后端处理data的中国哥们，问sort linked list。随手写了个merge sort过
关，merge的时候没用dummy node方法，if语句用的很多，比较蛋疼。讨论了一下具体的算法复杂度，直接背答案的人估计会被考倒。所以说做面试题的目的主要还是掌握算法并能灵活用于解题，不太可能所有题都能练到随手就写出最优算法bug free的程度。
3. 午饭不算正式面试，跟一个呆了六七年的front end developer谈话。他说话有气无力，感觉生命都被FB榨干了一样，最终也没聊出什么有意思的话题来。
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的时间不会有多少吧。

Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)