Ying's Hunting Journal: February 2015

Saturday, February 28, 2015

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

------------------------------------- thinking ---------------------------------------
The below solution is beautiful!!!!!!
https://oj.leetcode.com/discuss/19973/8ms-c-solution-using-bfs-with-explanation
Please try to give some optimizations in the codes to reduce the usage of the memory

Ordinary DP solution
https://oj.leetcode.com/discuss/11694/my-dp-solution-in-c

-------------------------------------- codes ----------------------------------------------
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1+len2 != len3) {
return false;
}
bool dp[len1+1][len2+1];
memset(dp, false, sizeof(dp));
for(int i = 0; i < len1+1; i++) {
for (int j = 0; j < len2+1; j++) {
if (i==0 && j==0) {
dp[0][0] = true;
} else if (i==0) {
dp[0][j] = dp [0][j-1] && (s2[j-1] == s3[j-1]);
} else if (j==0) {
dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]);
} else {
//bug here-> please be careful about the index, it should be s2[j-1] == s3[i+j-1]
//instead of s2[j] == s3[i+j] or s2[j-1] == s3[i+j-2]
dp[i][j] = (dp[i][j-1] && (s2[j-1] == s3[i+j-1])) ||
(dp[i-1][j] && (s1[i-1] == s3[i+j-1]));
}
}
}
return dp[len1][len2];
}
};

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

--------------------------- thinking ----------------------------------
https://oj.leetcode.com/discuss/19735/a-dp-solution-with-clarification-and-explanation

BUG -> please pay attention to the order of i and j, which represents the index of source string and target string!

Please try to optimize the codes below by using less memory!
---------------------------- codes -------------------------------------
class Solution {
public:
int numDistinct(string S, string T) {
int slen = S.size();
int tlen = T.size();

int dp[tlen+1][slen+1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < slen+1; i++) {
dp[0][i] = 1;
}
for (int j = 1; j < tlen+1; j++) {
for (int i = 1; i < slen+1; i++) {
if (S[i-1] == T[j-1]) {
//bug here ->i represent the source string!!!! should add dp[j][i-1] instead of dp[j-1][i]
dp[j][i] = dp[j-1][i-1] + dp[j][i-1];
} else {
dp[j][i] = dp[j][i-1];
}
}
}
return dp[tlen][slen];
}
};

Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

------------------------------- thinking -----------------------------------
https://oj.leetcode.com/discuss/19615/dp-solution-%26-some-thoughts
One thing I need to remember is how to correctly use memset()!!!!!!!
https://oj.leetcode.com/discuss/5586/memset-and-fill_n

very nice solution without using marker!!
https://oj.leetcode.com/discuss/9476/solution-does-not-need-table-palindrome-right-uses-only-space
-------------------------------- codes -------------------------------------
class Solution {
public:
int minCut(string s) {
int len = s.size();
if (len <= 1) {
return 0;
}
bool mark[len][len];
memset(mark, false, sizeof(mark));
for (int i = 0; i < len; i++) {
mark[i][i] = true;
}
int dp[len+1];
dp[0] = -1;
for (int i = 1; i <= len; i++) {
//bug here -> min should be i-1
int min = i-1;
for (int j = i-1; j >= 0; j--) {
if (s[i-1] == s[j] && (j+1 == i-1 || j == i-1 || mark[j+1][i-2])) {
mark[j][i-1] = true;
if (dp[j] + 1 < min) {
min = dp[j] + 1;
}
}
//else {
// mark[j][i-1] = false;
//}
}
dp[i] = min;
}
return dp[len];
}
};
------------------------- codes / no mark is needed ----------------------------------
class Solution {
public:
/**
* @param s a string
* @return an integer
*/
int minCut(string s) {
// write your code here
vector<int> cur(s.size()+1);
for (int i = 0; i <= s.size(); i++) {
cur[i] = i-1;
}
for (int k = 1; k < s.size(); k++) {
//odd counting
//bug here, start and end should be set to k instead of k-1 and k+1
int start = k;
int end = k;
while (start >= 0 && end < s.size() && s[start] == s[end]) {
if (cur[end+1] > cur[start] + 1) {
cur[end+1] = cur[start] + 1;
}
start--;
end++;
}
start = k - 1;
end = k;
while (start >= 0 && end < s.size() && s[start] == s[end]) {
if (cur[end+1] > cur[start] + 1) {
cur[end+1] = cur[start] + 1;
}
start--;
end++;
}
}
return cur[s.size()];
}
};

