google面试题汇总
2.二树， 打印层次顺序的节点 (level order traversal)
3.给一个字符串只由一，零和星组成， 返还一组数， 把星替换成1和2
4.有n个tuple 比如 [“a”,”b”,”c”] [“red”,”blue”]….要求生成 从每个tuple中取一个string构成的所有组合 比如 [“a”,”red”] [“b”,”blue”]…..
5.给一个String的array，问如何移除重复的string (hashmap,bst)
6.binary tree的max height
7.给一个integer的array，按照n1<=n2>=n3<=n4>=n5 的order排序。
A[0]<=A[1]>=A[2]<=A[3] shuffle
coding:
u = [u1, u2, u3, u4, u5, u6, …] (integers)
s = [s1, s2, s3, s4, s5, s5, …]
s1 <= s2, s2 >=s3, s3 <= s4, s4 >= s5,…..
8.fibonacci为啥不用recursive。分别的时间复杂度。空间复杂度，包含函数栈上的
9.sorted array有正有负如何按顺序输出平方值 (binary search,然后两边扫)
10.给一个BST，找第k个元素(inorder traversal or heap)
2.给个Binary Search Tree.with duplicate nodes。要求找到出现次数最多的那个数字。现场coding的话关键注意点在如何inorder遍历的同时刷新max。此外如果max是最后的一组数是个边界条件。
3.插入整数，然后计算最近五个数的平均数。
4.设计snake的数据结构，queue + 二维boolean数组。然后写一个每次移动的函数。
5.给了A[], B[], C[]三个String数组，要求求出数组的Combination，每一个数组中至少选一个，不用考虑duplicate
6.两个数组，问是不是permutation。 然后如果只能用constant space怎么做：quicksort。然后如果再让这两个数组是imutable，而且只能是n的复杂度,不考虑空间用couting sort
7.有这么个游戏，举个例子：给你5个空_ _ _ _ _, 每次猜一个字母，这里出题人想让你猜出来clock，假如你猜a，告诉你这里面没有。你又猜c，他把c全写出来，所以你有c _ _ c _。 让你最多猜10次。写一个程序去猜。输入是几个空，要考虑每次猜的反馈，尽量把词猜出来。
8.坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区域。 2. find（x，y），就是给个坐标，返回这个坐标所在的区域。可以返回区域的id，区域的id自己定。用二叉树。两棵平衡二叉搜索树，找到y1<=point<=y2/None,x1<=point<=x2/None
9.Moving Average, 每次输入一个数，调用double next_val(int val)，和现有的windows_size，输出当前平均数。
例如，win_size = 3，
next_val(1) = 1/3;
next_val(10) = (1 + 10) / 2;
next_val(3) = (1 + 10 + 3) / 3;
next_val(5) = (10 + 3 + 5) / 3 （因为已经数的总数已经到达win_size）
……
这题还算直接，一个queue不断记录当前的win_size个数，一个sum不断记录当前和就行。
10.Use the shorest unique prefix to represent each word in the array
input: [“zebra”, “dog”, “duck”,”dot”]
output: {zebra: z, dog: do, duck: du}
[zebra, dog, duck, dove]
{zebra:z, dog: dog, duck: du, dove: dov}
[bearcat, bear]
{bearcat: bearc, bear: “”}
再进一步处理,或者用radix tree
