http://www.1point3acres.com/bbs/thread-148695-1-1.html
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
LinkedList的思路是 吧每行每列的元素的cell存下来，node记的是与前面cell的差值。这样删除一行就只用改后面一个列的数据。
比如 原来有1 6 8 9 14
本来删除第6行的时候，要变成1 7 8 13 需要修改6 后面的 8 9 14 的index.
但是如果我们存的是前后index的差值，我们只需要修改删除行的后面那个index 。
比如 一样的例子： 1 5 2 1 5
我们还是删除一行，只需要改成 1 6 1 5 我们只需要修改一个就好了。
思路是这样，没写code。还要拓展成二维的
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.
http://www.1point3acres.com/bbs/thread-141774-1-1.html
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;
BFS: http://www.1point3acres.com/bbs/thread-141774-2-1.html
两道题：
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
不知道有没有更好地办法，因为当blacklist也就是选过的值增多的时候，复杂度可以到O(mn)，
搞一个 unordered_set<pair<int,int>> coordinates 来存所有false element的坐标。然后产生一个[0,coordinates.size()-1]的随机数x，coordinates[x]就是我们要翻转的element啦。 存coordinates 要O(n) time and O(n) space. 随机数和翻转都是O(1),所以总的复杂度是O(n).
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;
}
我说一个flip()是O(M+N)时间的实现，空间复杂度是O(M)。其中M，N分别是矩阵的行列数。
一开始先创建一个长为M的cum数组。cum[i]代表“到第i行（含第i行）为止，矩阵中有多少个false”。比如大矩阵是：
0 1 0 0
1 0 0 1
0 0 1 0
那么cum数组就是
[3 5 9]
我们用cum数组来决定下一个随机数出现在哪一行。比如对[3 5 9]，我们先产生一个1~9之间的随机数，比如4，然后在cum中找“第一个大于等于4”的数字，是第二个数5。那么我们就在第二行产生随机数。然后，因为5和其前面的数3的差为2，说明这一行有2个false，那么我们再产生一个[1 2]间的随机数，比如1。 然后遍历第5行，直到找到第1个0为止。这一步花费O(N)时间.
然后我们要更新cum数组，具体做法是把第二个数字和之后的数字都减1，最后cum变成[3 4 8]。这一步花费O(M)时间。
其实你生成一次随机数就可以了，比如你的例子中的4，那么4-3就是它在第二行中的位置。
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;
}
}
所以最后总时间是O(M+N)，空间是cum数组消耗的O(M)。
第二题 用 identical tree + recursive searching
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的时间复杂度，但是允许一定的setup 时间。
flip() 的时间是O(1), 总共ini时候需要的时间和空间是O(MN).
然后以上方法其实可以把空间复杂度也降到O(1), setup 时间复杂度还是 O(MN), 说白了就是用原来以为有的矩阵。。把里面的内容全给改了。。维护一个last position的指针，每次random完和last position 对调。。
补充说一下：因为这题是要返回剩下集合里随机的坐标，所以其实矩阵的I, J即使乱掉了也无所谓。。
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)
第一题类似于孤岛问题，follow up是如果在来个stream，每次输入一个点是岛点，问你怎么update已经有的数组并返回新的岛的个数。
第二个处理读取文件长度的，给你个每次读4096个Byte的function, 让你implement一个可以读取任意长度N的function，要用他给的4096 function。从同一个文件中读取，由于每次读取的长度不一定是4096的倍数，所以多读的要存起来，下次再读的时候要把这存起来的先读入。就是要考虑各种情况。第三个是求曼哈顿长度的，给一个2D数组，里面有1,2,-1若干，问所有1到2的manhattan distance最短的是多少。用 DP
每个1到所有2的距离取最小的，然后再在这些值中取最小的
第四个3 sum
http://www.1point3acres.com/bbs/thread-148676-1-1.html
第一面：国人帅哥，find the longestsubstring with at most m distinct characters in a stream that cannot fit intomemory， 用moving window和LRUcache的思路解决
第二面：美国小哥， set(x, y, val)， getSum(x,y) in very large table，所以你不能把table存成array的形式，用hashtable也不行，因为求sum的时候没法保证顺序，会loop到一些不需要用的点，所以必须要red-black tree，最后就是twodimensional rb tree解决，做完后问各种怎么解决multithreading，cannot fit into memory， overflow之类的问题
第三面：美国大叔，给两个长方形形找出并求出overlapping的坐标和面积，写出各种testcases，然后各种问如何扩展到很多长方形上，怎么用我写的function来把长方形分成多个长方形之类的
第四面： 美国大叔， 就是给一个无重复的排序数组，给一个rand（），这个function返回随机数在[0, 1)之间，然后让你写一个getRandom，返回一个在数组上下界range里，但是又不在数组里的数，每个这样的数必须被返回的几率相同。
random这题就是用segment tree。
PS：大家在面试的时候一定要注意简单题，我面的时候第三面是最简单的，code也是基本很快完成了，但是最后的feedback却是最差的，面试官评论貌似是不太能跟上我的思路= =，是说我communication太差了么。。反正大家注意简单题的坑
http://www.1point3acres.com/bbs/thread-148668-1-1.html
1. 有一个tree，不是binary，define weight as 它的子数的点的个数。weight 不是treenode的field.
define weight as 它的子树的点的个数
goal是对整个树按weight排序
第一题就是要按weight排序，weight是要自己算，面试官说需要的话自己写个函数～
2. 手机app，response时间长，怎么处理。解决了怎么测试。不是写代码题。
3. 第一题的tree，会常改变，要记录什么时间tree长什么样，用什么数据结构纪录。纪录很多很多有什么问题，怎么办。
就是想要存更改历史哈，包含（timestamp，tree）信息，我觉得要考察的就是如果历史很大，entry很多，用什么数据结构合适。
自定义一个无向的图,然后，求这个图里有多少个三角形。三角形的定义是，三角形abc中,(a,b), (b,c),(c,a)都相连。 半小时后拿到onsite...
对每个点a，找它的neighbor b，看a和b有没有共同的neighbor c，如果有，为了去重，我直接把a从b和c的neighbor里删掉了。
用邻接矩阵存，比如A，然后A^3得到新的矩阵B，它的迹除以6就是三角形个数
给一堆长方形，求它们的面积和。长方形自定义。
长方形那题，就是让处理overlap的。两两处理，如果有重叠，那么，保持其中一个长方形不变，然后把另一个拆开，使原本重叠的两个长方形变成不重叠的多个长方形。
做法为：把所有长方形上下边（共2N条）按照纵坐标排序，并且每条边标记是长方形的下边还是上边。然后从前往后扫描，用一个数组来记录边的横坐标，对于每条扫描的边横坐标（l, r), 就把数组l，r 所有index的所有数值＋1, 这一步cost O(N) 时间，所以可以用segment tree优化，这样只需要O(logN). 没碰到一条边就加上当前那一条边和下一条边所夹的面积。
所以，最后总时间可以是O(N^2) 或是O(NlogN) 如果你用segment tree来维护数组的话。
拆分长方形是很complicated的，因为长方形可以两两重叠，三三重叠等等，面积很容易算重了，这题其实可以按边的纵坐标排序，然后从小到大扫描，用segment tree维护, O(NlogN)。
因为长方形重叠的可能性千变万化，所以计算面积时为了避免重复，每次只累加相邻两条边所夹的面积，相邻两条边所夹的面积等于(边i纵坐标所对应的水平线上所有被边横坐标所覆盖的长度总和) * (边i + 1的纵坐标－边i的纵坐标). 第二个括号不用计算，关键在于计算第一个括号，第一个括号naive计算方法自然是对每一组(l, r)，都把l，r之间的index元素一个一个加1，然后便利一遍横坐标数组，用时O(N). 但是注意，l，r是连续的，并且长方型每一个下边，必定对应一个上边，利用这个对称性，可以用segment tree维护，segment tree每一个节点存贮这个节点所对应的区间里被覆盖的总长度，所以每一次操作可在O(logN)完成。
http://www.1point3acres.com/bbs/thread-147304-1-1.html
第一题，一堆数，找出和最接近0的两个数；
第二题， 1
/ \
2 3
/ \ / \
4 5 6
如上图，有好多节点，给一个目标节点，求出从root到目标节点有多少条最短path。 比如，目标节点为2，就有1条path, 目标节点5，有2条path.
这题是个坑，我跳进去了。写完之后，三叔说，我不喜欢你的code,但你写的也是对的
其实三叔应该是不喜欢我的算法，我用bfs做的，他的意思是，应该巧妙使用pascal triangle
input就是treenode，只不过和BST不同之处在于两个相邻的node会有同样的subtree。
implement 一个叫logger的interface，
题目是酱的，logger里有俩个method,分别叫做startRequest和endRequest,input都是request id,和时间，return是void.
每一个request都有 独一无二的id,并且开始和结束都需要分别调用那两个method。当一个request结束之后，需要打印出来它的id,开始时间以及结束时间，但是，要按开始时间先后打印。
不是全部结束后一次性打印呢。你可能想的复杂了。
假如是这样的：
request A |-------------------|
request B |--------|
B 结束之后并不能打印，要A结束之后才能打印，但是A结束之后就会立马打印出A和B。所以需要一个合适的data structure储存已经结束的B。
首先需要一个HashMap,存(id,request).
接着，需要一个queue存所以request的id或者request本身. 我选择了PriorityQueue并以开始时间排序,因为多线程的时候，单纯的Queue不能确保request是按照开始时间排序的。
每次endRequest的时候，赋给这个request end time, 同时
while (!heap.isEmpty() && heap.peek().endTime != null ) {
request a= heap.poll();
map.remove(a.id);
print(a);
}
哦对了，面试官说，多线程的时候应该用PriorityBlockingQueue. 所以用BlockingQueue应该也是可以的吧。
最后一题，followup 是 multithread来着，我这题用heap写的
multithread的话就用synchronize和concurrent的data structure，像priorityblockingqueue，concurrent hashmap
题目很简单，但是感觉自己没有好好把握这次机会，主要是第二面，基于我的code的一些改进，答得不好，整个人反应及其迟钝。
http://www.1point3acres.com/bbs/thread-147302-1-1.html
第一轮： 给一个 M * N的screen，和一个String,比如“Hello World", 请问整个screen能放下多少个string。
note: 如果有一个词在一行放不下，放到下一行。
这一轮感觉就是纯的字符串处理。
第二轮：给一个sorted array， 求出是否含有popular item。 popular item定义就是大于size的1/4。我给出了O（n)解法和代码。面试官follow up O(logn)。
找n/4 n/2 3n/4 n这几个candidate，然后分别用二分搜索看长度满不满足
第二题只需要检查0, 1/4, 2/4, 3/4 4/4位置的元素看它们是不是就可以了，检查每一个数用二分搜索找左右boundary算个数，所以是(10 logn) = logn
检查0是多余的，因为如果0的数字是popular的，那在1/4处还是它。
4也是多余的吧？最多只可能有3个数字，所以需要检查1, 2, 3
最后一个位置不多余啊，最后1/4段包括4/4那个点不包括3/4那个点。
第三轮：flow water
~ ~ ~ ~ ~ ~ ~
~ 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 *
* * * * * * *
给定一个grid，判断是否有点技能到达~,也能到达*。就用图的DFS,BFS做。
第四轮：给一个没排序的array，删除里面的duplicate，保留原来里面item的顺序。可能有多个重复的items。要O(n)解法
因为要o(n)，是map+double linkedlist的解法么？
第五轮：给一个String[] array, 和任意一个移动的window size k， 对array里的元素位置进行改变，使得window里的元素不重复. 要efficient的解法
考虑的情况很多，window就是在输入的string[] array里移动，windows里的元素可以是任何string。
是不是重新排列array使得相同string的distance至少为k？
这可以是一种解法，有很多种可能性，输出其中一种就行了。
我能想到的办法就是建一个map看每个词的出现次数， 然后根据map重新建一个array，做到相同的elements之间的距离大于k.不过这样应该是O(n) time O(n) space.
噢time应该是O(NlogN)因为需要按照出现次数排序
第五题应该是字符串重排， 要求相同字符的间距>k的变种题. 使用Heap可以快速解决。 大概是HashMap统计词频， Entry<Character, Integer> 作为item 放进Max Heap, 以Integer重复数量作为排序因子。 然后每次从Heap取出k个元素append到StringBuffer, Integer分别-1之后再放回Heap. 再取出K个entry重复就好了
http://www.1point3acres.com/bbs/thread-147293-2-1.html
一问warm up：sort color
二问：给一个stream类，里面有next()方法和hasmore()方法，要求写一个UnionSet类，实现unionOp()和next()方法
就是要通过给的IntStream类中的方法来构建新的UnionStream类。要求实现UnionOp，就是把两个stream做union操作，以及next()方法，类似于iterator。主要难点在于要一边call IntStream里的next()和hasmore()一边做unionOp，不能直接生成新的unionset。
IntStream A和B本身都是set。
然后你需要实现一个新的UnionStream，这个UnionStream的next()是A和B里的数字。但是同时需要保证UnionStream自己也是具有set属性的
恩…换通俗的话说就是，A里的数字都没有重复，B里的数字也没有重复，请实现一个新的方法去输出A/B里的数，并保证输出的数也没有重复。
举例：
A = [1,2,3].
B = [1,4,5,6]
输出就是[1,2,3,4,5,6]
但是新的UnionSet实时更新的。
一问warm up：longest increasing value sequence
二问：给一堆点，判断有没有一条line使得这些点关于这条line对称。一上来简直懵逼。。。小哥看我搞不出来，出了个简化版本，给一堆点和一条line，判断这堆点是否关于这条line对称，假设判断关于这条line对称的function是存在的。
写出这个来以后小哥又让我继续写original problem，结果时间就到了。。。
应该可以先计算所有点连成的线的中点，然后依次判断计算两两中点连成的线是不是symmetry line。但是这样复杂度就太高了。
http://www.1point3acres.com/bbs/thread-147244-1-1.html
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
Follow up: How to improve?
我覺得應該是要問Mapreduce吧？這不就是Mapreduce的經典問題：word count?
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.
Follow up: kSum Smaller
https://hellosmallworld123.wordpress.com/2014/10/10/google/
http://yuanhsh.iteye.com/blog/2194143
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
LinkedList的思路是 吧每行每列的元素的cell存下来，node记的是与前面cell的差值。这样删除一行就只用改后面一个列的数据。
比如 原来有1 6 8 9 14
本来删除第6行的时候，要变成1 7 8 13 需要修改6 后面的 8 9 14 的index.
但是如果我们存的是前后index的差值，我们只需要修改删除行的后面那个index 。
比如 一样的例子： 1 5 2 1 5
我们还是删除一行，只需要改成 1 6 1 5 我们只需要修改一个就好了。
思路是这样，没写code。还要拓展成二维的
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.
http://www.1point3acres.com/bbs/thread-141774-1-1.html
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;
BFS: http://www.1point3acres.com/bbs/thread-141774-2-1.html
两道题：
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
不知道有没有更好地办法，因为当blacklist也就是选过的值增多的时候，复杂度可以到O(mn)，
搞一个 unordered_set<pair<int,int>> coordinates 来存所有false element的坐标。然后产生一个[0,coordinates.size()-1]的随机数x，coordinates[x]就是我们要翻转的element啦。 存coordinates 要O(n) time and O(n) space. 随机数和翻转都是O(1),所以总的复杂度是O(n).
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;
}
我说一个flip()是O(M+N)时间的实现，空间复杂度是O(M)。其中M，N分别是矩阵的行列数。
一开始先创建一个长为M的cum数组。cum[i]代表“到第i行（含第i行）为止，矩阵中有多少个false”。比如大矩阵是：
0 1 0 0
1 0 0 1
0 0 1 0
那么cum数组就是
[3 5 9]
我们用cum数组来决定下一个随机数出现在哪一行。比如对[3 5 9]，我们先产生一个1~9之间的随机数，比如4，然后在cum中找“第一个大于等于4”的数字，是第二个数5。那么我们就在第二行产生随机数。然后，因为5和其前面的数3的差为2，说明这一行有2个false，那么我们再产生一个[1 2]间的随机数，比如1。 然后遍历第5行，直到找到第1个0为止。这一步花费O(N)时间.
然后我们要更新cum数组，具体做法是把第二个数字和之后的数字都减1，最后cum变成[3 4 8]。这一步花费O(M)时间。
其实你生成一次随机数就可以了，比如你的例子中的4，那么4-3就是它在第二行中的位置。
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;
}
}
所以最后总时间是O(M+N)，空间是cum数组消耗的O(M)。
第二题 用 identical tree + recursive searching
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的时间复杂度，但是允许一定的setup 时间。
flip() 的时间是O(1), 总共ini时候需要的时间和空间是O(MN).
然后以上方法其实可以把空间复杂度也降到O(1), setup 时间复杂度还是 O(MN), 说白了就是用原来以为有的矩阵。。把里面的内容全给改了。。维护一个last position的指针，每次random完和last position 对调。。
补充说一下：因为这题是要返回剩下集合里随机的坐标，所以其实矩阵的I, J即使乱掉了也无所谓。。
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)
先深度优先搜索 Ta, 找到和Tb root->val 相等的Treee A 中的节点。
然后写一个判断两个数是否是identical的函数。step 是O(n)
step 2 是 O(n) 最后还是O(n*k) k是A 中和B root->val相等的节点数
一个小trick是可能有重复元素，这样的话，step1就要存多个节点，不能找到一个节点就返回，所以最后用一个容器来存。
- static bool isPartof(TreeNode* root1, TreeNode* root2) {
- if(root1 == nullptr && root2 == nullptr) return true;
- if(root1 == nullptr) return true;
- if(root2 == nullptr) return false;
- if(root1->val == root2->val) return isPartof(root1->left, root2->left) && isPartof(root1->right, root2->right);
- else return isPartof(root1, root2->left) || isPartof(root1,root2->right);
- }
第一题类似于孤岛问题，follow up是如果在来个stream，每次输入一个点是岛点，问你怎么update已经有的数组并返回新的岛的个数。
第二个处理读取文件长度的，给你个每次读4096个Byte的function, 让你implement一个可以读取任意长度N的function，要用他给的4096 function。从同一个文件中读取，由于每次读取的长度不一定是4096的倍数，所以多读的要存起来，下次再读的时候要把这存起来的先读入。就是要考虑各种情况。第三个是求曼哈顿长度的，给一个2D数组，里面有1,2,-1若干，问所有1到2的manhattan distance最短的是多少。用 DP
每个1到所有2的距离取最小的，然后再在这些值中取最小的
第四个3 sum
http://www.1point3acres.com/bbs/thread-148676-1-1.html
第一面：国人帅哥，find the longestsubstring with at most m distinct characters in a stream that cannot fit intomemory， 用moving window和LRUcache的思路解决
第二面：美国小哥， set(x, y, val)， getSum(x,y) in very large table，所以你不能把table存成array的形式，用hashtable也不行，因为求sum的时候没法保证顺序，会loop到一些不需要用的点，所以必须要red-black tree，最后就是twodimensional rb tree解决，做完后问各种怎么解决multithreading，cannot fit into memory， overflow之类的问题
第三面：美国大叔，给两个长方形形找出并求出overlapping的坐标和面积，写出各种testcases，然后各种问如何扩展到很多长方形上，怎么用我写的function来把长方形分成多个长方形之类的
第四面： 美国大叔， 就是给一个无重复的排序数组，给一个rand（），这个function返回随机数在[0, 1)之间，然后让你写一个getRandom，返回一个在数组上下界range里，但是又不在数组里的数，每个这样的数必须被返回的几率相同。
random这题就是用segment tree。
PS：大家在面试的时候一定要注意简单题，我面的时候第三面是最简单的，code也是基本很快完成了，但是最后的feedback却是最差的，面试官评论貌似是不太能跟上我的思路= =，是说我communication太差了么。。反正大家注意简单题的坑
http://www.1point3acres.com/bbs/thread-148668-1-1.html
1. 有一个tree，不是binary，define weight as 它的子数的点的个数。weight 不是treenode的field.
define weight as 它的子树的点的个数
goal是对整个树按weight排序
第一题就是要按weight排序，weight是要自己算，面试官说需要的话自己写个函数～
2. 手机app，response时间长，怎么处理。解决了怎么测试。不是写代码题。
3. 第一题的tree，会常改变，要记录什么时间tree长什么样，用什么数据结构纪录。纪录很多很多有什么问题，怎么办。
就是想要存更改历史哈，包含（timestamp，tree）信息，我觉得要考察的就是如果历史很大，entry很多，用什么数据结构合适。
1) LC原题（#286 walls and gates），只不过换成博物馆里有小偷和艺术品
2)若有一排Ｎ个位子，上面已坐了一些人，假设已坐的旁边不能再坐人，问最多还可以再坐进多少人
感觉不用吧。。。这不就扫一遍，然后如果找到中间的length，这个interval能坐的人不就是ceil((length-2)/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++;
}-google 1point3acres
}
num += Math.max(0,(end-start-2)/2);
return num;
}
3)问一些过去的工作经验以及一些Java基本问题（因为履历有写） 如List.addAll是否为deep copy, inheritance，map要怎么一边read一边加或删, 如果用for/while会有什么结果。有问如何做的distributed运算然后问了３Sum smaller
4)假设有很多台机器有一个website，要怎么样利用多台机器去crawl 这个website所有links
公司有很多office，你可以每周末飞到别的office。只有在比某个数字小的hours内能飞到才可以飞。每个office有很多假期。怎样获得一年内最多的假期。
感觉是个max flow
感觉dp就可以？OPT(i,j)表示在第i个星期呆在j办公室的情况下，从年初到现在获得的假期。然后每次计算OPT(i,j) = max(OPT(i-1, k))，k是所有能在一个周末飞到j办公室的办公室。二维数组保存dp结果，算一遍后求个最大的假期
应该是OPT(i,j) = max(OPT(i-1, k))+V(i,j)
V(i,j)表示第i个星期呆在第j个办公室当周能享受到的假期
最顺溜的follow up就是问最大假期的方案，那么更新OPT(i,j)的时候顺手记下来trace就行了
给定一个二维数组，让你找里面有多少个3*3的正方形，每行每列每个对角线的和都是一个给定的值
我这题想不到好方法，直接暴力遍历所有3*3的方格去检查了。。。
这道题完了之后，又问了下Java里面的sychonized和static关键字是什么意思，然后给了个函数让你找有什么bug（溢出和线程同步）
第一题是leetcode上面的buy and sell stock II，用贪心算法做的
第二题是如果改一下变成卖完股票之后需要等一天再买，最大收益多少。这题并没有好的思路，又是基本遍历做的。。各位大神们有什么好想法吗
http://www.1point3acres.com/bbs/thread-148553-1-1.html
第一轮，树里找lowest common ancestor，有parent，给了两种解法，一直让我跑测试，聊的挺好，然后第二轮面试官一直没来，第一轮面试官就一直陪我聊天直到吃饭。。
下午第二轮，evaluate expression,比如"(+ 7 81 2)"，返回90。格式必须严格match（数之间只能有一个空格），不match就throw exception。完了之后让evaluate复杂的表达式，比如"(* 7 (+ 1 2))"，返回21。也必须check格式，递归。
第三轮，设计一个自动售货机，没做过design，之前也就随便看了看。主要是getFood和addFood,完了最后问多线程怎么搞，我就写了个类似于生产者消费者模型的代码（加了synchronize， 开始用代码用while和wait来check，结尾加notify）。-
第四轮，最坑爹的一轮，有一辆车，载有信号接收器和照相机，有声源，信号接收器正对着声源时信号最强，相反时最弱，让你找到最好的方向（正对着），然后照相。车有rotate(double leftWheel, double rightWheel)， 前面是左轮转的角度，后者是右轮转的角度。然后讨论左右轮分别转什么角度是原地旋转。先让我做几个assumption，比如声源的信号不是时刻恒定，假设是周期的比如10s，只有一个声源，车相对声援距离比较远，可以把它看成一个点等等。主要想法是原地旋转，每次旋转一个角度，等待10s获取最大值作为这个方位的最大值，然后持续旋转足够多的次数，保证找到的全局最大值是车对着声源的最大值。然后再做旋转直到信号强度在这个最大值的阈值内，表示找到了正确的方向。还有一个问题是怎么估计车和声源的距离，没时间答了。最后走的时候随便问了他，他说可以类似于找到两个点有相同的最大值，说明在一个圆上，然后记住角度，弧长，可以估计圆的半径。。
请问左右轮分别是什么角度的时候车是原地转动啊？
http://www.1point3acres.com/bbs/thread-148564-1-1.html
先问了我 youtube 如果产生向用户推荐的视频列表。 我说了当前播放视频的{标题，内容，介绍}，该用户的观看记录，观看了该视频的其他用户的观看记录，已及该用户的 IP 地址类型（家庭用户或企业用户）。又问如果是一个新用户怎么办，我就说可以随机推荐当前最热门的视频。似乎这不是他满意的答案，他提示说如果用户是从 facebook 中点击视频连接进来的呢？我就说那就可以获得该用户的社交网络信息，根据他的爱好来推荐视频。
字符串匹配，“.” 代表一个任意字符， “*” 代表0个或者多个任意字符。
例如 youtube
y.u.u.e --> true
you*be --> true
you.. --> false.
*u*u* --> true
第三轮，
小哥自我介绍他们组是根据用户播放的 MV 推荐相关 MV 播放列表。我说我知道这个功能，我很喜欢。
然后问我如何从 Youtube 的视频列表中找到圣诞相关的歌曲。我就先说哪些信息可以提取出来做特征来训练分类器，基本上跟上一轮说的差不多。
然后问如何选择training data.
然后又问如果圣诞歌曲在所有的 MV 中所占的比例特别小怎么办，小于 1% 甚至 0.1%
实现了一下 sparse matrix
我说用 hash table 来保存非零元素，用 truple (x,y) 做 key。然后让我实现两个 matrix 相加的算法。做完以后，他提醒我如果 M1(x,y) = -M2(x,y) 怎么办。我发现如果 M[(x, y)] == 0 的话，应该将该元素从 hash table 中删除。
有一个图，图中每一个节点的label是一个整数，找到最长的连续整数序列的长度。
例如
1
\
2- 3
\ /
4
|
5-8
|/
7
最长连续数列是 2-3-4-5，就返回4(结点个数)或者3(边的个数)都行。. more info on 1point3acres.com
我就说先取出结点列表，然后对结点列表进行排序， 从最小的结点开始做 DFS 找到最长路径。他说好，开始 coding.
我就写了一个 recursive DFS。
问：如果图特别大这段代码会有什么问题么？
答：recursive 函数的调用次数有限制，如果路径的长度大于次数限制就会失败。我说也可以用 iterative DFS 来解决问题。
问：如果图特别大，超出了一台电脑的内存限制怎么办？
答：把图分成多个小图，分别计算再合并，例如上图中的 4-5 节点切断就可以将图分开。
问：如果3-8之间有 edge， 如果找到最合适的分割点？
答：先将图中无效的边都去掉，例如 1-3， 2-4， 3-8， 5-7， 5-8。将图简化后就容易找到分割点了。
问：如果这些子图在不同的服务器上分布，如果解决
答：每一台服务器分别计算自己图中所有的连续区间。另外一台电脑逐个询问这些服务器，对可以合并的区间进行合并，找到最长的区间。
问：如果有 n 台服务器，这个合并的时间复杂度是多少
答：O(n)
问：能不能优化？
答：可以每两个服务器先合并自己的区间，这样做的时间复杂度是 O(logn)
问：如何配对两台将要合并区间的服务器？
答：按每台服务器上的最大区间的起始数字对服务器进行排序，选择相邻的区间进行合并。
问：为什么这么做？
答：凭直觉，每台服务器上的最大的区间更有可能是总区间的一份子。
我说得“合并”是指将所有结果收集起来，然后将重叠的区间merge。“合并”后所以的区间都保留，直到最后一次合并完成后才能确定最大的区间。
按你的例子，第一、二台服务器合并后的结果0-2,4;这个结果再和第三台服务器(5-6)合并，得到最终结果0-2，4-6，然后确认4-6是最终结果。
或者可以先第二、三台合并得到 4-6，再跟第一台合并，得到0-2和4-6。
在这个例子里，1, (2, 3) 的执行效果是要比 (1, 2), 3 好一点。所以最后两问就是问如何找到这个最优的合并顺序。
所以最后两问面试官就问我如何找到最优的合并顺序。
2. 即使在最坏的情况下，因为是多台机器并行运算，还是要比我之前提出的用一台机器轮流查询所有服务器要快一点吧。
计算可能的 Android 解锁图案的个数。
限制条件：
i) 3x3 共九个点-google 1point3acres
ii) 最短图案包含 4 个点
iii) 最长图案包含 9 个点
iv) 路径不得跨越未访问的点，但是可以跨越访问过的点
例如， 0-2-6-8 就不合法（0-2 跨越了 1， 2-6 跨越 4， 6-8跨越了7）
0-1-2-4-6-7-8 或者 7-4-1-0-2-6-8 是合法的
0 1 2
3 4 5
6 7 8
http://www.1point3acres.com/bbs/thread-148574-1-1.html
第一道题是一个比较简单的算法题: Given string A, there is a program that could generate a word using subset of characters of string A. Write unit test and test plan to test the program. 这道题就是结合了hash table和一些test skills. 第二道题比较有意思: A binary watch, with 5 LED lights presenting Hour (0-23), and 6 LED ligths presenting Minutes (0-59). Suppose you have N LEDs are on, print all possible time. 这道题其实就是位运算的变种，结合x &= ~(x-1)， 就可以算出一个数有多少bit是1. 最后在将分钟和小时join一下就可以。大叔后来又问如果加入了秒钟，月份，年份要怎么办。那我们就不可能用简单的nested loop, 需要一个recursive function去处理最终结果。
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的问题。还是基于字符串乘法的基础上，可以做两方面的优化。
第一题给你好多array, 算出他们的intersection。第二题: Given permutation rules (a,b,c,d) to (b,d,c,a), apply the same rule to (1,5,7,2), should return (5,2,7,1)。这道题要考虑有重复字母的情况，应用Hash Table，再加上一点小技巧去处理重复数字。这道题不难，我就索性写成了class玩一玩。
第一题记不大清楚了，是一道简单的Hash Table题目。第二题: Given a tree, each node with distinct value, find the longest path with consecutive value。这道题的key insight是所有数字都是不重复的，所以连续数字只能往一个方向发展。三姐说起点在root，这样更是简化了题目。简单想了一个DFS的算法，写了写。三姐又问如果不从root开始，或者是一个graph呢，那就得用DP了呗！简单说了说思路，没让写代码
但是还是有几个小瑕疵，二面三面的时候没有考虑到两个special case。
1. 三种水果，价钱分别是x,y,z给你m的钱，一定要把钱花到不能买水果的情况下，最少买多少水果一开始说贪心算法，先从最贵的买起，然后他说most case work，让我想反例。哎，竟然没想出来，然后他给了2,5,6;10这个例子。然后我用dfs做了，不知道为什么他没有很看懂代码，然后讲了不少时间，然后他说差不多明白了，我们已经在这道题花了太多时间了.
印象中之前见过这道题，但是怎么都想不起来了，然后就用min heap做了。
然后follow up是优化空间复杂度，没想到，呵呵。面经写的这里的时候忽然想到了我当时是怎么做的了，不过也只是用两个array优化了插入的时间复杂度,并没有优化空间复杂度。
LeetCode 263 + 264 Ugly Number I II
public static void solve(int n) {
List<Integer> list = new ArrayList();
int i2 = 0, i5 = 0;
list.add(1);
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++;
}
list.add(t);
print(t);
}
}
空间的优化就是，remove掉list里面 2 和 5 都用过的数， 可以考虑用linkedlist
第一轮，树里找lowest common ancestor，有parent，给了两种解法，一直让我跑测试，聊的挺好，然后第二轮面试官一直没来，第一轮面试官就一直陪我聊天直到吃饭。。
下午第二轮，evaluate expression,比如"(+ 7 81 2)"，返回90。格式必须严格match（数之间只能有一个空格），不match就throw exception。完了之后让evaluate复杂的表达式，比如"(* 7 (+ 1 2))"，返回21。也必须check格式，递归。
第三轮，设计一个自动售货机，没做过design，之前也就随便看了看。主要是getFood和addFood,完了最后问多线程怎么搞，我就写了个类似于生产者消费者模型的代码（加了synchronize， 开始用代码用while和wait来check，结尾加notify）。-
第四轮，最坑爹的一轮，有一辆车，载有信号接收器和照相机，有声源，信号接收器正对着声源时信号最强，相反时最弱，让你找到最好的方向（正对着），然后照相。车有rotate(double leftWheel, double rightWheel)， 前面是左轮转的角度，后者是右轮转的角度。然后讨论左右轮分别转什么角度是原地旋转。先让我做几个assumption，比如声源的信号不是时刻恒定，假设是周期的比如10s，只有一个声源，车相对声援距离比较远，可以把它看成一个点等等。主要想法是原地旋转，每次旋转一个角度，等待10s获取最大值作为这个方位的最大值，然后持续旋转足够多的次数，保证找到的全局最大值是车对着声源的最大值。然后再做旋转直到信号强度在这个最大值的阈值内，表示找到了正确的方向。还有一个问题是怎么估计车和声源的距离，没时间答了。最后走的时候随便问了他，他说可以类似于找到两个点有相同的最大值，说明在一个圆上，然后记住角度，弧长，可以估计圆的半径。。
请问左右轮分别是什么角度的时候车是原地转动啊？
http://www.1point3acres.com/bbs/thread-148564-1-1.html
先问了我 youtube 如果产生向用户推荐的视频列表。 我说了当前播放视频的{标题，内容，介绍}，该用户的观看记录，观看了该视频的其他用户的观看记录，已及该用户的 IP 地址类型（家庭用户或企业用户）。又问如果是一个新用户怎么办，我就说可以随机推荐当前最热门的视频。似乎这不是他满意的答案，他提示说如果用户是从 facebook 中点击视频连接进来的呢？我就说那就可以获得该用户的社交网络信息，根据他的爱好来推荐视频。
字符串匹配，“.” 代表一个任意字符， “*” 代表0个或者多个任意字符。
例如 youtube
y.u.u.e --> true
you*be --> true
you.. --> false.
*u*u* --> true
第三轮，
小哥自我介绍他们组是根据用户播放的 MV 推荐相关 MV 播放列表。我说我知道这个功能，我很喜欢。
然后问我如何从 Youtube 的视频列表中找到圣诞相关的歌曲。我就先说哪些信息可以提取出来做特征来训练分类器，基本上跟上一轮说的差不多。
然后问如何选择training data.
然后又问如果圣诞歌曲在所有的 MV 中所占的比例特别小怎么办，小于 1% 甚至 0.1%
实现了一下 sparse matrix
我说用 hash table 来保存非零元素，用 truple (x,y) 做 key。然后让我实现两个 matrix 相加的算法。做完以后，他提醒我如果 M1(x,y) = -M2(x,y) 怎么办。我发现如果 M[(x, y)] == 0 的话，应该将该元素从 hash table 中删除。
有一个图，图中每一个节点的label是一个整数，找到最长的连续整数序列的长度。
例如
1
\
2- 3
\ /
4
|
5-8
|/
7
最长连续数列是 2-3-4-5，就返回4(结点个数)或者3(边的个数)都行。. more info on 1point3acres.com
我就说先取出结点列表，然后对结点列表进行排序， 从最小的结点开始做 DFS 找到最长路径。他说好，开始 coding.
我就写了一个 recursive DFS。
问：如果图特别大这段代码会有什么问题么？
答：recursive 函数的调用次数有限制，如果路径的长度大于次数限制就会失败。我说也可以用 iterative DFS 来解决问题。
问：如果图特别大，超出了一台电脑的内存限制怎么办？
答：把图分成多个小图，分别计算再合并，例如上图中的 4-5 节点切断就可以将图分开。
问：如果3-8之间有 edge， 如果找到最合适的分割点？
答：先将图中无效的边都去掉，例如 1-3， 2-4， 3-8， 5-7， 5-8。将图简化后就容易找到分割点了。
问：如果这些子图在不同的服务器上分布，如果解决
答：每一台服务器分别计算自己图中所有的连续区间。另外一台电脑逐个询问这些服务器，对可以合并的区间进行合并，找到最长的区间。
问：如果有 n 台服务器，这个合并的时间复杂度是多少
答：O(n)
问：能不能优化？
答：可以每两个服务器先合并自己的区间，这样做的时间复杂度是 O(logn)
问：如何配对两台将要合并区间的服务器？
答：按每台服务器上的最大区间的起始数字对服务器进行排序，选择相邻的区间进行合并。
问：为什么这么做？
答：凭直觉，每台服务器上的最大的区间更有可能是总区间的一份子。
我说得“合并”是指将所有结果收集起来，然后将重叠的区间merge。“合并”后所以的区间都保留，直到最后一次合并完成后才能确定最大的区间。
按你的例子，第一、二台服务器合并后的结果0-2,4;这个结果再和第三台服务器(5-6)合并，得到最终结果0-2，4-6，然后确认4-6是最终结果。
或者可以先第二、三台合并得到 4-6，再跟第一台合并，得到0-2和4-6。
在这个例子里，1, (2, 3) 的执行效果是要比 (1, 2), 3 好一点。所以最后两问就是问如何找到这个最优的合并顺序。
所以最后两问面试官就问我如何找到最优的合并顺序。
2. 即使在最坏的情况下，因为是多台机器并行运算，还是要比我之前提出的用一台机器轮流查询所有服务器要快一点吧。
计算可能的 Android 解锁图案的个数。
限制条件：
i) 3x3 共九个点-google 1point3acres
ii) 最短图案包含 4 个点
iii) 最长图案包含 9 个点
iv) 路径不得跨越未访问的点，但是可以跨越访问过的点
例如， 0-2-6-8 就不合法（0-2 跨越了 1， 2-6 跨越 4， 6-8跨越了7）
0-1-2-4-6-7-8 或者 7-4-1-0-2-6-8 是合法的
0 1 2
3 4 5
6 7 8
http://www.1point3acres.com/bbs/thread-148574-1-1.html
第一道题是一个比较简单的算法题: Given string A, there is a program that could generate a word using subset of characters of string A. Write unit test and test plan to test the program. 这道题就是结合了hash table和一些test skills. 第二道题比较有意思: A binary watch, with 5 LED lights presenting Hour (0-23), and 6 LED ligths presenting Minutes (0-59). Suppose you have N LEDs are on, print all possible time. 这道题其实就是位运算的变种，结合x &= ~(x-1)， 就可以算出一个数有多少bit是1. 最后在将分钟和小时join一下就可以。大叔后来又问如果加入了秒钟，月份，年份要怎么办。那我们就不可能用简单的nested loop, 需要一个recursive function去处理最终结果。
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的问题。还是基于字符串乘法的基础上，可以做两方面的优化。
第一题给你好多array, 算出他们的intersection。第二题: Given permutation rules (a,b,c,d) to (b,d,c,a), apply the same rule to (1,5,7,2), should return (5,2,7,1)。这道题要考虑有重复字母的情况，应用Hash Table，再加上一点小技巧去处理重复数字。这道题不难，我就索性写成了class玩一玩。
第一题记不大清楚了，是一道简单的Hash Table题目。第二题: Given a tree, each node with distinct value, find the longest path with consecutive value。这道题的key insight是所有数字都是不重复的，所以连续数字只能往一个方向发展。三姐说起点在root，这样更是简化了题目。简单想了一个DFS的算法，写了写。三姐又问如果不从root开始，或者是一个graph呢，那就得用DP了呗！简单说了说思路，没让写代码
但是还是有几个小瑕疵，二面三面的时候没有考虑到两个special case。
1. 三种水果，价钱分别是x,y,z给你m的钱，一定要把钱花到不能买水果的情况下，最少买多少水果一开始说贪心算法，先从最贵的买起，然后他说most case work，让我想反例。哎，竟然没想出来，然后他给了2,5,6;10这个例子。然后我用dfs做了，不知道为什么他没有很看懂代码，然后讲了不少时间，然后他说差不多明白了，我们已经在这道题花了太多时间了.
- dp[i] = min(dp[i], dp[i-p[j]] + 1) 0<=j<p.length, i>=p[j]
印象中之前见过这道题，但是怎么都想不起来了，然后就用min heap做了。
然后follow up是优化空间复杂度，没想到，呵呵。面经写的这里的时候忽然想到了我当时是怎么做的了，不过也只是用两个array优化了插入的时间复杂度,并没有优化空间复杂度。
LeetCode 263 + 264 Ugly Number I II
public static void solve(int n) {
List<Integer> list = new ArrayList();
int i2 = 0, i5 = 0;
list.add(1);
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++;
}
list.add(t);
print(t);
}
}
空间的优化就是，remove掉list里面 2 和 5 都用过的数， 可以考虑用linkedlist
可是这样生成的数列有重复的。不过在add时和前一个数比较一下就可以了
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();
}
http://www.1point3acres.com/bbs/thread-147609-1-1.html
设计一个news feed的排名算法
有好几个行为的话，click， share， like什么的，对不同的行为给不同的score，然后learn to rank吗？
还是可以做prediction，每个行为一个predictor，最后aggregate（按不同的权重aggregate？）
我是按照你说的第一种来说的，不过面试官说可以用data driven的办法来给不同的行为score，比如如果你用heuristic来强制clickthrough是1，like是2，share是3的话，相当于假设like和clickthrough的距离与like和share的距离是一样的。用data driven的办法可以基于data给不同行为赋予不同的分数，比如可能更好的权重设置是clickthrough=1, like=2,share=5。
可以用binary search或用牛顿法迭代解方程 x^3 - b = 0
learn to rank的算法 面试的时候都要记得吗？
构造比较的pair，然后变成binary classification的问题，这样的解法可以接受吗
还有直接optimize ndcg 和map 的解法，怎么解得，objective function是啥。。都要会写不。。。
不用记得所有细节的，给个high level的算法就可以。我是完全没搞过rank的，所以我就当成个回归问题来做了。
据说只要system design和machine learning有一轮过了就可以，看看你更适合搞工程还是理论 ...
http://www.1point3acres.com/bbs/thread-147786-1-1.html
Define tree class。 Binary tree 都有哪些operation，一一实现这些operation（delete没有写完
第二轮：1. Design Garbarge collector in C++ ——被狂虐，完完全全不会！我就知道garbage collection的概念，new， delete，smart pointer，that's all...
2. Binary tree 两个node之间的距离。我就是用common ancestor的方法做的。问了复杂度。如果不用递归该怎么做？
第二轮还问了如何设计test，半天没整明白，最后问我知不知道什么是black box testing/white box testing
第三轮：leetcode flip game I, II 原题。问了复杂度。中间还问到了hash原理，举例一个string hash function。这个我自己完全没有用到hash，是面试官说可以把结果存起来，问能不能提高效率，然后就问了一些hash的问题。
第四轮：设计一个CPU和内存占用是Deterministic Behavior的Event Class，支持:IncrementCount(), GetEventCountLastMin(), GetEventCountLastHour(), GetEventCountLastDay(), 每秒可以有多达million个call，也可能什么都没有。这一轮最差了，最终也没有找到合适的data structure。后来还问了很多multi-thread的问题：如果多个线程同时cal怎么办。说用mutex， lock， notify等。让在函数中实现这些。
第四轮还问了如何设计test cases，才能准确的监测正确性，并且在最少的时间内？比如虽然需要test GetLastDay，但是肯定不希望跑好几天。我说distributed让多个server去test，但似乎方向没对。。。
第五轮：Design a data structure for sparse matrix, 支持：Set(row, col), Get(row, col), vector<int> Get(row), vector<int> Get(col)。先说用linkedlist，描述了怎么实现。问时间复杂度，问能不能优化。转而用Hash - Hash of hash，面试官说可以。然后让完整的写了实现前三个函数的code。写完后继续问：现在要支持insert(row/col), delete(row/col)，hash的办法会有什么问题？如何改进，又用回了linkedlist。。。 然后如何优化等等
最后一题应该用c++ map. 嵌套map。
面试官最后提示说支持insert delete的时候，用relative indexing
Related: Design a data structure for sparse matrix
第一轮，国人大哥，先让定义一个数据结构描述家族关系，比如父母，孩子，兄弟，姐妹，问用什么样的数据结构可以。其实就是写一个类。有点像图，但比图存的东西多一些。Extended -> how about multiple step-mother/father?
然后问给输入两个点，问他们的公共祖先，有点像LCA问题的变种。
有父指针直接tree就可以了吧。
其实就是维护一个父亲，一个母亲就行了。另外，一个取巧的办法是维护是第几层，这样子做LCA的时候可以先把低的那一个往上移几步，然后开始一次移一层。有点像链表里的双指针。
第二轮，还是国人大哥。one edit distance。。直接秒过。然后follow-up 问如果输入不是两个string, 而是char stream怎么办? 这样子就不能用length 来比较了。有点tricky。。好在国人大哥放水，引导着过了。。。。
直接拿着一张纸来了打印好的题来了，题目整整一张。。。汗。。。基本大意就是给一个 m * n 的 matrix 和 一个starting point，求能得到的最长周长。。不知道以前地理面有这个题没有。最后坑吃坑吃dfs 做出来了。。
就是从这个点开始的所有相同颜色所能围成的图形的周长。
第五轮。第一题，longest consecutive subsequence 变种，输入存的不是array of integer, 而是array of double linked list node. 其实思路是一样的。
第二题，palindrome permutation..问能组成的最长的palindromic substring是什么？
http://www.1point3acres.com/bbs/thread-147935-1-1.html
说先来个warmup question，不用写code。如果给你所有google search history，和一个新的input string，需要判断有没有被search过，你要用什么数据结构？如果有多个machine，怎么利用？如果有一个query总被search，怎么加速？楼主从hashmap开始，到prefix tree，再到先pre compute每个节点下面top 10，反正也不知道他到底想问什么，可能最后也没给出他最想要的结果。。。
开始coding question。给一个数组是从1到N，就是sort好的1到N个整数，其中随机擦掉了k个数，如何uniformly sample剩下N-k个整数。不能无限次sample，空间复杂度O(k)
每次从n-k里uniformly sample一个元素就行
我当时先给了naive的算法是把n-k个数copy出来再uniform sample，他说空间复杂度要o(k)，我就说那就只存每个区间的端点，比如存[(1,a1-1), (a1+1,a2-1), ..., (ak+1,N)]，然后再sample
这个方法好！这样的话等于就是weighted sampling?因为每个区间的长度不一样，所以时间复杂度应该是O(logK)吧
第一轮uniformly sample那个，请问那K个数字是已知的嘛？如果是这样那我们是不是可以用hashset记下这k个数字，然后就在1到N先sample一下， 如果sample的值在set里，往左或者往右找最近的一个不在set里的数？
这不uniform啊，这样离set越近被sample概率越大
我就想的到把K个elements和array尾部的k elements互换，然后在array前N-K elements随机抽取一个
这样可能也行吧，但是要修改原来的array
问我知不知道multithread如何work，我说基本不知道。。。然后他说没关系，假如现在有一个闹钟系统，你可以任意时间添加reminder，包括提醒时间和提醒内容需要调用的函数，你怎么设计这个操作？
楼主没有systemdesign基础，问了半天似懂非懂的就开始写addReminder，用一个hashmap存时间为key，value为list of events。然后main函数让时间无限循环，遇到time in events就调用所有的提醒内容函数。需要注意的是，1.及时删除已经提醒过的events，2. 调用提醒内容是时间在继续，调用完要回头补上调用期间可能会添加的event。最后一点是小哥提醒的，要check是否有多人同时在sync reminder，这我哪懂，就说加个函数不让多人同时sync，他说ok.
题目也设计的很专业，从最简单开始一点点加要求，一小题一小题的最后完成了一道大题。开始，给一段document，怎么word count？怎么按照词频sample单词？现在，要做一个random writer，如何process已有的document来随机生成一句话？反正就是一步一步的递进，每小问都以前面为基础，一点都不难。最后，就是类似存个bigram的count，sample 出一句话。
给你一个长为n的string，如何找出最长的substring with k unique characters。
http://www.1point3acres.com/bbs/thread-131911-1-1.html
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;
}
我当时就是最直白的用了四个变量存了白白，白黑，黑白，黑黑这四种连续两块栅栏的上色可能。然后找当前栅栏上色的方法和前两块栅栏上色方法之间的联系
白白=黑白
白黑=白白+黑白
黑白=黑黑+白黑
黑黑=白黑
最后把四种加起来就好了
这个题做成这样，就可以用矩阵乘法来做到logN了。
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分钟，面试官说我们还能做点什么呢。我心想，不应该就是我的提问时间了嘛。。。
结果又出了一道题。给你一个字典，里面全是由0和1组成的字符串，比如{1，1110，10001，01，001，1001，101，10，00}。然后给你M个0和N个1，问你最多可以找出几个字典里面的字符串，使得这些字符串里面一共有M个0和N个1。比如给你2个0，3个1，就返回{1，01，10}。给你5个0，5个1，就返回{1，01，101，10，00}。
理解这道题就花了5分钟，我一开始以为是问你可以用给你的0和1组成哪些字典里的字符，也就是每个字符串都可以用给你的这么多。正确理解后我说第一个想到的是贪心，但估计贪心不对，所以用DFS做，就从最短的开始往下搜。这个时候时间也超了，最后小哥走的时候说应该DP做，我说恩我知道了，但DFS肯定也行吧，小哥也没说什么。
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;
三维dp O(num0 * num1 * sizeof(array))
dfs我感觉是exponential
dp 的复杂度还有再乘以最长字符串长度~
先预处理下字符串数组就行了 每个字符串数下有几个０和１除非有很长很长的字符串 否则不影响时间复杂度
问了什么是deadlock，怎么解决deadlock。
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多。
我就用TRIE的方法做了，每个节点除了存接下去的节点的MAP外，还要存到当前路径为止的每个用户的文件数。查询的时候就是把给你的路径走完，在最后的节点过一遍所有的用户看哪个人的文件最多。
写完有一点小BUG，指出了就改掉了，然后讨论时间复杂度。说如果有F个文档，每个文档平均有E个条目，然后假设最后树的高度是H，一共有P个用户，那建树的时间复杂度是多少，查询的复杂度多少。我说建树的复杂度就是F*E*H吧，小哥说并不是每次都要访问到整棵树的高度，我说给的不都是worst case下的复杂度的嘛，小哥说哦这样啊。然后查询的复杂度我说就是H，小哥说再想想，我说哦应该是H+P，因为到了最后一个点要把这个点所有用户都遍历一遍。这轮就结束了。
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就行了，大叔说行了。
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();
}
http://www.1point3acres.com/bbs/thread-147609-1-1.html
1. Leetcode: FindFirst Bad Version.
2. Leetcode: GreyCode
1. Coding:
(1) 设计一个SparseVector （就是一个超长的vector，大部分elements都是0）的class，实现dot product的操作。follow-up1:如果一个vector很长（millionsof non-zeros）， 另一个vector很短（hundredsof non-zeros），如何优化。follow-up2:如何利用index之间的关系（比如设计class的时候规定按照递增的原则存non-zeroelements的index）进一步优化。
(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.
Linkedin
Leetcode: Find minimum in arotated array.
只有一轮是coding。其他都是data mining 相关面试。两个题：
1. 实现replaceStr(strings, string foo, string bar)。即在文档s中把所有foo的occurrences都替换成bar。算复杂度。
2. 实现 doublecubeRoot(double x)。可以用二分搜索或牛顿迭代法求解。
Google
店面：
第一轮：
有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.
一个sidewalk可以用[0, 1]的闭区间表示，一个raindrop可以用[a, a+0.01]的闭区间表示，其中a是随机在[0,1]中产生的数。写一段程序simulate雨点打湿sidewalk的过程，并返回整个sidewalk被打湿所需要的时间。自己设计sidewalk的class和raindrop的class并实现两个函数:(a) 随机产生新的雨点并根据雨点的位置更新sidewalk的状态.(2) 判断sidewalk是否被全部cover。两个函数都要求是O(1)
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;
};
如何高效地swap。
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.
设计一个news feed的排名算法
有好几个行为的话，click， share， like什么的，对不同的行为给不同的score，然后learn to rank吗？
还是可以做prediction，每个行为一个predictor，最后aggregate（按不同的权重aggregate？）
我是按照你说的第一种来说的，不过面试官说可以用data driven的办法来给不同的行为score，比如如果你用heuristic来强制clickthrough是1，like是2，share是3的话，相当于假设like和clickthrough的距离与like和share的距离是一样的。用data driven的办法可以基于data给不同行为赋予不同的分数，比如可能更好的权重设置是clickthrough=1, like=2,share=5。
可以用binary search或用牛顿法迭代解方程 x^3 - b = 0
learn to rank的算法 面试的时候都要记得吗？
构造比较的pair，然后变成binary classification的问题，这样的解法可以接受吗
还有直接optimize ndcg 和map 的解法，怎么解得，objective function是啥。。都要会写不。。。
不用记得所有细节的，给个high level的算法就可以。我是完全没搞过rank的，所以我就当成个回归问题来做了。
据说只要system design和machine learning有一轮过了就可以，看看你更适合搞工程还是理论 ...
http://www.1point3acres.com/bbs/thread-147786-1-1.html
Define tree class。 Binary tree 都有哪些operation，一一实现这些operation（delete没有写完
第二轮：1. Design Garbarge collector in C++ ——被狂虐，完完全全不会！我就知道garbage collection的概念，new， delete，smart pointer，that's all...
2. Binary tree 两个node之间的距离。我就是用common ancestor的方法做的。问了复杂度。如果不用递归该怎么做？
第二轮还问了如何设计test，半天没整明白，最后问我知不知道什么是black box testing/white box testing
第三轮：leetcode flip game I, II 原题。问了复杂度。中间还问到了hash原理，举例一个string hash function。这个我自己完全没有用到hash，是面试官说可以把结果存起来，问能不能提高效率，然后就问了一些hash的问题。
第四轮：设计一个CPU和内存占用是Deterministic Behavior的Event Class，支持:IncrementCount(), GetEventCountLastMin(), GetEventCountLastHour(), GetEventCountLastDay(), 每秒可以有多达million个call，也可能什么都没有。这一轮最差了，最终也没有找到合适的data structure。后来还问了很多multi-thread的问题：如果多个线程同时cal怎么办。说用mutex， lock， notify等。让在函数中实现这些。
第四轮还问了如何设计test cases，才能准确的监测正确性，并且在最少的时间内？比如虽然需要test GetLastDay，但是肯定不希望跑好几天。我说distributed让多个server去test，但似乎方向没对。。。
第五轮：Design a data structure for sparse matrix, 支持：Set(row, col), Get(row, col), vector<int> Get(row), vector<int> Get(col)。先说用linkedlist，描述了怎么实现。问时间复杂度，问能不能优化。转而用Hash - Hash of hash，面试官说可以。然后让完整的写了实现前三个函数的code。写完后继续问：现在要支持insert(row/col), delete(row/col)，hash的办法会有什么问题？如何改进，又用回了linkedlist。。。 然后如何优化等等
最后一题应该用c++ map. 嵌套map。
面试官最后提示说支持insert delete的时候，用relative indexing
Related: Design a data structure for sparse matrix
第一轮，国人大哥，先让定义一个数据结构描述家族关系，比如父母，孩子，兄弟，姐妹，问用什么样的数据结构可以。其实就是写一个类。有点像图，但比图存的东西多一些。Extended -> how about multiple step-mother/father?
然后问给输入两个点，问他们的公共祖先，有点像LCA问题的变种。
有父指针直接tree就可以了吧。
其实就是维护一个父亲，一个母亲就行了。另外，一个取巧的办法是维护是第几层，这样子做LCA的时候可以先把低的那一个往上移几步，然后开始一次移一层。有点像链表里的双指针。
第二轮，还是国人大哥。one edit distance。。直接秒过。然后follow-up 问如果输入不是两个string, 而是char stream怎么办? 这样子就不能用length 来比较了。有点tricky。。好在国人大哥放水，引导着过了。。。。
直接拿着一张纸来了打印好的题来了，题目整整一张。。。汗。。。基本大意就是给一个 m * n 的 matrix 和 一个starting point，求能得到的最长周长。。不知道以前地理面有这个题没有。最后坑吃坑吃dfs 做出来了。。
就是从这个点开始的所有相同颜色所能围成的图形的周长。
第五轮。第一题，longest consecutive subsequence 变种，输入存的不是array of integer, 而是array of double linked list node. 其实思路是一样的。
第二题，palindrome permutation..问能组成的最长的palindromic substring是什么？
http://www.1point3acres.com/bbs/thread-147935-1-1.html
说先来个warmup question，不用写code。如果给你所有google search history，和一个新的input string，需要判断有没有被search过，你要用什么数据结构？如果有多个machine，怎么利用？如果有一个query总被search，怎么加速？楼主从hashmap开始，到prefix tree，再到先pre compute每个节点下面top 10，反正也不知道他到底想问什么，可能最后也没给出他最想要的结果。。。
开始coding question。给一个数组是从1到N，就是sort好的1到N个整数，其中随机擦掉了k个数，如何uniformly sample剩下N-k个整数。不能无限次sample，空间复杂度O(k)
每次从n-k里uniformly sample一个元素就行
我当时先给了naive的算法是把n-k个数copy出来再uniform sample，他说空间复杂度要o(k)，我就说那就只存每个区间的端点，比如存[(1,a1-1), (a1+1,a2-1), ..., (ak+1,N)]，然后再sample
这个方法好！这样的话等于就是weighted sampling?因为每个区间的长度不一样，所以时间复杂度应该是O(logK)吧
第一轮uniformly sample那个，请问那K个数字是已知的嘛？如果是这样那我们是不是可以用hashset记下这k个数字，然后就在1到N先sample一下， 如果sample的值在set里，往左或者往右找最近的一个不在set里的数？
这不uniform啊，这样离set越近被sample概率越大
我就想的到把K个elements和array尾部的k elements互换，然后在array前N-K elements随机抽取一个
这样可能也行吧，但是要修改原来的array
问我知不知道multithread如何work，我说基本不知道。。。然后他说没关系，假如现在有一个闹钟系统，你可以任意时间添加reminder，包括提醒时间和提醒内容需要调用的函数，你怎么设计这个操作？
楼主没有systemdesign基础，问了半天似懂非懂的就开始写addReminder，用一个hashmap存时间为key，value为list of events。然后main函数让时间无限循环，遇到time in events就调用所有的提醒内容函数。需要注意的是，1.及时删除已经提醒过的events，2. 调用提醒内容是时间在继续，调用完要回头补上调用期间可能会添加的event。最后一点是小哥提醒的，要check是否有多人同时在sync reminder，这我哪懂，就说加个函数不让多人同时sync，他说ok.
题目也设计的很专业，从最简单开始一点点加要求，一小题一小题的最后完成了一道大题。开始，给一段document，怎么word count？怎么按照词频sample单词？现在，要做一个random writer，如何process已有的document来随机生成一句话？反正就是一步一步的递进，每小问都以前面为基础，一点都不难。最后，就是类似存个bigram的count，sample 出一句话。
给你一个长为n的string，如何找出最长的substring with k unique characters。
http://www.1point3acres.com/bbs/thread-131911-1-1.html
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;
}
我当时就是最直白的用了四个变量存了白白，白黑，黑白，黑黑这四种连续两块栅栏的上色可能。然后找当前栅栏上色的方法和前两块栅栏上色方法之间的联系
白白=黑白
白黑=白白+黑白
黑白=黑黑+白黑
黑黑=白黑
最后把四种加起来就好了
这个题做成这样，就可以用矩阵乘法来做到logN了。
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分钟，面试官说我们还能做点什么呢。我心想，不应该就是我的提问时间了嘛。。。
结果又出了一道题。给你一个字典，里面全是由0和1组成的字符串，比如{1，1110，10001，01，001，1001，101，10，00}。然后给你M个0和N个1，问你最多可以找出几个字典里面的字符串，使得这些字符串里面一共有M个0和N个1。比如给你2个0，3个1，就返回{1，01，10}。给你5个0，5个1，就返回{1，01，101，10，00}。
理解这道题就花了5分钟，我一开始以为是问你可以用给你的0和1组成哪些字典里的字符，也就是每个字符串都可以用给你的这么多。正确理解后我说第一个想到的是贪心，但估计贪心不对，所以用DFS做，就从最短的开始往下搜。这个时候时间也超了，最后小哥走的时候说应该DP做，我说恩我知道了，但DFS肯定也行吧，小哥也没说什么。
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;
三维dp O(num0 * num1 * sizeof(array))
dfs我感觉是exponential
dp 的复杂度还有再乘以最长字符串长度~
先预处理下字符串数组就行了 每个字符串数下有几个０和１除非有很长很长的字符串 否则不影响时间复杂度
问了什么是deadlock，怎么解决deadlock。
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多。
我就用TRIE的方法做了，每个节点除了存接下去的节点的MAP外，还要存到当前路径为止的每个用户的文件数。查询的时候就是把给你的路径走完，在最后的节点过一遍所有的用户看哪个人的文件最多。
写完有一点小BUG，指出了就改掉了，然后讨论时间复杂度。说如果有F个文档，每个文档平均有E个条目，然后假设最后树的高度是H，一共有P个用户，那建树的时间复杂度是多少，查询的复杂度多少。我说建树的复杂度就是F*E*H吧，小哥说并不是每次都要访问到整棵树的高度，我说给的不都是worst case下的复杂度的嘛，小哥说哦这样啊。然后查询的复杂度我说就是H，小哥说再想想，我说哦应该是H+P，因为到了最后一个点要把这个点所有用户都遍历一遍。这轮就结束了。
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就行了，大叔说行了。
自定义一个无向的图,然后，求这个图里有多少个三角形。三角形的定义是，三角形abc中,(a,b), (b,c),(c,a)都相连。 半小时后拿到onsite...
对每个点a，找它的neighbor b，看a和b有没有共同的neighbor c，如果有，为了去重，我直接把a从b和c的neighbor里删掉了。
用邻接矩阵存，比如A，然后A^3得到新的矩阵B，它的迹除以6就是三角形个数
给一堆长方形，求它们的面积和。长方形自定义。
长方形那题，就是让处理overlap的。两两处理，如果有重叠，那么，保持其中一个长方形不变，然后把另一个拆开，使原本重叠的两个长方形变成不重叠的多个长方形。
做法为：把所有长方形上下边（共2N条）按照纵坐标排序，并且每条边标记是长方形的下边还是上边。然后从前往后扫描，用一个数组来记录边的横坐标，对于每条扫描的边横坐标（l, r), 就把数组l，r 所有index的所有数值＋1, 这一步cost O(N) 时间，所以可以用segment tree优化，这样只需要O(logN). 没碰到一条边就加上当前那一条边和下一条边所夹的面积。
所以，最后总时间可以是O(N^2) 或是O(NlogN) 如果你用segment tree来维护数组的话。
拆分长方形是很complicated的，因为长方形可以两两重叠，三三重叠等等，面积很容易算重了，这题其实可以按边的纵坐标排序，然后从小到大扫描，用segment tree维护, O(NlogN)。
因为长方形重叠的可能性千变万化，所以计算面积时为了避免重复，每次只累加相邻两条边所夹的面积，相邻两条边所夹的面积等于(边i纵坐标所对应的水平线上所有被边横坐标所覆盖的长度总和) * (边i + 1的纵坐标－边i的纵坐标). 第二个括号不用计算，关键在于计算第一个括号，第一个括号naive计算方法自然是对每一组(l, r)，都把l，r之间的index元素一个一个加1，然后便利一遍横坐标数组，用时O(N). 但是注意，l，r是连续的，并且长方型每一个下边，必定对应一个上边，利用这个对称性，可以用segment tree维护，segment tree每一个节点存贮这个节点所对应的区间里被覆盖的总长度，所以每一次操作可在O(logN)完成。
http://www.1point3acres.com/bbs/thread-147304-1-1.html
第一题，一堆数，找出和最接近0的两个数；
第二题， 1
/ \
2 3
/ \ / \
4 5 6
如上图，有好多节点，给一个目标节点，求出从root到目标节点有多少条最短path。 比如，目标节点为2，就有1条path, 目标节点5，有2条path.
这题是个坑，我跳进去了。写完之后，三叔说，我不喜欢你的code,但你写的也是对的
其实三叔应该是不喜欢我的算法，我用bfs做的，他的意思是，应该巧妙使用pascal triangle
input就是treenode，只不过和BST不同之处在于两个相邻的node会有同样的subtree。
implement 一个叫logger的interface，
题目是酱的，logger里有俩个method,分别叫做startRequest和endRequest,input都是request id,和时间，return是void.
每一个request都有 独一无二的id,并且开始和结束都需要分别调用那两个method。当一个request结束之后，需要打印出来它的id,开始时间以及结束时间，但是，要按开始时间先后打印。
不是全部结束后一次性打印呢。你可能想的复杂了。
假如是这样的：
request A |-------------------|
request B |--------|
B 结束之后并不能打印，要A结束之后才能打印，但是A结束之后就会立马打印出A和B。所以需要一个合适的data structure储存已经结束的B。
首先需要一个HashMap,存(id,request).
接着，需要一个queue存所以request的id或者request本身. 我选择了PriorityQueue并以开始时间排序,因为多线程的时候，单纯的Queue不能确保request是按照开始时间排序的。
每次endRequest的时候，赋给这个request end time, 同时
while (!heap.isEmpty() && heap.peek().endTime != null ) {
request a= heap.poll();
map.remove(a.id);
print(a);
}
哦对了，面试官说，多线程的时候应该用PriorityBlockingQueue. 所以用BlockingQueue应该也是可以的吧。
最后一题，followup 是 multithread来着，我这题用heap写的
multithread的话就用synchronize和concurrent的data structure，像priorityblockingqueue，concurrent hashmap
题目很简单，但是感觉自己没有好好把握这次机会，主要是第二面，基于我的code的一些改进，答得不好，整个人反应及其迟钝。
http://www.1point3acres.com/bbs/thread-147302-1-1.html
第一轮： 给一个 M * N的screen，和一个String,比如“Hello World", 请问整个screen能放下多少个string。
note: 如果有一个词在一行放不下，放到下一行。
这一轮感觉就是纯的字符串处理。
第二轮：给一个sorted array， 求出是否含有popular item。 popular item定义就是大于size的1/4。我给出了O（n)解法和代码。面试官follow up O(logn)。
找n/4 n/2 3n/4 n这几个candidate，然后分别用二分搜索看长度满不满足
第二题只需要检查0, 1/4, 2/4, 3/4 4/4位置的元素看它们是不是就可以了，检查每一个数用二分搜索找左右boundary算个数，所以是(10 logn) = logn
检查0是多余的，因为如果0的数字是popular的，那在1/4处还是它。
4也是多余的吧？最多只可能有3个数字，所以需要检查1, 2, 3
最后一个位置不多余啊，最后1/4段包括4/4那个点不包括3/4那个点。
第三轮：flow water
~ ~ ~ ~ ~ ~ ~
~ 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 *
* * * * * * *
给定一个grid，判断是否有点技能到达~,也能到达*。就用图的DFS,BFS做。
第四轮：给一个没排序的array，删除里面的duplicate，保留原来里面item的顺序。可能有多个重复的items。要O(n)解法
因为要o(n)，是map+double linkedlist的解法么？
第五轮：给一个String[] array, 和任意一个移动的window size k， 对array里的元素位置进行改变，使得window里的元素不重复. 要efficient的解法
考虑的情况很多，window就是在输入的string[] array里移动，windows里的元素可以是任何string。
是不是重新排列array使得相同string的distance至少为k？
这可以是一种解法，有很多种可能性，输出其中一种就行了。
我能想到的办法就是建一个map看每个词的出现次数， 然后根据map重新建一个array，做到相同的elements之间的距离大于k.不过这样应该是O(n) time O(n) space.
噢time应该是O(NlogN)因为需要按照出现次数排序
第五题应该是字符串重排， 要求相同字符的间距>k的变种题. 使用Heap可以快速解决。 大概是HashMap统计词频， Entry<Character, Integer> 作为item 放进Max Heap, 以Integer重复数量作为排序因子。 然后每次从Heap取出k个元素append到StringBuffer, Integer分别-1之后再放回Heap. 再取出K个entry重复就好了
http://www.1point3acres.com/bbs/thread-147293-2-1.html
一问warm up：sort color
二问：给一个stream类，里面有next()方法和hasmore()方法，要求写一个UnionSet类，实现unionOp()和next()方法
就是要通过给的IntStream类中的方法来构建新的UnionStream类。要求实现UnionOp，就是把两个stream做union操作，以及next()方法，类似于iterator。主要难点在于要一边call IntStream里的next()和hasmore()一边做unionOp，不能直接生成新的unionset。
IntStream A和B本身都是set。
然后你需要实现一个新的UnionStream，这个UnionStream的next()是A和B里的数字。但是同时需要保证UnionStream自己也是具有set属性的
恩…换通俗的话说就是，A里的数字都没有重复，B里的数字也没有重复，请实现一个新的方法去输出A/B里的数，并保证输出的数也没有重复。
举例：
A = [1,2,3].
B = [1,4,5,6]
输出就是[1,2,3,4,5,6]
但是新的UnionSet实时更新的。
一问warm up：longest increasing value sequence
二问：给一堆点，判断有没有一条line使得这些点关于这条line对称。一上来简直懵逼。。。小哥看我搞不出来，出了个简化版本，给一堆点和一条line，判断这堆点是否关于这条line对称，假设判断关于这条line对称的function是存在的。
写出这个来以后小哥又让我继续写original problem，结果时间就到了。。。
应该可以先计算所有点连成的线的中点，然后依次判断计算两两中点连成的线是不是symmetry line。但是这样复杂度就太高了。
因为line可以是any line也就是说可以精确到double的。。根本迭代不过来。
http://www.1point3acres.com/bbs/thread-147244-1-1.html
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
Follow up: How to improve?
我覺得應該是要問Mapreduce吧？這不就是Mapreduce的經典問題：word count?
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.
Follow up: kSum Smaller
https://hellosmallworld123.wordpress.com/2014/10/10/google/
http://yuanhsh.iteye.com/blog/2194143
1. boogle question
我能想到的就是dfs来找。一个一个搜索，如果有搜索到就是true，不然就是false， 要注意dfs的时候visited matrix来记录走过的地方。
给定一个2darray， 里面的integer是没有重复的，怎样找到最长的连续数列O(mn）复杂度。如果用dfs的方法或者BFS的方法，复杂度应该是mxnx(m+n)，如果要用O(mn)的话，应该是用dp的方法
我能想到的就是dfs来找。一个一个搜索，如果有搜索到就是true，不然就是false， 要注意dfs的时候visited matrix来记录走过的地方。
给定一个2darray， 里面的integer是没有重复的，怎样找到最长的连续数列O(mn）复杂度。如果用dfs的方法或者BFS的方法，复杂度应该是mxnx(m+n)，如果要用O(mn)的话，应该是用dp的方法
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;
}
}
}
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最少。
这道题挺难，我能像到的就是从头1扫到sqrt(target). 然后计算,这样的复杂度应该是n!.
然后可以看到其实可以用dp的方法优化：
4. 给定一个2darray，里面包含integer，水可以从integer大的地方向小的或相等的地方流。 假设上边和左边是pacific，右边和下边是atlantic， 求所有能到达两个大洋的路径。
这道题因为要记路径，所以用DFS来做， 对于matrix里的每个点都做DFS，看他能不能到达两个大洋，如果能达到的话，就把路径记下来。
后来提示也可以用BFS的方法，从每个大洋的边界上的点开始BFS，找到所有能到达atlantic的点，同理也可以找到所有能到达pacific的点，最后两个一比较就可以找到那些两个大洋都可以达到的点了。
这道题挺难，我能像到的就是从头1扫到sqrt(target). 然后计算,这样的复杂度应该是n!.
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;
}然后可以看到其实可以用dp的方法优化：
int numberOfTerm(int n) {
int[] numOfT = new int [n];
for (int i=0; i<numOfT.length; i++) {
if (i == 0)
numOfT[i] = 0;
else
numOfT[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， 求所有能到达两个大洋的路径。
这道题因为要记路径，所以用DFS来做， 对于matrix里的每个点都做DFS，看他能不能到达两个大洋，如果能达到的话，就把路径记下来。
后来提示也可以用BFS的方法，从每个大洋的边界上的点开始BFS，找到所有能到达atlantic的点，同理也可以找到所有能到达pacific的点，最后两个一比较就可以找到那些两个大洋都可以达到的点了。
5. 给定一些box的w和l，假设box1可以放在box2的条件是宽和长都小于box2，求最长的可能放进盒子的序列，实际上这道题很像Career cup上一道身高和重量叠人墙的题目。我们只需要将box按长度sort，然后如果长度相同再按宽度sort，然后扫描一遍整个数组，看看连续的宽最多有多少即可。
6. system design，设计一个键盘的输入法，不需要一个一个按，而是快速的滑动，怎样设计，怎样给suggestion给suggestion应该涉及到用trie的数据结构。此外如果用trie的话还要注意排序的问题，如果trie要排序的话还要记下每个char的频率。
6. system design，设计一个键盘的输入法，不需要一个一个按，而是快速的滑动，怎样设计，怎样给suggestion给suggestion应该涉及到用trie的数据结构。此外如果用trie的话还要注意排序的问题，如果trie要排序的话还要记下每个char的频率。
是密码，假设有一个4位的密码，我们要试所有的可能组合，怎么样让所有的可能组合组成的序列尽可能的短？
第二题很难描述，是一个关于decision tree的问题。
第五题是给一个string，一个valid function，然后找出这个string可能的所有可能的subset组成的string里找到最长的valid的String