Candy

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

-------------------------- thinking ------------------------------------------
It's good to at least understand the second solutions.
https://oj.leetcode.com/discuss/23835/one-pass-constant-space-java-solution
https://oj.leetcode.com/discuss/13841/easy-understand-solution-with-comments-constant-space-pass

--------------------------- codes -------------------------------------------
class Solution {
public:
int candy(vector<int> &ratings) {
vector<int> candys(ratings.size(), 1);
for(int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i-1]) {
candys[i] = candys[i-1] + 1;
}
}
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i+1]) {
candys[i] = (candys[i+1] + 1) > candys[i]? candys[i+1] + 1: candys[i];
}
}
int result = 0;
for (int i = 0; i < ratings.size(); i++) {
result += candys[i];
}
return result;
}
};

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

------------------------ thinking -------------------------------------
https://oj.leetcode.com/discuss/19100/o-n-c-solution-in-20ms-and-explanation

Suppose there are N elements and they range from A to B.

Then the maximum gap will be no smaller than ceiling[(B - A) / (N - 1)]

Let the length of a bucket to be len = ceiling[(B - A) / (N - 1)], then we will have at most num = (B - A) / len + 1 of bucket

for any number K in the array, we can easily find out which bucket it belongs by calculating loc = (K - A) / len and therefore maintain the maximum and minimum elements in each bucket.

Since the maximum difference between elements in the same buckets will be at most len - 1, so the final answer will not be taken from two elements in the same buckets.

For each non-empty buckets p, find the next non-empty buckets q, then q.min - p.max could be the potential answer to the question. Return the maximum of all those values.

Analysis written by @porker2008.

--------------------------- codes --------------------------------------------

