http://www.1point3acres.com/bbs/thread-201356-1-1.html
给一批人， 这些人每人都花了一笔钱，
让算， 谁给谁多少钱， 能让所有人都达到平均数
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;
}
}
}
http://www.1point3acres.com/bbs/thread-199194-1-1.html
这不和minimum window substring一样吗
http://www.1point3acres.com/bbs/thread-197372-1-1.html
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.
我只想到 brute-force，或是用 Map 存整個第一棵樹再掃第二顆做比較，想請問有沒有更好的想法？
把Tree用DFS做serialization , 就变成了找substring的问题了，可以用kmp或者直接用内置方法做吧
参考pre-order遍历序列化一棵二叉树。然后build这个字符串的失败函数。假设某字符的失败函数值为最大，且这个子串不以空开头，即为最大重复子树
假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照group在后序遍历中第一次出现的时间顺序决定。
这样我们可以一边后序遍历子树，一边建两个hashmap:
(root value, group id of left, group id of right) -> group id of root
group id -> subtrees of this group
这样我们做一遍后序遍历同时维护层数最高、subtree数量>=2的group id就行了。
这个其实跟用整棵子树的serialization作为key做法差不多，只是对key作了压缩。
group id就是一个数字，对应一棵unique的子树。
比如一棵3个结点的树，根结点是10, 两个node是20， 20.
那么group id->node的hash table存的是
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
所以返回group id 1下面的两个node.
2. Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array
http://www.1point3acres.com/bbs/thread-190439-1-1.html
1. 友善印度小哥。说是考察一群学生的出勤率，如果连续3天来晚（L）就记作差（F），或者任意两天旷课（A）也记作F。成为F就一直是F了。考察30天后，有多少种F的排列组合。
楼主一开始以为是dp，像 decode ways 一样的用两个variables记录之前两天的结果就好了。然后就陷入泥沼了。小哥提示用 automata 解释。画出图来后楼主基本已经蒙了。呵呵，大家可以自己画一画。每一天可以有7种states， 楼主真的呵呵了。自从 valid number 之后就再没用过automata了。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
第一个题可以用2个automata的乘积么 The Product Construction for Automata
第一题就是HMM啊。做ML应该都知道。
恩 第一题仔细想想 还是dp的问题 其实也是一个HMM 每个时刻8个状态. 前一个天8个状态合起来求后一天的. 他提示automata 感觉反而能让人弄迷糊 实在是邪恶
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];
}
我只知道简单做法：
就是dfs 每一天三种可能 （这个要和你confirm）就是L A 或者 good
然后递归30天后检查这种排法是否F，更新sum变量
可以在dfs过程中检查是否F，然后pass onto最后的检查. 鍥
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。 楼主把能记住的部分要求写一下：
做一个cinema的卖票web application。有很多users，在client side。server只有一个。要求�1point3acres璁哄潧
1. 每一个user一次可以看到10个空位。不同的user在同一时间不能看到相同的空位。
2. 如果这个user不满意这10个座位，可以refresh出另外10个，把当前的10个覆盖。
3. 每个user只能buy一个座，这个座必须是她看过的（包括之前覆盖过的和当前的10个）。买座位是通过输入座位号。
4. 买了一个座之后，其余user的当前看到的10个位置如果饱含这个座，要去掉，给个新的。
5. 如果有user要买没看过的座，视为malicious behavior，要制止。
6. user决定refresh或者buy的时间只有2s。
其余还有2个policy楼主记不清了。大姐问得很细，笑里藏刀地，包括用什么data structure，放在client还是server side，performance怎么办等等。哎，我估计architect才能答出来这题。
几天接到hr电话说挂在第三轮了的SQL了，因为楼主在最开始的self-estimation的说自己的SQL 是 6/10。我擦你呀啊！楼主的确是有很多SQL经验啊，但是每个SQL的API都不一样吧。。。况且楼主都是用的打包好的API啊。6分很高吗？多高是高啊。。
给一批人， 这些人每人都花了一笔钱，
让算， 谁给谁多少钱， 能让所有人都达到平均数
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;
}
}
}
http://www.1point3acres.com/bbs/thread-199194-1-1.html
| 给定一个句子, 和若干个搜索词, 求包含所有搜索词的最短句子长度. 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枚举所有. 希望大家提供更好的解 |
这不和minimum window substring一样吗
http://www.1point3acres.com/bbs/thread-197372-1-1.html
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.
我只想到 brute-force，或是用 Map 存整個第一棵樹再掃第二顆做比較，想請問有沒有更好的想法？
把Tree用DFS做serialization , 就变成了找substring的问题了，可以用kmp或者直接用内置方法做吧
参考pre-order遍历序列化一棵二叉树。然后build这个字符串的失败函数。假设某字符的失败函数值为最大，且这个子串不以空开头，即为最大重复子树
假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照group在后序遍历中第一次出现的时间顺序决定。
这样我们可以一边后序遍历子树，一边建两个hashmap:
(root value, group id of left, group id of right) -> group id of root
group id -> subtrees of this group
这样我们做一遍后序遍历同时维护层数最高、subtree数量>=2的group id就行了。
这个其实跟用整棵子树的serialization作为key做法差不多，只是对key作了压缩。
group id就是一个数字，对应一棵unique的子树。
比如一棵3个结点的树，根结点是10, 两个node是20， 20.
那么group id->node的hash table存的是
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
所以返回group id 1下面的两个node.
2. Input a matrix, where every number is greater or equal to the numbers on its right and bottom. Output a sorted array
http://www.1point3acres.com/bbs/thread-190439-1-1.html
1. 友善印度小哥。说是考察一群学生的出勤率，如果连续3天来晚（L）就记作差（F），或者任意两天旷课（A）也记作F。成为F就一直是F了。考察30天后，有多少种F的排列组合。
楼主一开始以为是dp，像 decode ways 一样的用两个variables记录之前两天的结果就好了。然后就陷入泥沼了。小哥提示用 automata 解释。画出图来后楼主基本已经蒙了。呵呵，大家可以自己画一画。每一天可以有7种states， 楼主真的呵呵了。自从 valid number 之后就再没用过automata了。. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
第一个题可以用2个automata的乘积么 The Product Construction for Automata
第一题就是HMM啊。做ML应该都知道。
恩 第一题仔细想想 还是dp的问题 其实也是一个HMM 每个时刻8个状态. 前一个天8个状态合起来求后一天的. 他提示automata 感觉反而能让人弄迷糊 实在是邪恶
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];
}
我只知道简单做法：
就是dfs 每一天三种可能 （这个要和你confirm）就是L A 或者 good
然后递归30天后检查这种排法是否F，更新sum变量
可以在dfs过程中检查是否F，然后pass onto最后的检查. 鍥
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。 楼主把能记住的部分要求写一下：
做一个cinema的卖票web application。有很多users，在client side。server只有一个。要求�1point3acres璁哄潧
1. 每一个user一次可以看到10个空位。不同的user在同一时间不能看到相同的空位。
2. 如果这个user不满意这10个座位，可以refresh出另外10个，把当前的10个覆盖。
3. 每个user只能buy一个座，这个座必须是她看过的（包括之前覆盖过的和当前的10个）。买座位是通过输入座位号。
4. 买了一个座之后，其余user的当前看到的10个位置如果饱含这个座，要去掉，给个新的。
5. 如果有user要买没看过的座，视为malicious behavior，要制止。
6. user决定refresh或者buy的时间只有2s。
其余还有2个policy楼主记不清了。大姐问得很细，笑里藏刀地，包括用什么data structure，放在client还是server side，performance怎么办等等。哎，我估计architect才能答出来这题。
几天接到hr电话说挂在第三轮了的SQL了，因为楼主在最开始的self-estimation的说自己的SQL 是 6/10。我擦你呀啊！楼主的确是有很多SQL经验啊，但是每个SQL的API都不一样吧。。。况且楼主都是用的打包好的API啊。6分很高吗？多高是高啊。。
