## Tuesday, November 24, 2015

Q1. Given char array and corresponding double array, return a random char that has the same probability as the double array.
Eg: char * a = "abc",   double * d = [0.2, 0.7, 0.1]. You should have 20% chance to return 'a', 70% to return 'b' and 10% to return 'c';
Follow up: how to test if the function is correct?
Solution:  convert the double array to intervals and generate random number (0 - 1) and check which intervals is the number in.
Eg: a:  0 - 0.2
b:  0.2 - 0.9
c: 0.9 - 1. visit 1point3acres.com for more.

Q2.  given millions of electronic books and each book contains hundreds of pages. Given a function OCR to convert the electronic image of book pages to text file. That is to say, scan the books first to get photo copy and then convert the image to text file. So in the process, there is supposed to be 5% error. How do we tell if two books are identical considering the error?.
Error can come from several cases liek:  "word random" -> "word ran dom";  "word random" -> "worded random"; "word random" -> "word     "
Solution: It's an open ended question, you can propose different approches.

Q1. Given a sparse excel file, design a data structure to effectively store all the informations.
Sparse means most of the excel are empty.
Write 4 functions: void set(int row, int col, int val),  int get(int row, int col), vector<int> getRow(int row), vector<int> getCol(int col)
getRow and getCol returns the corresponding row or column that is indexed at the input number which neglect empty cells.
Solution:
Using this one:    unordered_map<int, unordered_map<int,int>> myMap1, myMap2;
myMap1: (row -> (col -> val)) ;  myMap2: (col -> (row -> val)).
Follow up: what if there is a function eraseRow or eraseCol like in excel you can erase a whole row or column.
Hash table solution becomes unefficient because row index and column index changes and this cause erase time complexity to be O(n)
Solution : using LinkedList, and I have no time for coding

Round 3: Overlapping Intervals
Given a vector of intervals, return the interval that has the most overlap.
Eg: [0, 1], [2, 8], [3, 5], [4, 6], [9, 10].
return 3 and [4,5] because for interval [4,5] there are 3 overlapping intervals.
Solution:
sort starting and ending points and then scan. plus one if left node met, minus one if right node met.

Round 4: multiply strings
Given two integers represented by strings, return their product.
Follow up: how to increase time complexity and how to test it.
Solution is straightforward, just need to be careful about corner cases and invalid input.
Q1: 给了一个map<int,int> int_map, 还给了一个function： bool predict(int val); 函数是判断val是不是int_map的一个key。 感觉这个给的很无力啊，用find不就解决了的问题？
让写一段循环语句，删除int_map里面有val作为key的。
看上去简单，写的时候漏洞百出啊~大家可以写写看
for (auto it=int_map.begin();it!=int_map.end();) {
if (predict(it->first)) {
auto cur = it;
it++;.
int_map.erase(cur);
continue;
}
it++;
}.
Q2: 问C++的map 的insert函数的complexity是多少？ O(logN)

Q3: Given 2D matrix, N*N, element ranging from 1 - N^2, no duplicate.
return the length of longest consective path .

Eg.  1 3 5
2 4 6
9 8 7
Should return 5 because path 5 6 7 8 9 has the longest path length;

1. 给一个2D matrix，bool 型，初始状态是都是false,要求写一个flip函数，实现把其中一个element由false变成true。 要求是所有false element被翻转的概率相等。
1. 应该是random with blacklist，2维转1维,（i,j)->(i*n+j). from: 1point3acres.com/bbs

void flip(vector<vector<bool>> & matrix) {
int row = matrix.size();
if (row == 0) return;
int col = matrix.size();
if (col == 0) return;
vector<pair<int,int>> co;  // stores all the false elements’ coordinates
for (int i=0;i<row;i++) {
for (int j=0;j<col;j++) {
if (matrix[j] == false) co.push_back(make_pair<i,j>);
}
}
myFlip(matrix,co);
}

void myFlip(vector<vector<bool>> & matrix, vector<pair<int,int>> & co) {
int total = co.size();
int ran = rand()%total;  // generate a number between 0 and total-1
inr r = co[ran].first;
int c = co[ran].second;
matrix[r][c] = true;
co.erase(co.begin() + ran);  // erase (r ,c)
return;
}

