坐出租

         三天飞了圣何塞两次去面试。没有租车，尝试了下打车，头一次在美国打出租，坐了五六次，感觉算是出租行业，也是种族肤色分明。

         第一次落地圣何塞，上了一辆在机场等客的yellow cab，七年前从埃塞俄比亚来黑人大叔。从FB回机场是辆同样平凡的yellow cab，热情的巴基斯坦大叔开心的讲我们是邻居。再之后宾馆前台叫的yellow cab，同样平凡的小破车，边玩手机边开车的黑人小哥，索马里来美国淘金。。但是，同样是开出租，第二次到圣何塞，谷歌给租的车就完全不一样。出了机场，谷歌说派的司机已经到了。黑色林肯，西装革履的白人司机，问是F先生么。
         同样是开出租，白人就是开林肯有模有样高收入，其他的呢，就是又脏又累还挣不下钱的活。同样的技术同样的要求，却因为种族肤色不同而导致环境、收入迥异。作为一个亚洲黄种人，希望可以在美帝做到勇敢、做到自信。

Google Onsite Interview 11.20

Every interview in Google seems really lucky from the on campus all the way to this onsite interview .

Heard passing the on campus interview at the second day and was told some HR from Mountain View would contact with me. However one week passed still nobody contact me in the mean time others have already been contacted by the hr and started to schedule the onsite interview.

So I contacted with the university hr and one hour later a call came from Mountain View. It seems that he forgot me. He told me GTECH team was interested in me and would sign a onsite interview. That was a Friday and the interview was scheduled at next Thursday while I would have Facebook at the Monday. So I fried to San Jose twice in three days.

Just skip all these stuffs and let’s start the interview. Three interviews in total and a unofficial lunch with one engineer. Google’s interview is even more straightforward then Facebook. Even the self introduction is eliminated and just start with a ‘hi’ and followed by the coding problem. Because of signed NDA, I cannot talk about the detail questions.

Compared with Facebook to be honest I must say the culture of Facebook seems is better then Google in some content. Because the Facebook is new and young. Just like the previous days compared Google with Microsoft, it is the same now when compared Facebook with Google.

However Google is still really attractive not because its free food or beautiful campus or work space.  Those are not advantages compared with Facebook. I think the most attraction for me is Google is the only place where I could probably have chance to reach some great technology like GFS, MapReduce or BigTable. This is the only place. And those are the best ones in the world. As a engineer I must say it is impossible to resist such temptations of great technology. 

以下是面经部分。。


1st interview. One white handsome man with a asian shadow.
(1) build up the sibling pointer for every node in a binary tree.
        I just did this problem with constant memory in about 2 days ago. So I said there are two solutions. First uses a BFS to do the level order traverse and in each level just build the siblings in the next level which uses O(n) memory. The second also traverse the tree but take advantage of the current level are already build up and thus we only need the left most node of each level would be fine which uses O(1) memory. And he said the first solution could be fine and I implemented it in couple minutes.
(2) Given a list of characters and a dictionary, find out all the words in the dictionary which can be  built using the characters from the list. There are duplicates in the list and each character can be used only once.
I found two ideas which use hash or prefix tree as a dictionary. He asked me to do the second one. So I first preprocess the input list as a list with distinct characters and its number. Then use a DFS to generate all the combinations of the words built by the characters from list. During the DFS each step check if each character could be used by two conditions. If there is still available number. And if it resides in the next level in the prefix tree.

2nd interview. One white man who was late for 15 mins but made up it
Only one question something like a design problem but not. Say you are a project manager and someone need you to implement one class. The input of the class is a segmented linear function. And when given a x you need to return the y value corresponding to that segmented linear function. After several rounds of back and forth I started understand what he wanted to implement. Actually it was to use nodes in the edge of each segments to represent the segmented line. And then the coding part is given two segmented linear function and how you use add them up to a new one using the node representation. Do a merge by O(n) time complexity. Then he asked what’s the time complexity by adding m functions all together. I said that’s a better solution to do the bunch merge. He said it’s fine just answer the time complexity by your current algorithm. I said it’s mmn. Then I said I could optimize it. Because it’s already out of time and the next engineer is waiting outside the door. He said “your’s is already better then others”. Hope he didn’t lie me.

Unofficial lunch with a Asian engineer who is really nice and friendly and shared me a lot of feeling about working here.

3rd interview. Some one looks like Bosh who dropped the UCI degree and came here.
At first a little bit arrogant. But after coding part he became really nice and friendly. Totally agree that the ability decide how others attitude to you. And this round was the most satisfied one.
Given a real time infinite input stream with numbers. You are asked to implement a algorithm that could stop the input and return the current medium of the previous input stream.
I gave several different implementations.
(1) just use a vector. Insertion O(1). Get_medium O(n)
(2) maintain it is sorted. Insertion O(n) get_medium O(1)
(3) binary search tree with each node store the number of node in the subtree Insertion O(log n), get_medium O(log n)
(4) two heap Insertion O(log n), get_medium O(1)

