google面试题汇总

 

1.给一个数列和一个目标数, 返回目标数出现的次数,数列已经排序

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)

 

 

1.Maximal Rectangle Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

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