0 1 0 0
1 0 0 1
0 0 1 0

[3 5 9]

When can't use extra space, 用reservior resampling

private static void flip(boolean[][] table){
int count = 1;
int m = table.length;
int n = table[0].length;

int[] index = new int[]{-1, -1};
Random r = new Random();

for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(table[i][j] == false){
int x = r.nextInt(count);
if(x == 0){
index[0] = i;
index[1] = j;
}

count++;
}
}
}

if(index[0] != -1){
table[index[0]][index[1]] = true;
}
}

private static boolean subTree(TreeNode root, TreeNode B){
//Check whether B is a subtree of A
if(root == null && B == null){
return true;
}else if(root == null || B == null){
return false;
}

if(root.val == B.val && sameTree(root, B) == true){
return true;
}

return subTree(root.left, B) || subTree(root.right, B);

}

private static boolean sameTree(TreeNode A, TreeNode B){
if(A == null && B == null)
return true;

if(A.val == B.val){
return sameTree(A.left, B.left) && sameTree(A.right, B.right);
}else{
return false;
}

}

flip() 的时间是O(1), 总共ini时候需要的时间和空间是O(MN).

2. 给两个二叉树，A 和 B 。 要求判断A 是不是B 的子树。 子树的意思是： A 是 B的一部分： 例如：
A
1
2 3
B
0
1 4
2 3

A 就是B的子树。.

2. 第二题很有意思，像是之前面经上面发的find identical subtree。这个可能是简化版，recursive应该可以做。
inorder traverse the two trees and make them to two arrays. compare the two arrays.
inorder可以identical啊，把null表示出来就行了， time complexity is O(kn)

step 2 是 O(n) 最后还是O(n*k)  k是A 中和B root->val相等的节点数

1.     static bool isPartof(TreeNode* root1, TreeNode* root2) {
2.         if(root1 == nullptr && root2 == nullptr) return true;
3.         if(root1 == nullptr) return true;
4.         if(root2 == nullptr) return false;
5.         if(root1->val == root2->val) return isPartof(root1->left, root2->left) && isPartof(root1->right, root2->right);
6.         else return isPartof(root1, root2->left) || isPartof(root1,root2->right);
7.     }

random这题就是用segment tree。

PS：大家在面试的时候一定要注意简单题，我面的时候第三面是最简单的，code也是基本很快完成了，但是最后的feedback却是最差的，面试官评论貌似是不太能跟上我的思路= =，是说我communication太差了么。。反正大家注意简单题的坑

1. 有一个tree，不是binary，define weight as 它的子数的点的个数。weight 不是treenode的field.
define weight as 它的子树的点的个数
goal是对整个树按weight排序

2. 手机app，response时间长，怎么处理。解决了怎么测试。不是写代码题。
3. 第一题的tree，会常改变，要记录什么时间tree长什么样，用什么数据结构纪录。纪录很多很多有什么问题，怎么办。

1) LC原题（#286 walls and gates），只不过换成博物馆里有小偷和艺术品

2)若有一排Ｎ个位子，上面已坐了一些人，假设已坐的旁边不能再坐人，问最多还可以再坐进多少人

xoox-> 0
xooox->1
xoooox->1
xooooox -> 2
public int populate(boolean [] seats){
int num = 0;
int start = 0;
while(start < seats.length && seats[start]==false)
start++;
num += start / 2;
int end = start+1;
while(end < seats.length){
if(seats[end]==false)
end++;
else{
num += Math.max(0,(end-start-2)/2);
start = end;
end++;
}
num += Math.max(0,(end-start-2)/2);
return num;
}

V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期

y.u.u.e --> true
you*be --> true
you.. --> false.
*u*u* --> true

1
\
2- 3
\ /
4
|
5-8
|/
7

2. 即使在最坏的情况下，因为是多台机器并行运算，还是要比我之前提出的用一台机器轮流查询所有服务器要快一点吧。

ii) 最短图案包含 4 个点
iii) 最长图案包含 9 个点
iv) 路径不得跨越未访问的点，但是可以跨越访问过的点

