Facebook Onsite Interview 11/17

Summary.
The facebook's campus is amazing and everything is really really cool.
No need to explain why it is the best in the world.
Totally attracted by facebook's culture and style. It should be the dream place for an engineer at least for me. You can do any project you like and you think it is worth. You can learn any technique if you want and will be given plenty of freedom and resource. No need to say the free food, free snack and free budgets. Incredible awesome.

Received offer at 12.02. Really  excited.

以下是面经部分。。

Just write as a self review use. Talking by reverse order.

Round 3.
A really enthusiastic Chinese manager who changed several position from front end to back end in recent 3 years in FB.
Given a BST and int x. Find the inorder successor of int x.
( If int x is not in the BST or x is the biggest element in BST return NULL).

Haven't known this problem before. Finished really quick that I even cannot believe I can do it so fast without hesitation.

Solution.
First find the position of int x in the BST and store the searching path.
If not find, return NULL.
Get the position of int x Node*
If p has the right child
     return the left most child in the p's right subtree.
else
     find out the most recent ancestor that p resides in the its left subtree.
Thus the find_x runs in logn and search back runs in logn. Memory uses is logn.

Then asked how to improve it. Find there is not need to store the whole search path. Just store the most recent ancestor is good. Thus the search back runs in constant time. Memory usage is constant.
(The only problem is there is a little bug nobody pointed it out but I remembered after the interview. When search back up to find the recent ancestor I didn't check if the path vector just has one element before iterate from the 2nd last element. Hope it will have no problem)

Round 2.
Only asked how;to add an interval. Implemented quickly by vector. Then asked how to improve it. I try to find out the segment tree or bst. So I tried to use the bst. Stucked. Then he asked what kind of stl could use. I thought he was asking something else then bst. So I didn't know. But finally he said he is asking the set. Ohhhhmy..... And then talk about how to use set to do that and the implementation of set. The advantage of AVLTree. Oh.... Not to bad. I should tell him that I misunderstood his meaning.


Round 1.
Terrible round. I didn't treat it as a behavior round interview because he just asked me about 5 minutes about behavior question. Your last internship. And how do you like team work. And why do you choose fb. I finally know this was behavior round because the following interviewers said you have already done the behavior one.
Asked two coding questions. Answered really really bad. Totally been disrupted.
1. Use 2,3,5 combine  to a target value and count the number of combinations. First I wrote
f[x]=f[x-2]+f[x-3]+f[x-5];
Then he said the order didn't matter which means (2,3) is the same as (3,2). So I wrote
f[x][k]=f[x][k-1]+f[x-a[k]][k-1] 
After his hint I wrote the right one
f[x][k]=f[x][k-1]+f[x-a[k]][k] 
Then I begun to implemented that. And use the dp storage as
vector<vector<int>>dp(target+1,vector<int>(3+1,0)); 
Then he asked how to eliminate the f[x][0]. At that time I was totally distracted because not doing good till so far. Thus wrote really bad at this question. The result was he didn't wait for me but wrote the answer himself. Then pointed out the f[0][0] should be 1.

2. From the node[x,y] can jump to [x+y,y] or [x, y+x]. Given a node calculate the minimum steps needed to jump there. I thought it was a DP because he asked me the minimum steps. So I wrote
f[x,y]= min( f[x-y,y], f[x,y-x] )+1
Actually I was totally wrong because there could be only one path from (1,1) to (x,y). Although he said me memorized search would work, I felt so bad about this round of interview.

Summary.
The facebook's campus is amazing and everything is really really cool.
No need to explain why it is the best in the world.
Totally attracted by facebook's culture and style.