Google电面面经总结

2019-04-14 22:04发布

1. 上来问了tree里node求和的问题  很简单  然后follow up 给一个range 求range里的node值的和,不是path sum  是所有节点的求和   然后给个range 值在range之内就加进去    然后分析不同的树怎么优化
2. encoding,把 abcccdaa 这种字符串变为 ab3xcd2xa 这种

3. 给一个String的array,问如何移除重复的string。(hashmap, sort, binary tree)

4. 给一个integer的array,按照n1<=n2>=n3<=n4>=n5 的order排序(sort, 每3个把最大的放中间,然后跳两个继续扫描) public static void sort(int[] num){ if(num==null || num.length<2) return; for(int i=1; i5. class Foo() {
        int a;
        String b;
}
实现这个类的equals方法,cornor case比较多
后续问了很多基础知识,private, protected, public default的区别,final是干什么的,==和equals的区别,然后要求精简代码,最后缩短到四行,然后问了实现了equals还要干嘛,还要实现hashcode,然后楼主就a + b.hashCode给实现了一下,注意b=null的情况。基本就这么多了
(1) private, protected, public default的区别


Modifier    | Class | Package | Subclass | World
————————————+———————+—————————+——————————+———————
public      |  y    |    y    |    y     |   y
————————————+———————+—————————+——————————+———————
protected   |  y    |    y    |    y     |   n
————————————+———————+—————————+——————————+———————
no modifier |  y    |    y    |    n     |   n    **also known as package-private**
————————————+———————+—————————+——————————+———————
private     |  y    |    n    |    n     |   n


(2) == compares 2 reference for non-primitives, == compares values for primitives, equals compare state(attributes) for non-primitives, but the method may be overridden. (3) write an equals() function: the equals function of String: public boolean equals(Object anObject) { if (this == anObject) { return true; } if (anObject instanceof String) { String anotherString = (String)anObject; int n = count; if (n == anotherString.count) { char v1[] = value; char v2[] = anotherString.value; int i = offset; int j = anotherString.offset; while (n– != 0) { if (v1[i++] != v2[j++]) return false; } return true; } } return false; }

(4) compare using hashcode   1.如果两个对象相同,那么它们的hashCode值一定要相同;
  2.如果两个对象的hashCode相同,它们并不一定相同(这里说的对象相同指的是用eqauls方法比较)。  
    如不按要求去做了,会发现相同的对象可以出现在Set集合中,同时,增加新元素的效率会大大下降。
  3.equals()相等的两个对象,hashcode()一定相等;equals()不相等的两个对象,却并不能证明他们的hashcode()不相等。 6. 两个数组分别代表两个整数,相加。lc原题。回答最优情况下的复杂度。
7. 迷宫寻宝。一个grid表示的地图,上面有宝物,有障碍,要求找出图上一个点到所有宝物的总距离最短。我用了bfs.
8. 在某个游戏中设计一个排名更新算法。排名是根据各玩家的分数决定的,从高到低。设计数据结构。实现两个函数:第一个:输入是玩家名,输出是玩家排名;第二个:输入是玩家名和玩家的新分数,要求更新排名。
我的想法:用arraylist 和hashtable,arraylist里每个node有玩家key,分数,排名,排名是arraylist的index,然后用binary search更新玩家排名,use lazy approach, update rank in a node only when needed。
9. 把一个整数组里所有零移到后面。
10.problem solving:
2 player game
- there’s a set of marbles
- take turns removing 1 or 2
- winner removes the last one


- you get decide who goes first
我大概解释下,就是有俩人玩儿个游戏,现在桌上有n个弹球,你和你的对手轮流取,一次一个人只能取1个或2个,把桌面清空的那个人胜利。
你来决定谁第一个取弹球,在不同弹球数量n的情况下,请问你是否能制定出一个必胜策略?


(1)solution1: 先枚举一些case归纳(OP= opponent):
n=1,2 I first  (很显然我可以一次拿完直接胜利)
n=3 OP first   (让对手先拿,他拿一个我就拿俩,他拿俩我就拿一个,最后一定是我赢)
n=4 =1+3 I first  (我先拿一个,然后轮到对手,立马转化为n=3的情况,最后一定是我赢)
n=5 =2+3 I first  (我先拿两个,然后轮到对手,立马转化为n=3的情况,最后一定是我赢)
n=6 =3+3 Op first  (相当于两个n=3 case的重复,此时应该让对手先)
n=7 =1+3+3 I first (这个不用解释了吧)


所以最后归纳出的策略就是:
n=number of sticks
if(n%3==0){OP first}


(2)solution 2: 如果轮到我选择球的时候, 我会胜利的要求是当我选择以后,留给对手的球他输了我就能赢,只要他无论怎样都赢了, 我就输了。 比如我现在手里有 i个球, 我只能选择两个球或者一个球, 留给对手的就是i-1 或 i-2 个球。 假设D= true or false 表示我当前能否赢。 
那么DP表达式为
D = !D[i-1] || !D[i-2]; D[1] = true, D[2] = true,可以算出来D[n] = true or false 根据DP 如果是false 那当然他先选 如果是True 那我肯定可以先选。


11. 在地址栏输入url address后整个过程,我说的比较大致,连tcp都没提到,network实在是白学了。说完他问我web proxy server知道吗,我说sorry, i never heard about it,面完立马wiki,其实就是运用比较广泛的一类server。
http://stackoverflow.com/questions/2092527/what-happens-when-you-type-in-a-url-in-browser
proxy server: 代理服务器,http://en.wikipedia.org/wiki/Proxy_server
http://baike.baidu.com/view/751.htm
12. 1枚硬币,来选择出1-3的数字(比如3部电影,选出看哪一部),我想很简单啊,投两次不就有0-3四个数字么,不可以选出来了么,然后他说万一投到0咋办,我说那继续重投,毕竟1/4的概率不是总能遇到的,然后他说可以优化这样,如果投到0,那再投一次,那么就有0-7 8个数字,那么可以:
1-2 -》1
3-4 -》2
5-6 -》3
0-7 -》再投一次
真是个好办法(感觉很dynamic),下次实际可以运用了。
13. binary tree的max height,我先是写了个方法,然后他说既然你用Java,那就把他变成class的method吧,然后就做了点小改动,没什么大问题。
14. 面试官是印度人,开始给了一组map,问有没有发现什么pattern。. From 1point 3acres bbs
apple -> a3e
teacher -> t5r
Pattern就是首尾字母加中间的长度。题目要求:给一个txt文件,里面有很多word,写一个function,input是类似于“a3e”,需要输出所有满足这个pattern的word。
楼主说的是先pre-process一下文件,生成一个HashTable,”a3e"是key, value就是同一个pattern的word list。
面试官基本满意,开始我说对读文件的API不太熟悉,他建议还是要掌握一下。
java read file:
BufferedReader br = new BufferedReader(new FileReader("file.txt")); try { StringBuilder sb = new StringBuilder(); String line = br.readLine(); while (line != null) { sb.append(line); sb.append(System.lineSeparator()); line = br.readLine(); } String everything = sb.toString(); } finally { br.close(); }
java write to a file: public static void writeFile1() throws IOException { File fout = new File("out.txt"); FileOutputStream fos = new FileOutputStream(fout); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(fos)); for (int i = 0; i < 10; i++) { bw.write("something"); bw.newLine(); } bw.close(); }
15. 2.2D matrix,while or black stone. find if there are rectangels whose four corner are black stone.. From 1point 3acres bbs
wbwbw
wbwbw
wwwww
只要有一个就行,如图。。
先preprocess,用bitset存储,w变0,b变1,然后每行&,得到的结果x:
(x-1)&x >0,说明x中至少有两个0.
感觉用bitset反而更麻烦,直接用int或者long 好了


16. 
电面45分钟。一个数列,对每个数a都可以求出这样一个数f(a)=#(位置排在a后面,且比a大)。要求这些f(a)中的最大值。给充足提示引导到一个o(n^2)(其实是nloglogn)的方法。不要求写


代码,下面是大致思路:
1. 如果b>a,b在a后面,则f(b) 2. 遍历数列,更新L,最后根据L中数据求解。剩下的问题是,要考虑L中保存什么样的数,遍历时更新L中的数据仅用log(length L)时间;用什么方法可以根据这些数据最后在n时间内求f(a)最


大值。
3. 讨论复杂度,关键是L的长度。假设给出数列时以这种意义的“均匀”方式给出:数列当前长度为k,第k+1个数大小排在这k+1个数中第i位的概率是1/(k+1). 可以算出L长度的期望是logn(n是数


列长度)。所以实际复杂度是nloglogn。


17. BST的add, find和delete函数
delete函数需要复习一下,如果没有child,直接delete就可以了,如果只有一个孩子,那么用孩子节点代替,如果有两个孩子,找到右子树的最大值,交换这个最大节点和需要删除节点的值,然


后再删除交换后这个值所到达的节点。
http://www.algolist.net/Data_structures/Binary_search_tree/Removal
18. 给string, 只包含{0,1,?}, ?可以代表0或者1, 输出所有的组合. 例如"10?", 输出"100", "101"
19. java array linkedlist的区别, java sychronize关键字用法,Balanced search tree的搜索时间,java serialization
20. remove duplicate lines in a file。
21. Clone Graph ,5分钟做完,思路比较清楚
22. Palindrome Paritioning II
24. 面试官是个platform组的,上来先问了一堆C++继承的知识,然后问了一个在服务器端synchronize两个很接近的大文件,不能发送整个文件到back-up端。楼主先说了一个传log重构的方法,


然后如果没有log可以用的话就把文件分块压缩,比较压缩码确定哪一部分需要synchronize,面试官表示还OK。
然后是30分钟的coding部分:
25. 输入两个字符串s1, s2,输出s1中第一个没在s2中出现的字符。
26. Moving average, 设计题, 要求实现对于一个window_size, 不停插入值,返回当前的平均数,如果输入没有达到window_size则输出所有数的平均值,达到后踢掉最早的输入输出最新的平


均值。
27. 第一个写两个函数,分别是 public String encode(List list) 和List decode(String s)。String里可能包含任意字符,开始猜了一堆,最后encode连接String我说用"


",小哥说make sense。(string.length() + '#'分隔?)
第二题设计一个两人玩的游戏,"--"变成"++"是一个valid move,赢得条件是一方不能move, 给一个String比如“---++----++-+", 写一个函数返回所有valid move, 然后写一个函数判断当前是否


赢了,再写一个函数判断接下去是否会赢。
28. 32个bit表示RGBA颜 {MOD}值, 输入RGBA输出BGRA
     位操作 直接用一个mask提取相应RGBA的值,比如RGBA&0xFF000000提取R, shift后再组合成BGRA
     注意用unsigned int(本人用C++),否则right shift可能会在前面补1


29. 一个诡异序列
     1,  11,  21, 1211, 111221, 312211
     每一项其实是统计上一项连续相同数字个数, 比如1211表示上一项21里有一个2和一个1
     求第n项
     直接一个一个推,一位一位算,时间复杂度O(n*2^n) , 这个时间复杂度很tricky, 思路是最坏情况下第n项是第n-1项长度的二倍(比如12345下一项1112131415)
30. 一个矩阵,求最长连续的序列长度
[1 2 3
4 5 6
7 8 9]
我的解法时用dfs便利矩阵,如果便利过的元素就标记为false,不再遍历。
31. 我有一个输入字符,然后我有一个英文字典,说白了就是字符串数组,然后写一个function返回字典里拥有输入字符串里所有字母(非数字或者空格等符号,就是纯字母)的最短的那个字符串


。举个例子:
输入字符串"SR 456 T",字符串数组里有"SORT",而且是最短的,那么就返回它。
(1)就用个ArrayList对比时new一个新的instance,每对一个就remove一个,最后空了就说明符合。O(n)复杂度,感觉字母间check可以忽略不计吧。优化的话就是按长度sort dictionary
(2)我想了一个不知道对不对。
优化字典树:把每个字符串wrap成一个classs,有两个变量,一个是26长度的数组存放每个char出现的次数,另一个是该字符的长度,然后对所有的wrapped object排序,compare的方法是先比较


数组,a-z比重递减,都相同的话再比较长度,短的排前面。然后输入一个input,可以实现binary search。
(3)能不能先对词典建TreeMap(new Comparator(by word.length)), Anagram是排序后的Word。对输入filter&sort成一个新词,然后iterate treemap, 遇到第一个indexOf 不


为-1的就输出?


(4)先预处理, 给所有字符按照lexico oder 排序, 编上号, 然后分出含有A 的一个List ,含有B的List .... 共有26个List, 当然每个List 也是排序的。 然后对于这26个Merge Sorted Lists 


的方法进行遍历,如果在遍历过程中碰见某个时候26个指针碰到同一个index 就return。
(5)解法是不是: 建立一个bit串 把pattern每一位对应位置的bit置为1,然后dictionary对应的bit串每一位同样置位一次,然后两个bit串按位与一次。。。和pattern串相同的就留下,换下一个



或者解法是不是:建立一个enum 把pattern里面每个字符对应一个质数,其他的字符对应成这些质数之后最小的质数,然后对pattern做乘法,留下乘积,然后留下为原pattern乘积倍数的词?
32. 写MyString class interface。
33. 被除数是一个用string表示的数,除数是一个long,返回string类型的结果, 要考虑结果为小数和无限小数的情况


34. popular value
35. missing range
36. One question is below, what is your solution for this? I think this problem is not difficult at not, right.. 鍥磋鎴戜滑@1point 3 acres




bob, joe, bob, jane, bob, joe, jack


bob = 3
joe = 2


topN(2) = bob, joe


solution: double-linked list and hashtable.


32. 判断一个int是不是旋转180度后还是原来的数字,比如16891还是16891,返回 true。
33. 给的例子:
Graph g = new Graph();
g.addEdge(“abb”, “cde”);
g.addEdge(“abb”, “ff”);
g.addEdge(“ff”, “abb”);. From 1point 3acres bbs


implement  graph, addEdge,


之后 要求implement 一个cycle detection


三哥的没有明说的要求是这个graph里的node可以self point,也可以mult point to one node;
所以cycle detection最好是用recursive 的 DFS. (MD, 这点儿把老子整惨了)


之后follow up,给一个数n,返回所有的满足刚才条件的数,比如n=1 [0,1,8],n=2 [11,69,96,88]。
solution: 两个集合
same = {0, 1, 8}
mirror = {6, 9}


n = 3,  [101, 808, 609, 906, 111, 818, 619, 916, 181, 888, 689, 989]
可以看出是 n = 1 的数左右各加一个数,取自于 same, mirror 中。
如果取自same,则两个数必须相同,如取自mirror,则69 还有 反序。


n = k 就是 n = k - 2 左右个加一个数。
运用 Divide and Conquer 思想,一个旋转对称的数去掉头和尾还是对称。
33. 第一题: 实现搜索框的提示功能, 用户输入一个或者一部分字符后, 算法输出所有match的字符串. 
给了三种方案, 一种是简单的直接brute force; 第二种是trie; 第三种是类似正则表达式的做法; 面试官说用trie来实现吧. 先构建出trie, 然后把搜索函数写出来. 没什么好说的 从头开始写


出来. 完成后写了个简单的test case, 和他一起过了一遍;实现时代码量有些多,用了大概二十多分钟. 主要包括trie class, buildTrie, find the fist Node in Tire, print out all paths


(strings) in trie四部分。 
34. 第二题, deep copy linked list. 给了两种方案, 一是hashmap based, Time O(n) + Space O(n); 一是直接对List拆分拷贝 Time O(n) + Space O(1)。
35. Implement HashTable with get,set,delete,getRandom functions in O(1).
这题之前地里有人po过面经,楼主很幸运地当时认真实现过。。
重点在于2个hashmap+arraylist


36. Given a source word, target word and an English dictionary, transform the source word to target by changing/adding/removing 1 character at a time, while all 


intermediate words being valid English words.


37. serializable interface
38. 给定两个排序好的数组, 返回两个数组中包含的相同的元素(merge sort中的merge就行)
39. valid parenthesis
40. 通配符, 给定输入字符串 01*0*, *可代表0或1,输出所有可能的结果
41. given a BST, find a way to serilize all values in one string, then write a function to translate the string back to the original tree
   n1
   /  
ab  h
/     /  
m   g2 cb
我是按照BFS的顺序 得到val, 然后没有children的地方 用[None] 表示。因为这个tree里面的所有val 都是 numerice and 字母,所以[None]不会混淆
得到 s = s = 'n1 ab h m [None] g2 cb '     其中 为分隔符
42. Given two strings containing digits, return the one which represents the largest integer once the digits have been sorted in non-increasing order.
“245” -> 542
“178” -> 871
return 178
这题不是原题,没有见过,不过很简单。但是LZ过于紧张,写的时候有bug
做法是用两个长度10的数组来count在两个String里每位数字出现的次数,然后从9开始往后比,看看哪个不一样。input的string不是sorted的。给你了452和781一样返回781.因为按照降序排列后


452->542,781->871,是871大
43. 第一道题特别简单,给一个xValue arr, 一个b, 一个m, 求y = ax + b的所有yValue的值, follow up: 这个函数什么情况下是ascending的, 什么时候不是? 如果是decending的话, 我想正序


输出怎么做? 
44. 第二道题给一个xValue arr, 一个a, 一个b, 一个c, 求y = ax ^ 2 + bx + c, 要求yValue要递增输出。。。
开始说先得到yValue然后sort, 然后他说make sense, 但是时间复杂度太高, 要nlogn, 能不能再低。。
然后说hashmap, 然后他说hashmap是乱序的, 我说用linkedlisthashmap那个东西, 人家自动给你排序, 说不行, 因为不管怎样还是排序了。。. visit 1point3acres.com for more.


于是继续想。。。.1point3acres缃�


后来小哥提示说二元函数有个轴, x = -b/(2a)这么个东西, 然后左边是降序, 右边是升序!后来我不知道怎么又说了个merge。。。反正在他一顿指导下豁然开朗:轴右边升序存一个array, 轴


左边升序存一个array,然后merge这两个array into an extra array。。。时间复杂度是n。。小哥挺满意。。


但是后来时间不够了。。小哥就说你给我说一遍你思路吧。。google doc上也是他给我写的。。。虽然感觉他挺满意,态度特别特别好,但是毕竟最后一道题没解出来,不知道会不会给我onsite


。。。TAT
45. 就问了一道题,把一棵二叉树的路径上的节点的值的和加起来。然后把所有的和按顺序输出出来。
这道题主要靠的就是一个数的遍历
46. numebr format, 就是123456 -> 123,456 给integer返回string这样子的。这道题基本没纠结, 开始是先给他讲我的思路, 在google doc上写写画画来着, 然后实现代码
47. 返回一个bst的第二大值 (原谅我leetcode还没完整刷一遍,最近一直在看DP DFS这一类的题,树什么的还没整体理过思路TAT)。然后一路纠结,面试官也一直在给提醒啊什么的终于做出来了


。。
最右节点的父节点就是第二大的值了,或者用中序遍历的逆序来找第n大的值。
48. Coding部分问的是给一个List 要求转换成单个String并且能转回来。       做法是在String之间插入间隔字符比如`,如果List里的字符串里有`的话就再插入一个。解码的时候看


到两个`就换成一个,单个`就是字符串的间隔符了。Interface给的List,不知道是ArrayList还是LinkedList,所以最好用iterator。
49. 给两个 range A [a1, a2), B [b1, b2)
找到numbers shows up in range A  but not in range B
比如A [1, 2,3], B[3,4,5]
output [1, 2]. Waral 鍗氬鏈夋洿澶氭枃绔�,


讨论了如果 range 是连续的会怎么样, 如果不连续会怎么样


一开始我秀逗了, 非说连续的话要用(log n)
三姐也不点破, 就叫我写code, 写着写着我发现连续的话直接算边界的大小就可以了
50. We have an unordered list of Events from multiple sessions intermixed. Given this list (List), construct a new list containing only the latest Event for each 


session.直接hash table就可以了,不需要priority queue
51. Write a function to detect whether a poker hand contains a “pair” (exactly 2 cards with the same value). use hash
52. determine whether the hand contains a “straight”: values are consecutive. sort or use hashset.
53. 这样的,两个input,第一个是一个机器的total_mem,第二个是一堆job,每个job包含starting_time,duration,mem_needed,mem_needed就是说这个工作需要这么多的memeory。要求是输


出bool,表示是否在任意时间内,所有重叠工作的memory总和都不能超过total_mem。也就是测试这个机器的total_mem够不够大。
按start time 排序。
54. 面试问了一道题,首先给定一个encode method 把一个String数组整合成一个single string输出,然后让你写decode method,把这个single string再还原成原来的String数组输出。
我一开始的思路是在不同的string之间加mark,然后decode的时候遇到mark即可分割string。但是小哥好像不满意这个算法,他问我知不知道操作系统里面的文件系统怎么管理的。我说有一个


Index指示文件的位置,然后他让我按照这个思路写了decode 函数。之后又修改了代码的几个小地方。面试结束。
分隔符是 #s.length#, 如果string中有#的话,就把#变成##.
55. given two int arrays, determine whether one is permutation of the other。. From 1point 3acres bbs
做法很简单,先判断两个数组长度是否相同。之后对第一个数组建一个hashtable把所有出现的字符和出现的次数记录一下。然后扫一遍第二个数组,有相同的话就对应的出现次数减一。如果有字


符的出现次数变成负数,就是false。
56. construct a binary search tree from a sorted int array
这题对建立的树完全没要求,我还特意问了建的tree要不要balanced,面试官说无所谓。我还是取中间的数作为root,然后recrusively的处理左右子树。因为我建立node的时候用的都是root=new 


node(val)操作,所以在最后都要用delete操作把开的内存收回来。平时刷题的时候从来不会在意这些,面试的时候写完了面试官说有一个问题,我看了半天说能不能给点hint,他说了memory 


leak我就懂了
57. 在一个二维平面上,有很多个点。然后在原点有一个摄像机,摄像机可以看到一定角度内的东西,比如30度。然后问你这个摄像机要放在多少度角,它能看到的点最多。无论点离原点多远,


只要在角度内都能看到。比如把摄像头放在0度的地方,那摄像头就能看到0到30度之内的所有点。
float GetBestDirection(float *arrX, float *arrY, int n, float f) {},arrX和arrY就是所有点的x和y坐标,n是一共n个点,然后f就是摄像机能看到多少的角度


先把所有点的angle算出来,排序,然后用2 pointer来扫描。


58. 题目的意思是,一个博物馆,有N乘以N个房间,每个房间有OPEN,CLOSED两种状态


如果CLOSED,说明房间不能进人也不能出人


如果OPEN,则可能有守卫在里面,也可能没有守卫


给定N的大小,还有哪些房间CLOSED,哪些房间有守卫


输出:一个N乘以N的矩阵,每个元素的值是这个房间距离最近的守卫的距离


用DP做,从每个守卫出发,然后DFS。


59. given 100 trillion longs, find the 100 largest of those longs. min heap, quick select
60. 第一题是Check whether two binary search trees have same elements,我一上来理解错题意了,以为是有一个相同的element就返回true,结果卡了大概十几分钟,后来才发现是所有的


elements都要相同,赶紧重新写了一遍,有一个小问题,面试官指出了以后赶紧改正。
61. 第二题是给一个数组[x1, x2, ..., xn],要求返回一个数组,数组的每一个元素是原数组中除了自己之外其他元素的乘积,即[x2 * x3* ... xn, x1 * x3 *... xn, ..., x1 * x2 * ... x


(n - 1)],挺简单的,但因为第一题卡了太久,第二题最后一个小循环没写完时间到了,不过在讲思路的时候写了注释,面试官也认可了。
62. leetcode number of islands
63. sudoku solver
64. 就一题多线程的, 如果已经set, set()无操作 ,wait()清除set,如果没有set,set() 就set,wait()坐等直到set。
65. 找出一个数由最少几个平方的和的组成, DP
public int minNumber(int n){. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴 int [] f = new int[n+1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n ; i++){ int j = 1; int min = Integer.MAX_VALUE; while(j*j <= i){ int cur = 1 + f[i-j*j]; min = Math.min(min, cur); j++; } f[i] = min; } return f[n]; }
66. 给一个int array. 此array先是单调递增到某最大值,然后单调递减。 先问怎么找最小值,再问怎么求最大值,并写了求最大值的代码,二分法不用考虑最值在两端的corner case。
67. 给一个int array,里面所有element都是unique的。让写一个shuffle函数令所有element都不在原来的位置上。比如 {1, 2, 3} -〉{2,3,1}
68. 让按层输出一棵二叉树,直接用BFS就可以,很简单
69. reverse words in a string. 要求 in place做
70. 血库有三种血型 O+ A- B- 数量为X Y Z个单位, 给A+,B+,AB- 三种 病人,每种病人数量为I,J,K. 每个人需要一个单位的血。
输血规则 O+血可以输入给A+,B+血型的人, A-血可输给A+,AB-的人,B-可以输给B+,AB-的人。linear programming.
71. Read N Characters Given Read4, what if the read function is called multiple times?
72. 判断是否是binary search tree.
73. 给一个有地势高度的matrix, 周围是2个oceans, 选出能流入both oceans 的位置
               比如((0,3) (2,1) (3,0) 这几个点开始,河流能流入both oceans):
                                   ocean 1
                                   3 2 6 7 
                  ocean 1          4 2 1 3  ocean2
                                   1 5 4 2
                                   6 1 1 3
                                   ocean 2
先从和ocean1紧邻的点出发做一次BFS
然后从和ocean2紧邻的点出发做一次BFS
做BFS的时候,对于点(x, y),如果四周的某个点的高度比它高,就加入到queue
两次bfs都能访问到的点就是结果了
74. 给一个List removeduplicate.
75. 给一个tree, remove 掉其中该remove的node,然后把children接到node's parent上。
76. Input: Array of Sorted IntegersOutput: Pair of integers whose sum is nearest to zero.给了O(n) time, O(1) space的解法
77. 三道题是连续进阶的
1. 给你一个数组 每个元素是一个0~9的整数 把它当做一个整数(e.g. [1,2,3,4]-> 1234), 返回一个数组代表着输入的那个+1(e.g. 1234+1=1235->[1,2,3,5])
2. 给你两个数组 每个元素是一个0~9的整数 把他们当做两个整数 然后返回一个代表他们和的数组([1,2,3],[2,3,4] -> [3,5,7])
3. 给你两个数组 每个元素是一个0~9的整数 把他们当做两个整数 然后返回一个代表他们积的数组([1,2],[1,1] -> [1,3,2]).
78. 0表示旷课,1表示迟到。 连续3次迟到或者一次旷课,就要被罚。那边给定一个string, 判断学生会不会被罚
79. max stack (leetcode上min stack换成max了)
80. Given a collection of boarding passes, the starting city and the destination city, decide if one can get to the destination from the start city.


   graph:
    MIA -> DC
    DC -> NYC
    DC-> MIA


    def can_reach(graph, MIA, NYC)
    很简单的dfs,但是写的时候还是bug百出,最重要的graph里可能的环也忘了处理,问我给几个test cases,bug到我自己不忍直视。。。
    感觉要是自己写的话会好很多,一边跟她讲话一边写就脑洞大开,不知道在想啥了


81. Design a service to shortern url.
    完全没想法,问给你一个original url怎么generate短的url,会有millions of users怎么存储?
    我说 要存在hard disk上而不是memory,然后自己又很二的说了hashtable, 她问disk上的hashtable怎么讲?
    我支支吾吾了一顿,她说要从database取出来然后转成hashtable吗?我这才记起database这回事。
http://stackoverflow.com/questio ... ode-a-url-shortener 
82. 括号匹配
一开始用了O(N)的空间, 后来要求用O(1)的空间完成.
follow up, 不同types的括号匹配 {,[,(
83. Arraylist去重
一开始忘了数组remove要O(n),所以写了个O(n^2)的方法后来被要求实现O(n).
84. Use the shorest unique prefix to represent each word in the array
input: ["zebra", "dog", "duck",”dot”]
output: {zebra: z, dog: do, duck: du}
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=107220&extra=page%3D4%26filter%3Dsortid%26sortid%3D311%26searchoption%5B3090%5D%5Bvalue%5D%3D1%26searchoption


%5B3090%5D%5Btype%5D%3Dradio%26searchoption%5B3046%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311
85. missing range: 扫描一遍list,或者在list中二分查找一百次。
86. 设计一个API,实现用户A发送消息给B,内容包含一个title和context
不知道考点是啥= =. From 1point 3acres bbs
我说 bool send_message(string A, string B, string title, string context) {}
面试官问如果调用这个函数的人把参数的顺序搞错了怎么办,我说那把参数封装成一个class,问我python里面应该怎么做,没答上来。。-google 1point3acres


87. 要求实现一个set,可以用现成的stl,set除了支持插入和删除,还有一个random的功能,能够随机返回当前set里面的一个元素。时间上要求random O(1),插入和删除低于O(n)。想不到怎么


做到这个复杂度。。。
88. given a sequence and a number b between [-10, 10], return the bth sequence, b=1, 1121, next sequence is 211211, b=-1, 211211, previous sequence is 1121
89. Do a quick approximation of the number of bytes needed to store a timestamp value in microseconds that will span until the beginning of 2020?
90. 给一个二叉树,进行非递归的post order traversal