0-1-2-4-6-7-8 或者 7-4-1-0-2-6-8 是合法的

0 1 2
3 4 5
6 7 8

Onsite Round #2 一个美国中年人。第一题设计一个system可以返回Top K Google search results 。这道题就是Map Reduce 和 Quick Select的结合。但是我没有一下子就说出来，还是通过One CPU with unlimited RAM, One CPU with limited RAM, distributed system这样循序渐进的方式讨论的。我们大部分时间就是在讨论不用同方式的trade-off。第二题是一个简单的int pow(int n,int k)，用logN写写就好。面完了发现带我吃饭的人还没来，于是索性和他讨论讨论如何返回一个字符串来解决overflow的问题。还是基于字符串乘法的基础上，可以做两方面的优化。

1. 三种水果，价钱分别是x,y,z给你m的钱，一定要把钱花到不能买水果的情况下，最少买多少水果一开始说贪心算法，先从最贵的买起，然后他说most case work，让我想反例。哎，竟然没想出来，然后他给了2,5,6;10这个例子。然后我用dfs做了，不知道为什么他没有很看懂代码，然后讲了不少时间，然后他说差不多明白了，我们已经在这道题花了太多时间了.

1. dp[i] = min(dp[i], dp[i-p[j]] + 1)    0<=j<p.length, i>=p[j]
2. 给定这个形式2^i*5^j依次输出i=0到j=0开始依次递增的数列，例如：1，2，4，5，8，10之类的

LeetCode 263 + 264 Ugly Number I II
public static void solve(int n) {
List<Integer> list = new ArrayList();
int i2 = 0, i5 = 0;
for (int i = 0; i <= n; i++) {
int t = Math.min(list.get(i2) * 2, list.get(i5) * 5);
if (t == list.get(i2) * 2) {
i2++;
}
if (t == list.get(i5) * 5){
i5++;
}
print(t);
}
}

int nthUglyNumber(int n) {
vector<int> res(1, 1);
int l2 = 0, l3 = 0, l5 = 0;. more info on 1point3acres.com
for (int i=2; i<=n; i++) {
int m2 = res[l2] * 2, m3 = res[l3] * 3, m5 = res[l5] * 5;
int next = min(m2, min(m3, m5));
if (next == m2) l2++;
if (next == m3) l3++;
if (next == m5) l5++;
res.push_back(next);
}
return res.back();
}
2. Leetcode: GreyCode
1.  Coding:
(1) 设计一个SparseVector （就是一个超vector，大部分elements都是0）的class实现dot product的操作。follow-up1:如果一个vectormillionsof non-zeros）， 另一个vector很短（hundredsof  non-zeros），如何化。follow-up2:如何利用index的关系（比如设计class定按照增的原non-zeroelementsindex一步优化。
(2) Leetcode：3 Sum
2. System Design：设计一个K recent contact 的service，就是当用户把鼠标点到chat对话框的时候，自动弹出K个最近的联系人。follow-up是如果要弹出K个最熟悉的人怎么设计，以及资源估计（需要多少台机器来做数据存储，多少个处理request等等）。
3. Research conversation。 最后15分钟做一道简单的coding题，最常见的Leetcode:Valid Palindrome原题
4. Machine Learning：SVM和logistic regression的对比分析。对全Palo Alto的居民做全样本调查，收集性别、血型、身高、体重、是否抽烟、是否有高血压。。。等数据，然后最回归分析，发现抽烟和高血压是负相关，即抽烟的人不容易患高血压。与intuition相反，为啥？设计一个news feed的排名算法，用用户的implicit反馈做label：share，clickthrough，like等。

5. Coding：
(1) Leetcode: Subset. 需要用iterative的方法做，不能递归。
(2) Leetcode:  Reverse words in a string.
Leetcode: Find minimum in arotated array.

1. 实现replaceStr(strings, string foo, string bar)。即在文档s中把所有foo的occurrences都替换成bar。算复杂度。
2. 实现 doublecubeRoot(double x)。可以用二分搜索或牛顿迭代法求解。