class Solution {

public:

int maximumGap(vector<int> &num) {

if (num.size() < 2) {

return 0;

}

vector<int> grids;

grids.reserve(num.size() * 2);

vector<bool> mark(num.size(), false);

int min = num[0];

int max = num[0];

for (int i = 1; i < num.size(); i++) {

if (num[i] > max) {

max = num[i];

}

if (num[i] < min) {

min = num[i];

}

//important to have 0.1 added to max, or the max value will get num.size() as the index, which will cause the problem

double gap = double(max + 0.1 - min) / num.size();

for (int i = 0; i < num.size(); i++) {

int index = (num[i] - min) / gap;

if (mark[index] == false) {

mark[index] = true;

grids[index * 2] = num[i];

grids[index * 2 + 1] = num[i];

} else {

if (num[i] < grids[index * 2]) {

grids[index * 2] = num[i];

}

if (num[i] > grids[index * 2 + 1]) {

grids[index * 2 + 1] = num[i];

}

int maxGap = 0;

for (int i = 0; i < num.size(); i++) {

if (mark[i] && (grids[i * 2 + 1] - grids[i * 2] > maxGap)){

maxGap = grids[i * 2 + 1] - grids[i * 2];

}

int start = 0;

int end = 1;

while (true) {

while (end < num.size() && !mark[end]) {

end++;

}

if (end >= num.size()) {

break;

} else {

maxGap = (grids[end * 2] - grids[start * 2 + 1]) > maxGap? grids[end * 2] - grids[start * 2 + 1] : maxGap;

start = end;

end++;

}

return maxGap;

}

};

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

------------- thinking -------------------------------
Bug -> duplication should be considered in this case, this is very important!!!!!!!!!!!!!!!!!!!

https://oj.leetcode.com/discuss/25812/o-n-hashmap-java-solution
https://oj.leetcode.com/discuss/18886/my-really-simple-java-o-n-solution-accepted
https://oj.leetcode.com/discuss/19598/13-line-c-solution
---------------- codes -------------------------------
class Solution {
public:
int longestConsecutive(vector<int> &num) {
unordered_map<int, int> map;
int longest = 1;
for(int i = 0; i < num.size(); i++) {
//bug -> we might have duplications in the array!!!!
if (map.find(num[i]) != map.end()) {
continue;
} else {
map[num[i]] = 1;
}
int pre = num[i] - 1;
int nxt = num[i] + 1;
int start = num[i];
int end = num[i];
if (map.find(pre) != map.end()) {
start = num[i] - map[pre];
}
if (map.find(nxt) != map.end()) {
end = num[i] + map[nxt];
}
int length = end - start + 1;
if (length > longest) {
longest = length;
}
map[start] = length;
map[end] = length;
}
return longest;
}
};

Friday, February 27, 2015

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

----------------------------- thinking -------------------------------
4 sum cannot be implemented as 3 sum closest algorithm !!!!!
Be careful about the duplication in the array!!!
The simple codes is O(n3) complexity

Please read the O(n2) codes in the link
https://oj.leetcode.com/discuss/21401/is-there-really-a-o-n-2-solution

----------------------------- codes -----------------------------------
class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
sort(num.begin(), num.end());
vector<vector<int>> result;
if (num.size() < 4) {
return result;
}
int start = 0;
int end = num.size() - 1;
for (int first = 0; first < num.size() - 3; first++) {
//bug here -> should remove those duplications
if (first > 0 && num[first] == num[first-1]) {
continue;
}
//bug here -> the second one should start just next to the first instead of from the end
//4 sum cannot be fulfilled by the algorithm in 3 sum
for (int snd = first + 1; snd < num.size() - 2; snd++){
//bug here -> should remove those duplications
if (snd > first + 1 && num[snd] == num[snd-1]) {
continue;
}
int subsum = target - num[first] - num[snd];
int sstart = snd+1;
int send = num.size() - 1;
while (sstart < send) {
if (sstart > snd+1 && num[sstart] == num[sstart - 1]) {
sstart++;
continue;
}
if (send < num.size()-1 && num[send] == num[send+1]) {
send--;
continue;
}
if (num[sstart] + num[send] == subsum) {
int sol[4] = {num[first], num[snd], num[sstart], num[send]};
vector<int> sol1(sol, sol+4);
result.push_back(sol1);
if (num[sstart] == num[send]) {
break;
}
sstart++;
send--;
} else if (num[sstart] < subsum - num[send]) {
sstart++;
} else {
send--;
}
}
//if (subsum > 0) {
// start++;
//} else if (subsum < 0) {
// end--;
//} else {
// start++;
// end--;
//}
}
}
return result;
}
};

------------------------------------ read codes -----------------------------------------
class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
results=set()
num.sort()
new_num=[]
filter=dict()
for x in num:
if x not in filter:
filter[x]=1
new_num.append(x)
elif filter[x]<4:
filter[x]+=1;
new_num.append(x)
pairs=[[x,y] for x in xrange(len(new_num)) for y in xrange(x+1,len(new_num))]
twoSums=dict()
for pair in pairs:
if new_num[pair[0]]+new_num[pair[1]] in twoSums:
twoSums[new_num[pair[0]]+new_num[pair[1]]].append(pair)
else:
twoSums[new_num[pair[0]]+new_num[pair[1]]]=[pair]

for num1 in twoSums:
num2=target-num1
if num2 >= num1 and num2 in twoSums:
combinations=[pair1+pair2 for pair1 in twoSums[num1] for pair2 in twoSums[num2] if pair1[1]<pair2[0]]
for comb in combinations:
results.add(tuple([new_num[i] for i in comb]))
return [list(sums) for sums in results]

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

--------------- thinking --------------------------------------
using shifting method to adjust the location, and find the closest sum target
---------------codes --------------------------------
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
sort(num.begin(), num.end());
int start = 0;
int end = num.size() - 1;
int diff = INT_MAX;
//it's very important to stop when star is next to end(start+1<end), because there will be no 3 items left anymore!!!!!
while (start+1 < end && start >= 0 && end < num.size()) {
//bug here -> remember the start and end have been considered, so start+1, end-1 should be used as input
int nearest_ele = findNearest(num, start+1, end-1, target - num[start] - num[end]);
int sum = nearest_ele + num[start] + num[end];
if (abs(sum - target) < abs(diff)) {
diff = sum - target;
}
//when the sum is smaller than target, move start item
if (sum - target < 0) {
start++;
} else if (sum - target > 0) {//when the snum is bigger than target, move end item
end--;
} else {
return target;
}
}
return target + diff;
}
//binary search to find the nearest item to the target!
int findNearest(vector<int> &num, int start, int end, int target) {
//bug here
//remember to check if target is inside of start and end
if (num[start] >= target) {
return num[start];
}
if (num[end] <= target) {
return num[end];
}
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (num[mid] < target) {
start = mid;
} else {
end = mid;
}
}
if (num[start] >= target) {
return num[start];
}
if (num[end] <= target) {
return num[end];
}
return abs(num[start] - target) < abs(num[end] - target) ? num[start] : num[end];
}
};