Then he asked me implement it by two heaps. I did it. Then he asked me to test by a lot of test cases. I just wondered why he ask me to do so many. Then after doing all the test case correctly. He told me my solution is better then what he thought. Now I understand why he is so eager to run a lot of test cases. Because he just doesn’t want to believe my better solution is correct.

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. 

Replacement, Schedule Algorithm

1. Process Schedule
1. FIFO
2. Round Robin 
3. Fixed Priority Preempt
4. Multilevel queue
2. Cache Swap Algorithm
1. LRU
2. MRU
3. Least Frequently Used
4. Random Replacement
3. Memory Allocation Algorithm
1. Fixed-size Blocks 
2. Buddy Blocks 

Coding Interview Procedure

1. Read the coding problem
2. Clarify the problem 
1. like if the input is valid  
2. could be empty pointer 
3. corner case
3. Think out the idea. 
1. If cannot, talk with interviewer with your thought 
4. Talk out your ideas. 
1. If come up with multiple ideas, talk all of them and compare the difference. Do not wait for interviewer ask you if you know something 
2. Do the time complexity and space complexity analyze
5. Write the code
1. When dealing with some details like index of the array whether needed plus 1 or -1, do not try to first write something then modify it. Correct it at the first time
2. Communicate with interviewer but do not suspend writing
6. Write test case
1. Do not write some test case without any thinking
2. Normal case and corner case
7. Hope can have any follow up questions

[Leetcode Solution] Others

4Sum

Regular Expression Matching

[Leetcode Solution] Longest Substring Without Repeating Characters

find 20th popularist URLs

Given a file containing a huge volume of URLs, find the 20th popularist URL.

First use hash ( std::map ) to count the occurrence time of each URL. Then the problem is transformed into the problem that give an unorderred array, find out the 20th largest element in the array.

Two intuitive ideas are formed.
Let's assume in total N distinct URLs and find out the Kth URL

• QuickSelect 

• Direct use quick select algorithm to find out the 20th URL.
• Time complexity: O(N) for average time complexity
• Could be O(N*N) in the worst case.