A和B两个setof words。写一个方法返回(a) 只在A中出现的words. (b) 只在B中出现的words.(c) 同时在两个set中的words。follow-up是如果A和B很大，无法全都装进内存里，如何处理。

1. 给一个dictionaryof words（可以重复），实现一个方法判断一个document是不是可以用dictionary里面的words来表示出来。如果一个word在dictionary里出现了K次，那么它在这个文档里最多也只能出现K次。
2. 有很多jobs在一个machine上运行，每个job的属性有[jobID.UserID, startTime, endTime, ramRequired] 。求每个UserID的peak ram usage是多少。如果将方法扩展到大数据上？（多线程，多机）

(1) find second largestelements in an array.
(2) 给一堆2Dplane上面的点，判断这些点是不是vertical symmetric。即：是否存在一条线x=k。使得这些点关于这条线对称。follow-up是如何处理可以容许有一个点不对称的情况。
2. Rains on the sidewalk.

2是把[0,1]的区间分成100个宽0.01的小格，每个小格维护两个状态，一个是从左边界算起被打湿的长度，一个是从右边界算起被打湿的长度。每次有新的雨点就更新与该雨点有overlap的两个小格的状态。如果某个小格两个长度加起来大于或等于0.01，则该小格已经被完全打湿。再维护一个counter，每次有新的小格被打完全打湿，counter加1。这样就可以O（1）复杂度实现更新小格状态和判断是否sidewalk完全被cover。
3.(1) 给一个2Dvector表示一个image。如果image中有值为0的pixel，就删除掉该pixel所在的行和列，最后返回一个处理后的新的image。
(2) 统计一个uint8的image的histogram。返回是一个size是256的array，其中第K个element是image中值为K的pixel出现的次数。
4.
(1) 实现一个swap的template。问如果输入的type是如下的class
class MyVector{
int*buf;
intsize;
};

4(1) 交换指针(2) 读一段程序，大概是在一个array中找一个index，使得index左边的summation和右边的summation最接近。如何用O(1) 的复杂度实现。

4(2) 扫描一遍array记下total。然后从左边扫描并累积，再从total里面减去左边的累积量得到右边的累积值。扫描一遍就知道左右相差最近的index在哪

(3) OOP design： 设计一个Google Car 的Sensor SynchronizationSystem。从多个有着不同的CPU时钟的sensor读取message，并找到不同sensor的同步关系
5. Research conversation.

learn to rank的算法 面试的时候都要记得吗？

Define tree class。 Binary tree 都有哪些operation，一一实现这些operation（delete没有写完

2. Binary tree 两个node之间的距离。我就是用common ancestor的方法做的。问了复杂度。如果不用递归该怎么做？

Related: Design a data structure for sparse matrix

1. 给你一排栅栏，有N个，你要给它们上色。你有黑白两种颜色，颜色相同的栅栏最多只能两块连在一起，问你一共有多少种上色的方法。用DP做了，问了下复杂度什么的，做到常数的空间复杂度。

public int solution(int n) {
if(n <= 0)
return 0;

if(n == 1)
return 2;

int lastTwoSame = 2; // till current n, # of methods with last two same, now n = 2
int lastTwoDiff = 2; // till current n, # of methods with last two different, now n = 2;

// if last two fences have the same color, you have 1 choice for current one, which lead to
// new last two have different colors.
// if last two fences have different color, you have two choice for current one, one will lead
// to new last two have same colors, the other will lead to new last two have different colors.
for(int i = 3; i <= n; i++)
{
int temp = lastTwoSame;
lastTwoSame = lastTwoDiff;
lastTwoDiff = temp + lastTwoDiff;
}

return lastTwoSame + lastTwoDiff;
}

https://community.topcoder.com/stat?c=problem_statement&pm=11512&rd=14546

2. Leetcode原题，BEST TIME TO BUY AND SELL STOCK。分别问了一次，两次，还有N次，还问我有没有做过。我说三个都做过，然后简单给了思路。最后说N次的时候自己把思路记错了，两行代码的顺序搞反了，面试官发现了说逻辑有问题，我自己也一时没反应过来，还坚持说是对的。。。面试官也不知道要怎么改，就说这个一下子也理不清。
3. 最后还有5分钟，面试官说我们还能做点什么呢。我心想，不应该就是我的提问时间了嘛。。。

