## Friday, June 10, 2016

### Google Interview Misc Part 8

public void calculate(int[] nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
double avg = sum * 1.0 / nums.length;
double[] temp = new double[nums.length];
for (int i = 0; i < nums.length; i++) {
temp[i] = avg - nums[i];
}
int cur1 = 0; //pos
int cur2 = 0; //neg
while (cur1 < nums.length) {
while (cur1 < nums.length && temp[cur1] <= 0) {
cur1++;
}
while (cur2 < nums.length && temp[cur2] >= 0) {
cur2++;
}
if (cur1 < nums.length && cur2 < nums.length) {
double min = Math.min(temp[cur1], -temp[cur2]);. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
System.out.println("" + cur2 + " gives " + (min) + " to " + cur1);
temp[cur1] -= min;
temp[cur2] += min;
}
}
}
 给定一个句子, 和若干个搜索词, 求包含所有搜索词的最短句子长度. Badmin was able to beat Bill at billiards, but Bill always beat Badmin badly at badminton.给定搜索词: Query = [Badmin, Bill, beat]返回 4. 因为子句(Bill always beat Badmin)是包含Query中所有单词的最短子句.提示: 可以将子句看成倒排的形式如:"Badmin" = [0, 12]"Bill" = [5, 9]"beat" = [4, 11]其中倒排中的每个index是递增的, 可以利用这点剪枝(?) 这是我面试遇到的问题, 我只想到了暴力解, 就是用dfs枚举所有. 希望大家提供更好的解

1. Given a binary tree, find if there are two subtrees that are the same. (i.e. the tree structures are the same; the values on all corresponding nodes are the same). You should find the largest subtree and don’t use brute force.

(root value, group id of left, group id of right) -> group id of root
group id -> subtrees of this group

group id就是一个数字，对应一棵unique的子树。

0: NULL
1: leftnode, right node
2: root node

(root val, left id, right id)->root id的hashtable存的是
(20, 0, 0) : 1
(10, 1, 1) : 2

2. Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array

1. 友善印度小哥。说是考察一群学生的出勤率，如果连续3天来晚（L）就记作差（F），或者任意两天旷课（A）也记作F。成为F就一直是F了。考察30天后，有多少种F的排列组合。

int nPermute(int days){
// Automata
//    L      L      L
// I --> L1 --> L2 --> F
//    A      A
// I --> A1 --> F
// state I, I
int[] dp1 = new int[2];
// I, A1
int[] dp2 = new int[2];
// L1, I
int[] dp3 = new int[2];
// L1, A1
int[] dp4 = new int[2];
// L2, I
int[] dp5 = new int[2];
// L2, A1
int[] dp6 = new int[2];
// F.
int[] dp7 = new int[2];
dp1[1] = 1;
dp2[1] = 1;
dp3[1] = 1;
dp4[1] = 0;
dp5[1] = 1;
dp6[1] = 0;
dp7[1] = 0;
for(int i = 1; i <= 30; ++i){
int iLast = (i+1) % 2;
int iNow = i % 2;
// it is infact one HMM transition.
dp1[iNow] = dp1[iLast] + dp3[iLast] + dp5[ilast];
dp2[iNow] = dp1[iLast];
// ...
// so on and so forth.
}. 1point3acres.com/bbs
return dp1[30%2] + ... dp7[30%2];
}

2. 冷面沉默大叔。第一题two sum smaller。第二题 coin change。第三题 coin change 打出所有case。最后一题 shuffle tree。 答得很顺。

3. 披头金发小伙。先是个sql的问题，选每个周一的前几个data什么balabala的。小哥表达很不清楚。楼主乱答了一通。小伙啥也不说。第二题类似 one edit distance，要比较每种方法的好坏，反复说有木有除了sort，hashmap以外更好的。
. visit 1point3acres.com for more.
4. 木纳白人胖哥。Number of Islands II. 楼主用union-find默写完了。胖哥没多说，只是记。楼主有几个typo也帮忙提示了。然后问如何从union-find的tree里remove node。——。——. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

5. 和蔼中国大姐。一道system design。 楼主把能记住的部分要求写一下：

1. 每一个user一次可以看到10个空位。不同的user在同一时间不能看到相同的空位。
2. 如果这个user不满意这10个座位，可以refresh出另外10个，把当前的10个覆盖。
4. 买了一个座之后，其余user的当前看到的10个位置如果饱含这个座，要去掉，给个新的。
5. 如果有user要买没看过的座，视为malicious behavior，要制止。