标题: 国内找北美社招职位面试总结

发信人: dragon418 (T_Dog), 信区: JobHunting
标题: 国内找北美社招职位面试总结
关键字: Google Facebook Amazon Linkedin
发信站: BBS 未名空间站 (Thu Feb 26 02:42:06 2015, 美东)

版中大多数面经都是针对北美new graduate的, 在此贡献一下本人国内找北美工作的一
些经验吧, 也算是答谢mitbbs上分享面经的朋友对我的帮助. 更希望攒攒人品能够抽到
h1b签证 :)

[背景]
国内4年工作经验. 硕士毕业后一直在某做存储的外企工作.
14年7月份开始有出国打算并开始准备.

[准备]
在工作之余每天坚持至少刷3~4道算法题, 并关注各个公司的blog及github上的开源项
目.

1. 算法
   Leetcode自然不必说, 必刷. 先是用了将近两个月的时间把leetcode刷了1.5遍, 然
后每次电面和onsite面之前挑一些觉得做得不好的题再刷.

   其次就是看geeksforgeeks上题. 这是个老印host的网站, 但是上面的题目分类明晰
,有很多分类底下的题目非常好, 比如DP (印象最深的就是m个鸡蛋n层楼测在哪层楼鸡
蛋会被摔碎的问题)和graph (印象最深的就是单源/多源最短/最长路径和欧拉环). 每
天看一下还是能学到不少新鲜的知识的.

   其他就没有了, career up和glass door也断断续续看了一些, 上面的设计题挺好的
, 算法题感觉没有多大帮助.

2. OOD
   面向对象设计的面经在网上真是少之又少. 准确说来是题目不少, 但是几乎都没有