dp[m][n] represents the maximum number of string to choose for m zeros and n ones in [0...i - 1] subarray
assume ith element has x zeros and y ones.
dp[m][n] = (m - x >0 && n - y > 0) ? max(dp[m][n][i - 1], dp[m - x][n - y][i - 1] + 1) : dp[m][n][i - 1];
dp[m][n][0] = 0;

dfs我感觉是exponential
dp 的复杂度还有再乘以最长字符串长度~

2.先告诉我背景知识，图像中很多显示的都是近似。比如显示的一个圆并不是一个完美的圆，当你放大会发现都是相邻的像素点近似而成的。然后先让我开一个数组代表一个图片，里面数据的范围是0到255（黑是0，白是255），应该用什么数据类型。我没反应过来，面试官就说应该用unsigned char，我说哦。然后给了我一个函数，VOID PAINT(INT X, INT Y)，这个函数就是将图面中坐标为（X，Y）的方格涂黑（0）。要我设计一个函数 VOID PAINT(FLOAT X, FLOAT Y)。因为给你的两个坐标不是整数，所以相当于会覆盖到相邻的四块方格，然后每个方格按照被覆盖的面积，涂上对应比例的灰度。比如某个方格被覆盖了一半的面积，那这个方块就是涂成灰色（127）。也就是模拟一下图像里面近似的做法。

1. 给你一个文档，里面存的都是一个个文件的绝对路径，和这个文件的拥有者。比如“/FOO/CHH/1.TXT，LINDA”，“/FOO/CHH/2.TXT，PETER”，“/FOO/3.TXT，LINDA”。然后给你一个路径，找出这个路径下以及所有的子目录下哪个人的文件最多。比如给你“/FOO/SHH”那LINDA和PETER一样多，给你“/FOO”那就是LINDA多。

1. 给你一个排序好的整数数组，让你在里面找四个数（每个数可以重复用）使得它们的和等于给定你的值V。其实这道题就是用HASHTABLE的N^2复杂度的做法，不难。我一看是排序好的，第一个想到的就是从两头夹逼的做法，就说把V分成两部分，一个是M，一个是V-M，然后每部分看看能不能等于两个值之和。之后在面试官的一步步提示下才想起来用HASHTABLE就好了。讨论了复杂度什么的。
2. CRACKING THE CODE INTERVIEW 13.9， WRITE AN ALIGNED MALLOC AND FREE FUNCTION。我和面试官说这道题是书上原题，大叔说哦这样啊，那我们换一道。
3. 问你怎么保存一颗二叉树。我说存一个INORDER，再存一个PREORDER或者POSTORDER。大叔说只能存一个，我说那就把树看作是FULL TREE，缺少的子树就存一个特殊符号标记一下，这样的话只需要存一个INORDER就行了，大叔说行了。

第二题，         1
/   \
2      3
/   \   /  \
4      5     6
如上图，有好多节点，给一个目标节点，求出从root到目标节点有多少条最短path。 比如，目标节点为2，就有1条path, 目标节点5，有2条path.
这题是个坑，我跳进去了。写完之后，三叔说，我不喜欢你的code,但你写的也是对的

input就是treenode，只不过和BST不同之处在于两个相邻的node会有同样的subtree。

implement 一个叫logger的interface，

request A |-------------------|
request B     |--------|
B 结束之后并不能打印，要A结束之后才能打印，但是A结束之后就会立马打印出A和B。所以需要一个合适的data structure储存已经结束的B。

while (!heap.isEmpty()  &&  heap.peek().endTime != null ) {
request a= heap.poll();
map.remove(a.id);
print(a);
}

note: 如果有一个词在一行放不下，放到下一行。

4也是多余的吧？最多只可能有3个数字，所以需要检查1, 2, 3