• Heap
•  First build up the maximum heap and then pop up the top element K-1 times
• Then the next top element will be the Kth URL
• Build up heap runs in O(N) time if use divide and conquer strategy
• Each time pop up runs in O(logN)
• Total time complexity is O(N)+O(K*logN)
• (If we maintain a heap with fixed size of K elements, then there is no need to build up the entire heap and each insertion runs in O(logK). Thus the total complexity is O(N*logK)

Compare the two method, we can find if the K is small like 20, the second method using a heap would be better. If the N is big and so is the K like 100000 then QuickSelect could be better.

Following is the implementation for both algorithms.

Count the number of reverse ordered pairs

Use merge sort we can easily calculate the total number of reverse ordered pairs.

Here talks about how to find out the number of reverse ordered pairs for each element which means

Given an array A[n], for each element A[x], count the number of reverse ordered pairs that the number of A[y] that y>x  and A[x]>A[y].  (Assume no duplicate in the array.)

For example given array A[ ] = {41 67 34 0 69 24 78 58 62 64 5 45 81 27 61}
Then the reverse ordered pair number for each element is {5 10 4 0 8 1 7 3 4 4 0 1 2 0 0}

1. This problem cannot be solved in O(n) time. Because if it could, sort problem could be also solved in O(n) time.
2. There are two intuitive ideas. 
1. Use merge sort. During merge sort procedure when we merge two subarr arr1 and arr2 into arr, if any element resided in arr2 is put into arr before any element which still remains in arr1. Then we should add 1 for each remaining element in arr1's number of reverse ordered pair. But this will cost O(n) time. So instead when each element in arr1 is the current element will be put into arr, we count how many elements in arr2 have already put into arr ahead of this element. And this could be done in O(1).
2. Use a binary search tree. We scan the array from back to front and each time when an element X is scanned.  First check out how many elements in the BST is bigger then X. This costs O(logn) by adding a meta information for each node which denotes the total number of node in this subtree rooted by this node. Then insert X into BST which costs O(logn). The only problem for this method is implementing a BST is simple but a Balanced BST could take some time.

Here are the implementation of two methods and use them to calculate the same data and we can see the results are the same.

Suning R&D Center 2nd Round Video Interview 11.7

2nd round interview with Suning R&D Center which is focusing on search engine. However I'm more interested in cloud computing and distributed system such infrastructure stuffs.

There are 2 back-2-back interviews each about 50 minutes. Both interviewers are really biubility persons.

The first interview with Director of Search was talking about how to deal with parsing the user input queries. The first step is to add white space if user forgets to do that. Thus it was a coding problem given a input string and a dictionary containing all the words. It was easily done by a dfs. The second step is how to you deal with the phrase consisted by several words. For example if the input string is androidphone and there are three words "an, android, phone" in the dictionary. How to you delimit it as "android phone" rather then "an doird phone". And the only project experience talking about is search engine.

The second interview with an Senior PM was talking about how to optimize the search engine. What we focused on is how to scale up. After that given a situation that how to you count how many facebook user read a post if some of them shared that post.

I should be more prepared for this interview because I have already found that the interviewers are mostly focus on the information retrieval technology from LinkedIn.

Learned

• 肯定会被问到的就是你想做什么方向。
• 为什么你想做这个方向
• （应该提前想好这两个问题用英语怎么说，要不然突然发现想表达的观点里有些词不知道怎么讲真是好尴尬）
• 既然已经提前发现他们都是做搜索的，就应该多多准备这个方向的内容，虽然我对这个不是特别感兴趣。最后证明他们确实在问搜索方面的问题，而且只问了这个的问题）
• 当问设计题、思考题（coding之外的题目时），不要光说答案啊，要把整个思考的过程说出来，应该主要是表达出自己的思维和逻辑能力

总体来说，做的方向和问题的方向不是很match。另一方面头一次被问这种设计题和思考题，不太会答题的策略。所以除了上来的第一道算法题飞快就写出来了以外，别的答得都不咋地。估计是跪了。

最后hr打来电话问我啥时候能开始工作，我说二月份。然后hr就表示那估计悬了，他们想要立马就能工作的。。。当时还是挺无语的，毕竟你们在招new grad，我十二月底才能毕业，哪儿有new grad能面试完就立马入职啊，难道要人毕业之后才开始找工作么。而且不能一开始先问清楚我啥时候能入职么，都面到这会儿了才说。。

Medium interview experience.

Google On-Campus Interview 10.6

Google is my most wanted company which is like kind of a dream.
Well prepared for this on campus interview and it seems I got a luck ball.
There are total two back to back interviews each 45 minutes.

The first round started with a coding problem without any introduction and the interviewer looked like a shy geek. He gave me two pretty simple coding problems which I done in about 20 minutes. After that he though for a time and put out a new coding problem which I though is made by himself. Then all the remaining time and discuss that question.

The second round talked about some basic usage of C++ language in the first half time. The second half were solving a problem which was interviewer's first task when he entered google. It was a string compare problem which roughly equals to medium difficulty problem in leetcode.

Seems that I do have a good luck that all the interview question are quiet easy and have a very positive interview experience.


(11.10) Move forward to next round

终于遇到奇葩的烙印了

在美国选了计算机方向，话题里注定就少不了烙印。无论是同学口口相传还是网上的帖子里看到的故事，烙印给我的印象都是能扯淡、能巴结、不干实事臭不要脸的形象。

接触的第一个烙印是第一学期，一门课的project，一个烙印联系我问我要不要一起做，我一想挺好啊。然后约着见面谈一下。见面之后该烙印就直白的表示，他这学期要毕业没时间做project，能不能一组然后让我做。。虽然提出的要求很奇怪，但总比传说中要好一百倍，传说中的都是一开始说自己会好好做怎么怎么样，但是结果却啥也不干。这是对烙印的第一印象，感觉还是不错的。

之后实习，从第一个面试官到第三个面试官全是烙印。态度都很和蔼。从面试到实习再到最后拿到return offer，基本上全是和烙印在打交道，感觉烙印还是很善良很踏实的，从来没有为难过我，相反而是经常在工作和技术上帮助我。让我觉得网上的人一棒子轮死的说法还是比较不负责任的。

之后就是前阵子career fair，和fb的一个烙印工程师聊天，那个口音叫一个重啊，几乎什么都听不懂。但是最后他却给我了on campus面试的机会。

直到遇到现在这个烙印，我对烙印的印象都是很好的。
这真是个奇葩的烙印叫他V好了。我们一起一个课做paper的presentation，paper总共6个section，前边4个就是讲讲intro啊related work啊之类毫无难度的东西，section5才开始讲具体内容，sec 5包含了六七个小标题，总共占整个paper大半页数。
V先是问我打算怎么分工。我表示感觉内容还好，我都可以，看他怎么分都行。我以为会把sec 5的若干小标题分成两半一人一半。结果V表示，那他做前4个sec，我来做第5.。。。

头一次遇到奇葩的烙印。但从统计学角度来看，虽然个别烙印确实给我们留下了非常恶心的印象，但是不能反映印度人整天的情况的。所以本人还是反对网上网友因为个别烙印严重伤害到其利益后，就把一个国家的人一棍子轮死的言论的。

//Updated 11/22
真是庆幸这个吐槽是用中文写的。。
这周上课到的有点早，又碰见了这个三哥同学。。三哥同学很兴奋的跑过来跟我讲说居然看到了我的博客，觉得里边的总结挺有用。。
同时交流了下做功课的心得，三哥很热情的跟我介绍了几本他觉得很吊的复习书，然后把盗版pdf发了过来。。

Bit Manipulation

1. Bit Operators

1. & ( bitwise and )
2. |   ( bitwise or )
3. ^ (xor)
4. <<, >> (shift)
5. !   ( bitwise not, complement)

2. Usages

• &     used to set a bit into 0
• |       used to set a bit into 1
• ^      used to check whether two bits are the same. ( thus can store information )
• <<    used to perform the times 2 operation

3. How to set a sequence of bits into 0s or 1s

Let say we can an integer X and would like to set from i-th bit to j-th bit into 0s (or 1s).

We first get a mask that all bits are 1 except the bits from i to j ( looks like 11111000..0011111)

Finally  X = X & Mask 

4. How to get that mask

How can we get the mask that all the bits are 1s except some are 0s ( all are 0s except some are 1s)

In order to get some masks looks like this

• 00000111 :     (1<<3)-1
• 11100000 :     ( !0 ) - ( (1<<5) -1 )
• 11100111 :     ((1<<3)-1)  |  (( !0 ) - ( (1<<5) -1 ))         

5. How to swap two variable without using extra variable

x = x ^ y

y = x ^ y

x = x ^ y

This shows that XOR operator could store extra information within one variable which could be used in some brain teaser.

6.How to check if a integer is power of 2

( ( x & ( x -1 ) ) == 0 )

All the integer which is power of 2 and 0 will return true.

x = 0 ;      // 2 ' 00000000
x-1        ;  // 2 ' 11111111
x & ( x-1 )// 2 ' 00000000

6.Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”

External Sort

1. External Sort

The simplest one 'two way merge sort".

First pass. Use in memory sort to sort records within each page.

Following passes. (Assume using 3 pages of memory 2 as input buffer and 1 as output buffer). 

           1. Merge every two pages into one 

           2. Merge every four pages into one

           3. Merge every eight pages into one

   Each time use input buffer to read from one source. Read next page when the records run out in input buffer. When output is full write it into disk and clear it.

2. qiqiguaiguaide

1. sizeof ( float) == 4
2. struct{ char[3] } . The size of this structure is 4 because of alignment
3. struct { char [3], int , float, char [0] }. The usage of char [0]
4. Extern C

Ohters from Interview

1. sizeof ( float) == 4
2. struct{ char[3] } . The size of this structure is 4 because of alignment
3. struct { char [3], int , float, char [0] }. The usage of char [0]
4. Extern C

Arista Network On Campus Interview 11.3, 11.4

Meet up with a really nice interviewer who is really friendly and  and communicate really comfortable.

First come up a coding problem which is kind of easy. I cannot say what it is. But it is just some basic operations on the linked list.

Then come ask multiple areas of knowledge like C, C++, data structure, debugging. All of these are asking some basic concepts.

The interview is wonderful and fits me a lot. During coding phase it allows you to type the code in a computer and to compile and run it rather then just writing on the white board.
When asking about the size of a float variable it allows you to figure it out by writing some code if you are not sure about it.

Great interview experience. Very nice interviewer.

11.4 noticed to move forward to 2nd round which is the final round and which would only contains technical problems and coding problems. sound great

[Leetcode Solution] Remove Nth Node From End of List

Amazon Interview Online Assessment 11.2

Amazon is the best choice for me because of its AWS and EC2. They are the dream place I would like to work in. Hope the embarrassing of Amazon Fire Phone won't have too much negative effect on Amazon this year's hiring.

Referred by a friend and contacted by a HR last week. Then her gave me a link to the online assessment.

In the Online Assessment there are two parts of the problems, coding part and reasoning part.

The first coding part has two coding problems give 70 minutes. I cannot tell you what the problems are. But they are definitely easy and basic coding problems. Everyone with basic coding knowledge would easily solve both two problems in 15 minutes.

The second seasoning part given 35 minutes with 24 problems. This is the really difficult part. For me the most challenging is not the question itself. But you know some of them have a really long description and another really long question. THAT IS TERRIBLE BECAUSE IT TAKES ME A LOT OF TIME JUST TO FIGURE OUT WHAT IT IS SAYING FOR AN NO-ENGLISH SPEAKER. And because having no idea about what kinds of questions may be asked  thus have no idea about how to schedule the time. I don't think this is a good way to assess people that may not separate different people because neither smart guys or not smart guys would do better because none of them have any time schedule strategy because nobody have any information about the meta information of questions.

Didn't do a good job at online assessment. Not a positive experience.

(11.5) received a email which told me to another online assessment which is called the work style and personality test. ohhhhhh myyyyyy


(11.10) Move forward to next round onsite interview