解答. 所以我都是按照自己的理解和工作中的用到的一些设计方法来练习这种题目的.
每周用CRC练习1~2道经典的OOD的题 (e.g. elevator, vendor machine, chess game,
ATM, etc)

   虽然花了很多精力准备了OOD的题, 但是没有一家公司面过我这种类型的题 :(

3. 系统设计
   主要是high scalability和high availability的web service的设计.关注了下面几
个跟系统设计相关的resource:

    (1) HighScalability Website
         这是我最开始看的网站, 也是我觉得最好的一个网站. 里面总结了很多real-
life architectures, 尤其是"All Time Favorites"这个专栏下的文章都非常经典, 可
以follow文章里的链接找到tech talk的slides或video.

         由于本人没有web service相关工作经验,所以一开始看起来非常吃力. 不过
经过一段时间的"煎熬", 还是能够形成high level的design sense的, 尤其是能够知道
在设计一个scalable的web时要注意哪些问题以及这些问题大概有哪些方法解决.


    (2) 各个公司的blog及其在github上的open source projects
         我看的最多的是Facebook和Linkedin的技术博客. 看HighScalability网站能
够形成high level的design sense, 关注这些公司的博客尤其是其开源项目能够加深了
解每个product的设计和细节.
         其实到了一定时间后看这些技术博客和开源项目并不是出于面试的目的了,
而是出于兴趣. 尤其是Facebook的博客, 有时候会详细介绍公司在技术上遇到了哪些问
题和瓶颈, 曾经尝试了什么方法去解决以及为什么采用了现在的方法, 我觉得看看这些
文章还是蛮有意思的.

    (3) Paper
         看了大概有二十几篇论文, 详细了解了一些技术和产品的设计/实现/性能评
测, 比如vector clock的应用, 改进的consistent hashing, HDFS, zookeeper的实现,
openstack swift的architecture等.

[面试]

投了很多公司, 但是只有FLAG理会了, 其他公司要么就是没有回音,要么就是简历直接
被拒. 中间还穿插着面了一下国内的阿里云(拿到了offer, 但犹豫了一阵还是坚持以出
国为目的吧).

目前拿到了F家Infrastructure组和A家AWS组的offer, L家被拒, 狗狗第一次面试挂了,
隔
了半年HR又给了一次面试机会, 仍在进行中.

算法难度: G > F = A > L
系统设计难度: L > A > F > G
系统设计在整个面试中的比例: L (70%) > A (60%) > F (40%) > G(20%)

1. 狗家

电面:
(1) Given a string S and a string T, find all occurences of T in S.
An occurence is found if the substring of S is the permuation of T.

(2) You are given a sorted array of integers in range [0, 99], your task is
to output a string that describes numbers that are missing in the array.

For example:
Given array is [0, 1, 2, 50, 52, 75]
Output string is "3-49, 51, 53-74, 76-99"

(3) Express a target integer as a sum of square numbers, using as few terms
as possible.

For example:
14 = 9 + 4 + 1
13 = 9 + 4
12 = 4 + 4 + 4

(4) You are given an array A. Each element is a tree node and the tree node
is defined as:
        typedef struct __TreeNode {
                int                id; // the node's ID, e.g. 0xEEAD
                int                parentIndex; // parent node's ID, e.g.
0x5EED
                int     weight;       // the weight of the node
        }TreeNode;

        Your task is to output the weight sum of each subtree. Should solve
it in O(n) time complexity.

onsite的部分题目可以在我之前的帖子中找到. Onsite是在Beijing的office.
http://www.1point3acres.com/bbs/thread-111785-1-1.html

2. F家

电面一轮, strstr的两个变种, 主要考察能否将一些复杂的逻辑抽象成对象以简化代码.

onsite是美国和英国的面试官来中国面的,我们那一波大概有八九十人, 我是一下午面
完的4面, 春节回家的前一天又skype加面了一轮系统设计.

算法题都是Leetcode和CC150上的题目的原题和变种. 变种题目稍加推理便可以得到答
案.

设计题有两个, 一个是针对search engine中的某个具体问题进行scalable的设计, 还
有一个是multi-thread环境下Cache的设计, 后者的重点也是在scalable, 只不过是多
核上的scalable, 而非多机器上的scalable. 具体题目就不透露啦 :)

除此之外, 其中有一面对我现在工作的project进行了详细的讨论

3. L家

电面1:
(1). OS related questions.

(2). Mirror a tree in place

(3). Design a data structure that has following interfaces:
     - bool insert(T val)
     - bool remove(T val)
     - bool search(T val)
     - T removeRandom()

(4). Given an array A[], output another array B[], where B is the product of
all the elements in A except A.
     optimization: Could you do it without using divide operator?

电面2:
(1). OS related questions

(2). Detail discussion about my current project

3. //public interface InfluencerFinder {
    /**
     * Given a matrix of following relationships between N LinkedIn users (
with ids from 0 to N-1):
     * followingMatrix[j] == true iff user i is following user j
     * thus followingMatrix[j] doesn't imply followingMatrix[j].
     * Let's also agree that followingMatrix == false.
     *
     * An influencer is a user who is:
     * - followed by everyone else and
     * - not following anyone herself/himself
     *
     * This method should return the influencer's id in a given matrix of
following relationships,
     * or return -1 if there is no influencer in this group.
     */
//    int getInfluencer(boolean[][] followingMatrix);
//}

Onsite是通过skype进行的, 总共6面,其中4面是系统设计, 在白板上画框图.

Round 1:
1. Implement an iterator for Array<Integer>.
   When you call next(), returns the next positive integer
   Implement hasNext(), returns true if there is one positive integer

   For example:
   (1,-4,0,5)
   next() -> 1
   next() -> 5
   next() -> 6

2. Serialization and Deserialization of a binary tree with full codes