~  ~   ~   ~   ~   ~  ~
~  1   2   2   3  (5) *
~  3   2   3  (4) (4) *
~  2   4  (5)  3   1  *
~ (6) (7)  1   4   5  *
~ (5)  1   1   2   4  *
*  *   *   *   *   *  *

IntStream A和B本身都是set。

A = [1,2,3].
B = [1,4,5,6]

First Round. Given k stack of coins, take n conins, what is the max sum of the n coins.
eg. stack1: 1, 4, 700, 3
stack2: 5, 10, 6
if n = 2, then the max sum should be 5+10
if n = 3, then the max sum should be 1+4+700

Second Round. Array Longest Adjacent Consecutive Sequence
eg. [6,1,2,5,3] -- return 2, [6,1,2,3,5] -- return 3

Follow up: Generic Tree Longest Consecutive Sequence
eg.
1
/ \  \
5   4  2
/   \
7     3
\
6

return 3.
int max = 0;
public int findArr(int [] nums){
if(nums.length<1) return 0;
int temp = nums[0];
int length = 1;
int max = 0;
for(int i = 1;i<nums.length;i++){
if(nums[i]== temp+1)
length++;. 1point3acres.com/bbs
else
length = 1;
max = Math.max(max,length);
temp = nums[i];
}
return max;
}
public int findTree(TreeNode root){
helper(root,1);
return max;.
}
public void helper(TreeNode root,int length){
max = Math.max(max,length);.
if(root == null) return;
List<TreeNode> list = new ArrayList(root.children);
for(TreeNode t: list){
if(t.val==root.val+1)
helper(t,length+1);
else helper(t,1);
}
}

Third Round.
a. Two arrays of string find the common element.
A - HashSet.
Follow up: What if the two array are very large (10TB).
A - MergeSort

b. Summary Ranges.

Fourth Round.
a. 2Sum Smaller
Given an array of n integers nums and a target, find the number of pair i, j satisfy the condition nums[i] + nums[j] < target.

http://yuanhsh.iteye.com/blog/2194143
1. boogle question

int [][] min = new int [m][n];
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if (i == 0 && j == 0)
min[i][j] = 1;
else if (i == 0) {
min[i][j] = num[i][j-1] == num[i][j] ? min[i][j-1] + 1 : 1;
}
else if (j == 0) {
min[i][j] = num[i-1][j] == num[i][j] ? min[i-1][j] + 1 : 1;
} else {
if (num[i][j] == num[i-1][j] + 1)
min[i][j] = min[i-1][j-1] + 1;
else if (num[i][j] == num[i][j-1] + 1)
min[i][j] = min[i][j-1] + 1;
else
min[i][j] = 1;
}
}
}
2. 给定一个array，输入是0到99之间的整数，输出一个string包括所有miss掉的数，如果相邻长度超过2，则输出比如3-5而不输出单个数。

3. 给定一个target的整数，将他分解成square的和，保证这个分解的term最少。

`int numberOfTerm(int n) {if (n == 1)return 1;int min = n;for(int i = 1; i < sqrt(target); i++) {min = Math.min(numberOfTerm(n-i*i) + 1, min);}return min;}`

`int numberOfTerm(int n) {int[] numOfT = new int [n];for (int i=0; i<numOfT.length; i++) {if (i == 0)numOfT[i] = 0;elsenumOfT[i] = i;for (int j=1; j<=sqrt(i); j++) {numOfT[i] = Math.min(numOfT[i], numOf[i-j*j] + 1);}}return numOfT[n-1];}`
4. 给定一个2darray，里面包含integer，水可以从integer大的地方向小的或相等的地方流。 假设上边和左边是pacific，右边和下边是atlantic， 求所有能到达两个大洋的路径。

5. 给定一些box的w和l，假设box1可以放在box2的条件是宽和长都小于box2，求最长的可能放进盒子的序列，实际上这道题很像Career cup上一道身高和重量叠人墙的题目。我们只需要将box按长度sort，然后如果长度相同再按宽度sort，然后扫描一遍整个数组，看看连续的宽最多有多少即可。
6. system design，设计一个键盘的输入法，不需要一个一个按，而是快速的滑动，怎样设计，怎样给suggestion