Round 2:
Implement a hash table with multi-thread access, including the following
interfaces:
(1) bool get(Key k, T &t)
(2) void put(Key k, T t)
(3) void rehash(int newSizeOfArray)

Round 3:
1. Design a key-value store deployed on a single machine. The API your key-
value store provides should be:
(1) bool get(Key k, char *data, int &dataLen)
(2) void put(Key k, char *data, int dataLen)

You are only provided with the following file API from OS:
(1) create file
(2) open file
(3) close file
(4) read file (fid, int offset, int readLen)
(5) append file(fid, char *data, int dataLen) // append data to the end of a
file

2. We have following program:

int main() {
        char *buffer = new char[100];
        printf("0x%x", buffer);
        for(int i = 0; i < 100; ++i)
                buffer = 'a' + rand() % 26;
        sleep(10000); // sleep 10 seconds
        delete [] buffer;
        return 0;
}

Now We compile this code to one program, and execute two instances of the
program concurrently. And we find the two program output the same buffer
address "0xFFFF8900". Question is: does the write in the two programs
interfere each other?

Actually this is all about the details of how does virtual memory work, such
as exception handling, MMU, how does inter-process communication works, etc.

Round 4 :

You are given a graph interface:

int[] getConnections(int userID)
In this interface, you can give a userID, then it returns all IDs of his
friends.

Now please implement the following functions:
(1) bool is1stDegreeConnection(int srcUserID, int destUserID)
    it returns whether destUserID is the friend of srcUserID

(2) bool is2ndDegreeConnection(int srcUserID, int destUserID)
    it returns whether destUserID is the friend of srcUserID's friends
        Tried different algorithms and finally got the most optimized one.

(3) bool is3rdDegreeConnection(int srcUserID, int destUserID)
    it returns whether destUserID is the srcUserID's friends' friend
        (3) is an open question, no need to write codes.


Round 5:

You have thousands of web server and database machines in a datacenter, and
each of them continuously generate real-time statistics data, such as CPU
Utilization, Memory Usage, JVM statistics, etc.

There are also two services. One is figure plotting service, who will plot
figures for all the collected statistics data by some machine learning
algorithm, and the other one is alerting service, who will detect abnormal
behaviours of the machines and sending alert emails or SMS to the
administrators.

Please design this monitoring system, including describing how the
statistics data are collected by the two services and what is the bottleneck
in your monitoring system. The system should be with high scalability and
availability. During this design, had a discussion about consistent hashing,
Zookeeper and HDFS.

Round 6:
Hiring Manager Interview (30 minutes) and one short system design (20
minutes) about the cooperation of old-interface machines and new-interface
machines.

4. A家

电面1:
(1) 10 minutes behavior questions
(2) 10 minutes knowledge-based questions such as memory management, thread
sync, data structure, C++, etc
(3) Search the kth node from the last of a linked list.
(4) word ladder II

电面2:
(1) 20 minutes behavior questions
(2) 15 minutes discussion about block storage related to my work
(3) Given the sbrk() function in Unix, implement a memory management module,
which should basically provides malloc() and free() interfaces.

Onsite interview 是通过 Jebber Video 进行的, 早上5点到10点共五轮.

Round 1:

(1) First 20 minutes all about behavior questions.

(2) Search a target number in a right shifted sorted array, which is
distributed in hundreds of machines in a datacenter.

Round 2:

1. LeetCode上word search的变种

2. 在1中我用到了trie树来加速搜索,于是实现trie树, 包括插入/查询操作.

3. 在1和2的代码中如何对数据进行压缩以节省内存

Round 3:

(1) First 20 minutes all about behavior questions.

(2) Fully discussion on my projects.

(3) 针对我做过的两个项目, 推翻项目中的一些假设, 提出新的问题, 看如何设计新的
方案解决.

Round 4:

这一轮是hiring manager, 所以问的都是behavior questions, 例如why Amazon, how
to handle conficts, how to handle deadlines, any case you insist on
something, etc. 最后问了一个小的设计题.

Round 5:
(1). First 20 minutes all about behavior questions.

(2). 设计Flickr, 包括图片上传, newsfeed, 点赞, 评论等功能的设计和数据库的
scheme. 其中还问到了会用AWS中的那些product去实现设计的系统.