1. card shuffler：shuffle的程序是一个简单的array，array里的值代表当前位置卡片的下一个位置
e.g 当前卡片位置ABCDE shuffle array是01234的话下个卡片位置还是ABCDE，43210的话下个卡片位置是EDCBA。
问给定一个shuffle array，不断用这个array去shuffle，能否得到最初的card deck，能得话要多少次。
我能想到的做法是一个一个的字母找，看多少次能回到原来的位置（或者不能回到原来的位置），记录这个次数为t[i], 然后求所有t[i]的LCM最小公倍数,
求最小公倍数的方法是先求最大公约数（用辗转相除法），然后再用a*b/gcd(a,b) 求最小公倍数。
public int cardShuffler(int[] cards, int[] shuffle) {
int[] steps = new int [cards.length];
for(int i=0; i<cards.length; i++) {
steps[i] = stepsBack(i, shuffle);
if (steps[i] == -1)
return -1;
}
return LCM(steps);
}
private int stepsBack(int start, int[] shuffle) {
int i = start;
int res = 0;
Set visited = new HashSet();
do {
i = shuffle[i];
if (visited.contains(i))
return -1;
visited.add(i);
res++;
} while(i != start);
return res;
}
private int LCM(int[] steps) {
int res = steps[0];
for(int i=1; i<steps.length; i++) {
res = res*steps[i]/GCD(res, steps[i]);
}
return res;
}
private int GCD(int a, int b) {
int n1 = Math.max(a,b);
int n2 = Math.min(a,b);
while(n1%n2 != 0) {
int tmp = n1%n2;
n1 = n2;
n2 = tmp;
}
return n2;
}
2.给定一个binary search tree，返回range内所有key，key可以有重复。
感觉这道题比较简单，就是二分法递归就可以。
public List getKeys(TreeNode root, int start, int end) {
if (root == null)
return new List();
if (start > root) {
return getKeys(root.right, start, end);
}
if (end < root) {
return getKeys(root.left, start, end);
}
List left = getKeys(root.left, start, root.key);
List right = getKeys(root.right, root.key, end);
left.add(root.key);
right.addAll(right);
return left;
}
3. 把一个数拆成任意个平方和的最小拆法。
f(0) = 0;
f(n) = for(i = 1 to sqrt(n))f(n-i*i) + 1;
应该可以用DP优化。
public class Solution {
public int findMinSqrSum(int n) {
int [] min = new int [n+1];
min[0] = 0;
for (int i=1; i<n; i++) {
int m = min[i-1]+1;
for(int j = 1; j <= (int)Math.sqrt(i); j++) {
m = Math.min(m, min[i-j*j]+1);
}
min[i] = m;
}
return min[n];
}
}
1. BST求两个节点和为某个值的数目，2sum变种
简单的做法就是遍历所有的数，将它们存在一个hashset里，因为bst没有duplicate，然后再遍历一遍，找出2sum即可。
还有更优的方法就是用BST的sorted性质，做两个iterator，一个从头开始找next，一个从尾部开始找prev，
public Boolean TwoSumBST(TreeNode root, int target) {
NextIter nIt = new NextIter(root);
PrevIter pIt = new PrevIter(root);
TreeNode n = nIt.next();
TreeNode p = pIt.prev();
while(n.val < p.val) {
if (n.val + p.val == target) {
return true;
} else if (n.val + p.val < target) {
n = nIt.next();
} else {
p = pIt.prev();
}
}
return false;
}
public class NextIter {
Stack stack;
TreeNode p;
public NextIter(TreeNode root) {
stack = new Stack();
TreeNode p = root;
while(p != null) {
stack.push(p);
p = p.left;
}
}
public TreeNode next() {
TreeNode rtn = null;
if (p == null) {
p = stack.peek().right;
rtn = stack.pop();
}
while(p != null) {
stack.push(p);
p = p.left;
}
return rtn;
}
}
public class PrevIter {
Stack stack;
TreeNode p;
public PrevIter(TreeNode root) {
stack = new Stack();
TreeNode p = root;
while(p != null) {
stack.push(p);
p = p.right;
}
}
public TreeNode prev() {
TreeNode rtn = null;
if (p == null) {
p = stack.peek().left;
rtn = stack.pop();
}
while(p != null) {
stack.push(p);
p = p.right;
}
return rtn;
}
public Boolean hasNext() {
return stack.isEmpty();
}
}
第二题Number of Islands。用BFS或者DFS都可以
2. 给字符串，写压缩算法，解压算法已有，例如aaabbbbcccc->aaa4xb4xc，需要考虑3aaaaa->35xa会出问题，
首先分析一下这个题，只有在连续字母超过3个的时候压缩才有意义，另外如果最前面如果是一个数字的话，比如说3aaaaa应该要压缩成3a4xa这样，而不能压缩成35xa。
之后就主要是implementation的问题了
3. 给一堆query，求一个小时内出现次数最多的1000个query，用lg(n)的方法。
对于每个entry，记录query的次数，同时维护一个min heap， 就是最小值在最上面，里面所有的值都比顶点值大的heap，然后每次query都给相应的entry 记录次数++，并且将其插入heap中，如果heap的size超过1000， 那么就拿掉最顶上的那个值（最小值），一个小时以后，heap里存的就是前1000个最大的数
4. 类似系统设计，不是设计一个具体的东西，就是问了很多类似GFS，MapReduce类似的概念.
5. 判断一个word的任何permutation是不是palindrome
能够形成palindrome的条件如下
如果word含有奇数个字母，那么只能有一个奇数个字母，其他都是偶数个字母
如果word含有偶数个字母，那么应该所有字母都是偶数个。
电面
1. Given a sorted array of floats, find the index of the number closest to x:
Example: {1.2, 2.5, 9.3} x = 5, return 1
那这道题其实就是2sum closest，从两边向中间扫，然后计算最小差值。
2. Of the pairs of words in the dictionary that have no letters in common, find one that maximizes the product of the words’ lengths.
这道题好像也没有什么特别的解法，就是一个一个扫O(n^2)
3. bob, joe, bob, jane, bob, joe, jack
bob = 3
joe = 2
topN(2) = bob, joe
interface TopN {
void insert(String query);
List getTop(int n);
}
我能想到的做法就是维护一个Hashmap记录每个String出现的次数。
当需要找topN时，建立一个N size的min heap，然后把所有的数往里放，如果超出了size的话就remove最小的那个，最后这个heap里存的就是topN个element了。只能想到这个做法。
写一个shuffle数组的算法
给一个数组A[]，里面的数是无序的，比如 A[]={1,2,3,7,3,2,5}
shuffle完之后，使之满足A[0]=A[2]<=A[3]..
比如一种可能的结果是 A[]={1,7,3,5,2,2,1}
void shuffle(int A[], int n)
{
}
这道题的算法有两种：一种是先将数组分成两个部分，一部分是全部小于median的，另一部分是全部大于median的，然后两两交换位置插入。求没有sort的array的median的方法有很多种。
1. sort，O（logn）
2. 用minheap找第k最小元素，将所有的元素先build heap，是O（n）， 然后call getMin k times，就可以得到第k小的元素。时间复杂度是 (O(n + klogn),但是要用掉一个O(n)的空间来存heap
3. 用maxheap，方法类似，先建立一个k大的maxheap，然后将所有元素往maxheap里面放，并且删掉最大的元素，最后maxheap里就是第k大的元素。
4. Quick Select:和quick sort类似，先选择一个pivot，然后找到这个pivot的位置，之后再根据这个pivot和k的关系来recursive的寻找，如果piovt的选择是随机的，那么average run time应该是O（n)的。
5 还有改进的Quick Select方法，可以保证worst case的runtime是O(n)， 具体的方法是将array分成5个一组的group（最后一个group可能会没有5个元素），然后每个group找median，放入一个array叫m中，然后用recursive的方法找到这个m的median，用这个median作为pivot来partition这个array， 这样可以保证分出的array是（比较）balanced
另外一种算法是扫描所有奇数项，假设扫描到k了，我们看a[k], a[k-1]和a[k+1]的关系，
1.如果a[k]比他们都大，则不需要做事，直接跳到下一个奇数项
2.如果a[k]比他们都小，或者比其中一个小，则交换那个更大的值。
如果仔细想想，当k已经交换完了以后，k+1之前的数都满足了，而下一个技术项k+1是不可能交换一个比k+1更大的数到k+1的，所以k+1之前就都满足条件了，那么往后就会一直是对的。
Google 店面：
Given these operations:
Update triplets:
: indicates that A is the direct manager of B
: indicates that A and B have the same direct manager.
: indicates that A is the direct manager of B
Query triplet:
: print true/false A is in the management chain of B
这道题应该是先建立一个有向图，然后找是否在manager chain的话就是用dfs或者bfs就可以
public class GraphNode {
char name;
List childeren;
public GraphNode(char c) {
name = c;
children = new ArrayList();
}
public void addChildren(GraphNode n) {
children.add(n);
}
}
//add to graph is simple.
//dfs search for if A is in the management chain of B
public boolean isInManagementChain(GraphNode A, GraphNode B) {
if (isEmpty(A.children)) {
return false;
}
for(GraphNode n : A.children) {
if (n.name == B.name) {
return true;
}
if (isInManagementChain(n, B)) {
return true;
}
}
return false;
}
2. Binary Tree Maximum Path Sum
但是需要是不相邻的node才可以算， 那这道题的做法和Maximum Path Sum其实是一样的，只不过我们除了要传当前root的最大值，还要加上不包括root本身的最大值，这样才好比较。然后用一个global的max来记录大小。
7/29最新google电面，面完接着发面经，攒RP，求下一轮电面或者onsite！！！
通话质量不好，有杂音，好在面试官不是三哥／三姐，口音比较清楚，而且把问题写在了doc上.
两个题
1. longest consecutive numbers
]lc原题，但要考虑重复，而且numbers无序， 并且要输出最长的numbers,
example：
1, 2, 3, 4, 6, 7, 8, 9, 10, 11 → 6, 7,8, 9, 10, 11
11, 10, 9, 8, 7, 6 4, 3, 2,1 ->11, 10, 9, 8, 7, 6
1, 2, 3, 1, 2, 3, 4, 5 -> 1, 2, 3, 4, 5
1, 2, 3, 4, 3, 4, 5, 6, 7 -> 3, 4, 5, 6, 7
这道题的做法应该是用一个hashmap记录所有的数字发生的频率，然后挨个数字扫描，对于每个数字尽量向两边扩充，看能够扩充多少，如果大于max的话，就记录下这些numbers。
2.第1题的follow－up
numbers变成二叉树，找longest consecutive numbers
example:
1
2 3
5 3
→ 1, 2
树的题一向做的不好，感觉和树这种数据结构不来电，花了挺长时间，最后面试官说简化只要求最长的length就好，因为时间紧迫，随便写了一个递归就交了，不知道有没有bug，但是从面试官反应来看，应该写的不是太没水平～～
二叉树的话其实做法和Max Path Sum的做法差不多，让每个节点的children返回到他为止最长的连续numbers，然后用一个global的max比较记录。
public List findLCNinBT(TreeNode root) {
List max = new ArrayList();
}
private List _findLCN(TreeNode root, max) {
if (root == null) {
return new List();
}
List left = extend(_findLCN(root.left, max), root.val);
List right = extend(_findLCN(root.right, max), root.val);
if (left.size() > right) {
if (left.size() > max.size()) {
max = left;
}
return left;
}
if (right.size() > max.size()) {
max = right;
}
return right;
}
private List extend(List range, int i) {
if (range.isEmpty()) {
range.add(i);
}
else if (range.get(0) == i || range.get(0) == i+1)
range.add(0, i);
}
else if (range.get(size()-1) == i || range.get(size()-1) == i-1)
range.add(i)
} else {
range = new ArrayList();
range.add(i);
}
return range;
}
Onsite:
第一轮:
多叉树，每个节点是一个整数，求书中最长递增路径比如5,6,7,8,9
看似简单其实有不少坑，感觉就是跪在这一轮了，所以后边面的反而很放松。。
这道题其实跟之前的这道是一样的，只不过这次不是Binary Tree而是multi tree了。每个node应该要传递包括他自己的递增和递减两个序列给他的parent，并且用一个global的List来保存最长的序列。
第二轮：
四叉树压缩黑白图片，一个图片递归分成2×2四部分，如果一个区域颜色一样就设为叶子节点，算黑像素比例
follow up是给两个图片，把白色视为不透明，黑色视为透明，重叠在一起，返回一个图片，都用四叉树表示
这个递归不难，感觉做的不错，最后出了一个小bug，在他提示下改了
可以用dfs做，每往下一层，代表的百分比就/4
public double findPercentage(TreeNode t) {
Percentage total = new Percentage();
return dfsFindPrcentage(t, 0, total);
}
public class Percentage {
public double per;
}
private void dfsFindPercentage(TreeNode t, int level, Percentage total) {
if (t.isLeaf()) {
if (t.isBlack()) {
total += 1/(Math.pow(4, level);
}
return;
}
for(TreeNode n : t.children) {
dfsFindPercentage(n, level+1, total);
}
}
重叠的话也是用recursion做。
如果发现其中一个node是黑的leaf的话，直接将另外一个copy过来即可。如果是白色leaf的话，那么就保留白色leaf。
public TreeNode _dup(TreeNode t1, TreeNode t2) {
if (t1.isLeaf()) {
if (t1.isBlack()) {
return t2;
}
return t1;
}
if (t2.isLeaf()) {
if (t2.isBlack()) {
return t1;
}
return t2;
}
TreeNode res = new TreeNode();
for(int i=0; i<4; i++) {
res.children.add(_dup(t1.children.get(i), t2.children.get(i)));
}
return res;
}
一堆密码箱，每个密码都是四位0-9之间，算一个暴力破解String，包含所有可能的四位序列，让这个序列尽量短.
我们就用枚举的方法，尽量让重复的序列大，然后先试3个重复的，然后2个 1个。 用一个hashset来记录已经访问过的数字。
其实这是一种greedy algorithm，由于初始值不同，有可能不是最短的序列。
最后一轮，求sum(n^i) 就是1+n+n2+n3+…+n^N， 快速写了一个O(N)之后让我优化，其实这个二分O(lgN)很容易想的，但是当时用了很长时间表现不太好。
这道题可以用dp做
public long getPowerSum(int n, int i) {
int[] dp = int[i+1];
int total = 0;
for(int j=0; j<=i; j++) {
if (j == 0) {
dp[j] = 1;
} else {
dp[j] = dp[j-1]*n;
}
total += dp[j];
}
return total;
}
第二题是个矩阵，每个节点是一个计算机，计算机之间传一个文件的cost是节点值x路径长度，选择所有计算机为接收端，求所有文件传输的cost
感觉要用2次dp一次算出从上面和左边的，一次算出下面右边的。
input: 一个文件，包含了很多单词，可以全部装入内存一个target number ： t
output： 一个单词的最小set，这些单词的出现的频率的总和大于等于t
比如，文件中 A 500次，B 300, C 200, D100, t = 1000. 结果为 A，B, C.
因为可以放进内存里，所以我们就用一个hashmap来记下所有的单词出现的频率, 然后用这个所有单词的list build一个max heap，最常出现的放在max heap的顶上，这样我们每次从heap里拿最大的那个值，加进total里并且和target比较即可。buildheap是O(n), 每次拿出一个heap的最大值是olog(n). 记下所有单词是O(n),所以最差情况还是O(n);
public List letterSum(List words, int t) {
Map<String, Integer> map = new HashMap<String, Integer>();
List sList = new ArrayList();
for(String s : words) {
if (map.containsKey(s)) {
map.put(s, map.get(s)+1);
} else {
sList.add(s);
map.put(s, 1);
}
}
maxHeapify(sList, map); //use List as Heap;
int total = 0;
List res = new ArrayList();
while(!sList.isEmpty()) {
String s = pop(sList, map);
res.add(s);
total += map.get(s);
if (total >= target)
return res;
}
return res;
}
private List maxHeapify(List list, Map<String, Integer> map){
for(int i=list.length()-1; i>= 0; i++) {
int leftChild = i*2 + 1;
int rightChild = i*2 + 2;
int r = i;
while(r != -1) {
r = maxHeapifyHelper(list, map, r);
}
}
}
private int maxHeapifyHelper(List list, Map<String, Integer> map, int i) {
int leftChild = i*2 + 1;
int rightChild = i*2 + 2;
if (leftChild < list.length() && rightChild < list.length()) { if (list.get(leftChild) > list.get(i) || list.get(RightChild > list.get(i)) {
return swap(list, leftChild, rightChild, i);
}
} else if (leftChild < list.length()) { if (map.get(list.get(leftChild)) > map.get(list.get(i))) {
swapHelper(list, leftChild, i);
return leftChild;
}
} else if (rightChild < list.length()) { if (map.get(list.get(rightChild)) > map.get(list,get(i))) {
swapHelper(list, rightChild, i);
return rightChild;
}
}
return -1;
}
private List swap(List list, Map<String, Integer> map, int i, int j, int root){
if (map.get(list.get(i)) > map.get(list.get(j))) {
if (map.get(list.get(i)) > map.get(list.get(root))) {
swapHelper(list, root, i);
return i;
}
} else {
if (map.get(list.get(j)) > map.get(list.get(root)) {
swapHelper(list, root, j);
return j;
}
}
return -1;
}
private void swapHelper(List list, int i, int j) {
int tmp = list.get(i);
list.set(j, list.get(i);
list.set(i, tmp);
}
private String pop(list, Map<String, Integer> map) {
swap(list, 0, list.size()-1);
int res = list.remove(list.size()-1);
maxHeapifyHelper(list, map, 0);
return res;
}
也可以用selection algorithm去解决的这个问题。每次随机找一个pivot，然后将pivot放到正确位置，统计之前的所有的数，看是不是可以满足target，如果可以满足的话，就继续找，直到找到一个可以满足的数并且之前一个正好是不满足的数。就是答案了。
店面：
第一题，上来问了一下hashing解释一下。说为啥能constant time get数据。 我心想index过去就有了。让后blabla。
完了叫我写hashcode function， 之前看到eclipse里面hashCode function的提示。 于是就写这个了。 s[0]*31^(n-1) + s[1]*31^(n-2) … + s[n]
然后就缩这个是O(n)， 就不是constanttime ：（ ， 那就算到s[0] 到s[10] 吧。
第二题，一道Math题。就是求float number 的squre root: public float sqrt(float f, int p)， precision是表示小数点后位数（2就要两位一致）。我就先找到result两边的integer标为l , r。 然后就一阵二分法。问题是， 判断precision和大于一小于一时出错了。然后一阵改。。。。。表示很无奈。这种math， corner cases特别多的没准备好。说好的array， string，说好的tree，说好的recursive呢，都没有。。
public float sqrt(float t, int p) {
float res = (float)sqrt((int)Math.floor(t));
float diff = 1.0;
float step = diff/10;
for(int i=0; i<p; i++) { float l = res + diff; float r = res; float mid =(l + r)/2; while(l >= r) {
if (mid * mid == t)
return mid;
else if (mid * mid > t) {
l = mid – step;
} else {
r = mid + setp;
}
}
step /= 10;
diff /= 10;
res = l;
}
return res;
Google On site
1. binary search.
大概就是，一个数组, 1112223334445556677888…当中少2个数字，找到就行了。
写完大概还有20分钟，让他几个test case,向了4个case,把code path都过了一边，然后没时间了。
既然已经排过序，直接找一遍就是O(n).但是因为这个数组是排序的，所以我们可能可以用更好的办法（binary search O(logn)
public int[] find2Missing(int[] input, int start, int end, int[] res) {
if (start > end)
return res;
int mid = (start + end)/2;
if (input[mid] < input[mid+1]-1) { res = recordRes(input[mid] + 1, res); } if (input[mid] > input[mid-1])+1 {
res = recordRes(input[mid] -1, res);
}
if (res[0] != 0 && res[1] != 0) {//found
return res;
}
res = findMissing(input, start, res);
if (res[0] != 0 && res[1] != 0) {//found
return res;
}
res = findMissing(input, end, mid);
return res;
}
private int[] recordRes(int r, int [] res) {
if (res[0] == 0) {
res[0] = r;
} else {
res[1] = r;
}
return res;
}
大概就是一个数组
1,4,2,6….
每次调用一个函数，按照数组里面的数字的大小，返回相应的Index。
比如， 上面的例子就是
1/13 的概率返回0,
4/13的概率返回1.
首先我们把所有的和都加起来，比如说上面的例子就是13。
然后按rand一个1到13之间的数t，然后看t落在哪个index的区间，
给一个image, 中心对称一下。 LZ一直写的Python,他让我用java,因为输入是byte [] image,
有点忘记java了。 先大概10分钟写完，后来发现题目意思理解错误，Image 每个像素是一个bit，我以为是
一个byte。 然后擦光重写，最后虽然写完了，他看了一边，觉得没有bug。然后就提问了一下，结束。
这道题就是reverse每行，然后reverse每列，就得到了中心对称的图形。
Topological sort的题目：
Topological sort有两种做法，一种是用DFS，就是一般的DFS加一个visited set记录已经访问过的节点，一旦到达了一个根节点（他没有子节点或者子节点都被访问过）就放入一个result的array里，最后这个array里的顺序全部倒过来就是topological sort了。当然这种算法有个问题就是要先确定这个graph是acyclic的。
还有一种方法是先找到一个没有in edge的节点，将这个节点放入result里面，然后搜索这个节点的所有子节点，找下一个没有in edge的节点。如果找不到这样一个节点，说明有cycle。不然的话应该可以拿走图里面的所有节点。如果是这种做法的话，我们就需要一个in edge的matrix和一个out edge的matrix，out edge我们用来找下一步搜索的节点，in edge的用来remove节点并放入结果list
除了排dependency（pre-requisite的课程），还有一类字典的题可以用topological sort
有一个字典因为某种原因每个字符都被替换成一个别的字符了（但还是一一对应)，
但是单词的顺序没有改变，比如
cat
coffee
common
变成了
dkc
dbhhzz
dbllbq
所以我们要做的就是先从这个单词的顺序中得到一个字母的topological sort, 两两比较，得出一个DAG
List<List> graph = new ArrayList<List>();
for (int i = 0; i=words.size()-2; i++) {
String w1 = words.get(i);
String w2 = words.get(i+1);
int j = 0;
int k = 0;
while(j < w1.length() && k < w2.length()) {
if (w1.charAt(j) = w2.charAt(k) {
i++;
j++;
} else {
if (graph.get(w1.charAt(j)-‘a’) == null) {
graph.get(w1.charAt(j) – ‘a’) = new ArrayList();
}
graph.get(w1.charAt(j) – ‘a’) = w2.charAt(k) – ‘a’;
}
}
}
//now generate a in graph out of the out graph.
List<List> inGraph = new ArrayList<List>（）；
for (int i=0; i<graph.length(); i++) {
for(int j = 0; j<graph.get(i).length(); j++) {
int k = graph.get(i).get(j);
if (inGraph.get(k) == null) {
inGraph.add(k, new ArrayList());
}
inGraph.get(k).add(k, i);
}
}
List = topSort(graph, inGraph);
private List topSort(
1. 二叉树的序列化和反序列化，节点的value是String类型
2. 找两个排好序的list的共同元素
5 -> 6 -> 6 ->8
4 -> 4-> 6 -> 6 -> 8
答案是 6 -> 6 -> 8
这道题的做法是可以这样，用两个指针指向这两个list的head，然后比较，如果相等的话，就把两个数都放进结果里，然后同时向后移动， 如果不相等，我们就只把比较小的那个向后移动。这样的话我们只会移动O(m+n)次。
follow up如果一个list很小一个list很大有没有办法优化。如果用上面的办法的话就其实没有什么差别了。
Onsite:
merge K lists变形。变简单，你可以定义一个class来描述输入list.
这道题就是两种做法，一种是建立一个k个的数大小的heap，然后每次都都从这个min heap的顶上拿最小的那个node，然后将这个list的下一个数放进heap里，直到拿完为止。
还有一种办法就是两两list merge。 假设每个list都是n个数长，那么时间复杂度应该是O(nlogK).
第二轮： 讨论算法，没有写代码。输入是一串字符和一个字典。找出字典里面包含所有输入字符的最短序列。
比如：输入时”ca”, 字典里面有 [“cat”,”tac”,”act”,”sdf”,”asdf”]
那么返回： “cat”,”tac“， “act”.
面试官期望的应该是用tree来做的，但是我没想到最优的tree结构。
唯一能想到的tree的结构就是所有的string 都sort一下，然后和原string hash到一个hashMap里，然后建trie。但是这个方法也不一定快。
給一個車牌號碼(美國的)，以及一個dictionary，請找出dictionary裡含有所有該車牌號碼裡的所有英文字母(case insensitive)的最短字串.
車牌 RO 1287 [“rolling”, “real”, “WhaT”, “rOad”] => “rOad”
follow up:
(1) 如果dictionary裡有上百萬個字，該如何加速
(2) 如果dictionary有上百萬個字，然後給你上千個車牌號碼，要你回傳相對應的最短字串，該如何optimize?
所以我们如果要搜索所有的string的话，用strstr的话就是O（n*m), n是字典的大小，m是每个word的长度。可不可以做到O（n）呢？其实我们可以把26个字母转换成一个bit mask，这样每次比较每个单词是否包含特定的字母就只需要用一次位运算就可以了。这种方法的问题就是没法处理duplicate的情况，除非我们用一个array来统计每个字母出现的次数。
给你一组Treenode，他们每个有一个id，一个parentId，一个value，让你输出所有subtree的sum of value
注意这个是没有children node的，只有parentId。 她先问是top down还是bottom up，因为只有parentId所以是bottom up， 然后输出吧， 其实就是层遍历，但是重点是如何找每一层的node，什么时候跳出循环，她hint了我，然后写的时候出了java api的bugs。。不过还是立刻改过来了，然后问运行时间，结果中途电话还断了一次。。居然面试还能超时5分钟。。。也是醉了
周四Google电面完，周五收到onsite，周六来发下面经。
可能是因为我做得慢，总共就做了一道题，就是一个游戏。
input string：“+++–++-+”
游戏规则：每人每次可以 flip “++” to “–“（必须是相邻的）
第一问：generate all possible moves
第二问：determine if this player can will
Extra：这两个问题的implementation的Big-O
下个人没法flip了这个人就赢；all possible moves for next flip
对于all possible moves，我们可以用recursion dfs的方法，选定一个++，flip成–， 用剩下的string继续recursive直到找不到连续的++为止。O(n!)的时间复杂度。
当没有人可以flip了，这个人就输了，所以最后一个人的position是losing position。而只要上一步任意一步可以走到losing position，那么这个position就是winning position（因为假设player一定会挑optimized办法），不然他就是losing position。
用dp的话其实不太好用，我们可以用dp解决连续个“+++”的问题， 然后再用这个结果来解决整个string的问题。
boolean [] isWin = new boolean [s.length()];
for (int i = 0; i<isWin.length(); i++) {
if （i == 0 || i == 1) {
isWin[i] = false;
} else {
isWin[i] = false; // if cannot go to any losing position, it is losing position
for (int j = 0; j <= i-2; j++) {
if (isWin[j-1] && isWin[i-j-2]) || (!isWin[j-1] && !isWin[j-1]) {
isWin[i] = true;
break;
}
}
}
}
然后我们统计input里所有的连续++，，如果isWin的数目是奇数个，那么就是先手赢，不然的话就是输
1. array， 找一个point，两边总和相等， 很简单，要注意负数情况
其实就是两边扫，先计算一下所有的element的和，然后从左边开始扫。扫到一个数就加进左边的sum，并从右边的sum减去，直到搜到两边相等为止。
implement 2048
假设有一个队列每个人都有不同的高度。给定所有人的高度和每个人之前比他高的人的个数，要求rebuild 这个array。
按照比他之前的高度的人数开始往结果里放，先放0的，如果有多个0的那么就按高度顺序往里放，然后再放1.2。。。的
class Person {
int height;
int front;
Person(int h, int f) {
this.height = h;
this.front = f;
}
}
public int[] rebuild(int[] height, int[] front) {
List<Person> list = new ArrayList<Person>();
for (int i=0; i<height.length; i++) {
list.add(new Person(height[i], front[i]);
}
//sort the people by front, then by height.
Collections.sort(list, new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
if (p1.front != p2.front) {
return p1.front - p2.front;
}
return p1.height - p2.height;
}
);
//insert the persons based on the sorted order
List<Person> result = new ArrayList<Person>();
for (int i=0; i<list.size(); i++) {
Person p = list.get(i);
if (p.front == 0) {
result.add(p);
} else {
int count = 0;
for(int j=0; j<result.size(); j++) {
if (p.height < result.get(j).height) {
count++;
}
if (count == p.front) {
result.insert(j+1, p);
break;
}
}
}
}
一个白人小哥，上来直接在google docs上粘贴了题目.
write a function to add operator(+-*/) to a string so it equals to a target value
for example
123,6 -> 1+2+3
12345, 27-> 1+2*3+4*5
然后我问了数字顺序能不能变，答说不能；问了要不要括号，答说不能用括号。
最开始就想到了类似leetcode basic calculator，后来又想到了用backtracking，但是backtracking不是很熟，写了半天也没写对，时间到了就问了几个问题就thank you了
public boolean getResult(String s, int target) {
}
public boolean helper(String s, int target, int pos) {
if (pos == s.length) {
return calculator(s) == target;
}
StringBuilder sb = new StringBuilder(s);
if (helper(sb.toString(), target, pos+1)) {
return true;
}
sb.insert(pos, '+');
if (helper(sb.toString(), target, pos+2)) {
return true;
}
sb.setCharAt(pos, '-');
if (helper(sb.toString(), target, pos+2)) {
return true;
}
sb.setCharAt(pos, '*');
if (helper(sb.toString(), target, pos+2)) {
return true;
}
sb.setCharAt(pos, '/');
if (helper(sb.toString(), target, pos+2)) {
return true;
}
return false;
}
//takes in a string of equation and return result
private int calculator(String s) {
List<String> list = new ArrayList<String>();
int start = 0;
for (int i=0; i<=s.length(); i++){
char c = s.charAt(i);
if (!Character.isDigit(c) || i == s.length()) {
String tmp = s.substring(start, i);
list.add(tmp);
start = i+1;
if (i < s.length()) {
String op = new String(c);
list.add(op);
}
}
}
Stack<String> cal = new Stack<String>();
for (int i = 0; i<list.size(); i++) {
String t = list.get(i);
if (t.equals("*")) {
int r = String.ValueOf(cal.pop()) * String.ValueOf(list.get(i+1));
cal.push(Integer.parseInt(r));
i++;
} else if (t.equals("/")) {
int r = String.ValueOf(cal.pop()) / String.ValueOf(list.get(i+1));
cal.push(Integer.parseInt(r));
i++;
} else {
cal.push(t);
}
}
//process the + and -
int r = 0;
while (!cal.isEmpty()) {
int n = Integer.parseInt(cal.pop());
if (cal.isEmpty() || cal.pop().equals("+")) {
r += n;
} else {
r -= n;
}
}
return r;
}
warm up 问题：求 int(log X). 第二题， 给一堆strings 和一个input string, 在input里找出minimum unused char.
求logX就是用binary search在0到X之间搜索一个数字n^10 x or n^10 == x
public int getLog(int X) {
int start = 0;
int end = X;
while(start X) {
end = mid-1;
} else {
start = mid+1;
}
}
return start;
}
2. 国人小哥。特别nice！给一个数字的array，两个数字间只用+或者* 算出最大的值。
当然可以用dfs try all possible combinations and get max。但是因为只需要知道max。所以可以用dynamic programming 的办法来记录每个的最大值和最小值（*）的话可能会由最小值变成最大值。等等
public int getMax(int[] input) {
int[] max = new int [input.length];
int[] min = new int [input.length];
for (int i=0; i<input.length; i++) {
if (i==0) {
max[i] = input[i];
min[i] = input[i];
} else {
max[i] = Math.max(input[i] + max[i], input[i] * max[i], input[i] * min[i]);
min[i] = Math.min(input[i] + min[i], input[i] * max[i], input[i] * min[i]);
}
}
return max[input.length-1];
}
3.烙印大叔。 给一个array 和一个 target求出 array里有几组tuple相加是小于等于target的。 第二题是一个array里面只有0-9的digits, 有一个target， 判断是否存在一种组合可以等于target。eg: [6,3,1,0,5] target=78,这个return True. 63+10+5 = 78 如果target= 636 return True. 631+0+5 = 636
public int tupletLessThan(int[] array, int target) {
Arrays.sort(array);
int count;
for (int i=0; i<array.length-2; i++) {
int start = i+1;
int end = array.length-1;
//fix end, and add all the numbers that sums to less than target
while(start < end) {
while (array[start] + array[end] + array[i] < target) {
count++;
start++;
}
end–;
start = i+1;
}
}
return count;
}
public boolean findTarget(int[] array, int target) {
int curr = 0;
}
private boolean helper(int[] array, int target, int start) {
if (target < 0) {
return false;
}
if (start == array.length) {
return target == 0;
}
for (int i=start; i<array.length; i++) {
int r = generateNumber(array, start, i);
if (helper, array, target-r, i+1) {
return true;
}
}
return false;
}
private int generateNumber(int[] arr, int start, int end) {
int res = 0;
for (int i=start; i<=end; i++) {
res *= 10;
res += arr[i];
}
return res;
}
4.烙印小哥。 rearrange array，使得相邻两个字符是不一样的。
首先统计所有字符的出现次数，然后每次都拿出现次数最多的那个数字。填进下一个空白的array。
class Node {
char c;
int freq;
public Node(char i, int j) {
this.c = i;
this.freq = j;
}
public void decr() {
freq–;
}
}
public char[] rearrage(char[] arr) {
Map map = new HashMap();
for (char c : arr) {
if (map.contains(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
PriorityQueue priority = new PriorityQueue(100, new Comparator(){
@Override
public int compare(Node n1, Node n2) {
return n1.freq.compareTo(n2.freq);
}
});
Iterator iter = map.iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
priority.add(new Node(entry.getKey(), entry.getValue()));
}
char[] out = new char[arr.length];
int pos = 0;
while(!priority.isEmpty()) {
Node first = priority.remove();
if (pos == 0 || first.c != out[pos-1]) {
out[pos] = first.c;
pos++;
first.decr();
if (first.freq != 0) {
priority.add(first);
}
} else {
Node second = priority.remove();
out[pos] = second.c;
second.decr();
if (second.freq != 0) {
priority.add(second);
}
priority.add(first);
}
}
return out;
}
5. 俄罗斯小哥？长得像格格巫。。。LRU~~.
国人小哥shadow，白人geek主面。问题：将一个image mirror一下。image是用bit表示的。白人小哥不太理人。
如果是用bit表示的，我们只需要按bit reverse每个数就可以。
public int[] reverseImage(int[] image) {
int[] res = new int [image.length];
int p = 0;
for (int i : image) {
res[p++] = reverse(i);
}
return res;
}
private int reverse(int i) {
int res = 0;
int mask = 1< 0) {
res *= 2;
if (mask & i > 0) {
res + 1;
}
mask >> 1;
}
return res;
}
国人小哥，不知道结果怎么样，不过感觉就在一直提醒我，给我感觉挺好的。问题是一个文件，一个set的word，让你找出出现次数最多的word。
想起来感觉只有把所有word扫一遍，统计所有word出现的次数，同时可以找出出现最多的那个。
Map<String, Integer> map = new HashMap<String, Integer>();
for (String w : words) {
if (map.containsKey(w)) {
map.get(w).put(w, map.get(w)+1);
} else {
map.put(w, 1);
}
int maxCount = 0;
String rtn = null;
if (map.get(w) > maxCount) {
maxCount = map.get(w);
rtn = w;
}
return rtn;
}
白人lead，问题：总结一下就是， 有n个点，［0，1，2］，输出序列为：［0，1，2，1，0，2，0］ 满足： 0->1, 1->0, 0->2, 2->0, 1->2, 2->1， 求得最短输出序列。
感觉这道题只能一个一个的试，用DFS
这题我的想法是这样。。。
要求的这个序列，如果将两点之间看做一条单向边的话，其实这个序列就相当于将一个完全图遍历每个边，且每个边只遍历一次，就是一笔画问题。。
因为是完全图，一定存在解，然后直接dfs就行。。。然后观察一下dfs的解。很容易找到规律。所以最终是可以得到这题的构造解的。
所以实际上就是找一条DFS的路径，能够cover所有的edge，并且最短。
class Edge {
int from;
int to;
@Override
public int hashCode() {
}
@Override
public boolean equals() {
}
}
Set<Edge> visited = new HashSet<Edge>();
List<List<Integer>> adjMatrix = ArrayList<List<Integer>>();
for(int i=0; i<arr.length; i++) {
adjMatrix.add(i, new ArrayList<Integer>());
for(int j=0; j<arr.length; j++) {
if (i != j) {
adjMatrix.get(i).add(j);
}
}
}
int n = arr.length;
int start = arr[0];
List<Integer> res = new ArrayList<Integer>();
dfsFindPath(adjMatrix, n, start, res, visited);
return res;
}
public void findPath(List<List<Integer>> adjMatrix, int n, int start; int res, Set<Edge> visited) {
if (res.size() == n*(n-1)) {
return res;
}
List<Integer> next = adjMatrix.get(i);
for(int i : next) {
Edge e = new Edge(start, i);
if (!visited.contains(e)) {
visited.add(e);
res.add(i);
findPath(adjMatrix, n, i, res, visited();
visited.remove(e);
res.remove(i);
}
}
}
午饭，国人小哥很好。一直跟我聊天。这轮不算在面试之中。
白人，感觉人很好。问题是： longest consecutive sequence in array。followup： longest consecutive sequence in tree,但是是简化版，只要求从parent 到root的longest sequence。
如果是array的话，就把他转换成一个Set，然后对于每个数向两边extend，对于tree的话，因为只是root 到leaf的，所以只要用一个函数return每个节点的最大值，然后用一个global的track，就可以。
白人小哥。问了我一曾经onsite的时候面过的题目。就是一个matrix存value。两种操作，一种是query（x1,y1, x2, y2）返回此区间的value的和。 第二种是update（x, y, v），要求更新matrix的值。followup 分别是如果你想要query快，如果你想要update快。如果你想即让query快，又想要update快。怎么办？
如果想要qurey快，那么就直接存一个每个坐标左上边的所有数的和的矩阵，如果update快，就要直接update原矩阵。
如果要两个都快，就取一个折中的办法，存每一行的col 0 到当前col的和，这样update 和 query都是
O（n）的复杂度了。
感觉整体下来面试不难，但是我每一轮都没有bugfree，每当我说我想要过一个例子来看一下有没有bug，面试官都是觉得没时间了，然后就帮我指出来哪里可能有问题。这个也是我担心的一点。
1. 华人大叔。题目：Given a large integer array, count the number of triplets whose sum is less than or equal to an integer T.
大叔英文很地道, 全程态度比较认真，不冷不热。一开始猛然间以为是3-Sum的题，仔细想想不太一样，细节问题挺多。最后写了一个O(n2lgn)的算法，然后问大叔更简便的有木有，大叔迟疑了片刻说应该有数学相关的取巧办法。。
这道题其实就是先排序，选定一个数，从之后的所有数里面找两个数sum小于target，这个也是先选定一个数，另一个二分查找就可以。
2. 华人小哥。题目：Given an array of Ad (profit, start_time, end_time) and a timespan [0, T], find the max profit of Ads that fit the timespan.
小哥进来就说了句中文：怎么样啊？顿觉好温暖，中文寒暄了几句就用英文开始了。先说了穷举法O(2^n), 然后说了贪心法（不是最优解），最后用DP解决。小哥态度灰常好，给了很有用的提示, 就像自家人啊。
感觉有点像knapsack problem，我们应该建立一个maxProfit[i][j], i start from 0 to T and j start from 0 to Ads[size];
for(int i=0; i<T; i++) {
for(int j=0; j ads[j].time) {
maxProfit[i][j] = Math.max(maxProfit[i-ads[j].time]][j-1] + ads[j].profit, maxProfit[i][j-1]);
} else {
maxProfit[i][j] = 0;
}
}
}
return maxProfit[T][ads.length];
3. 俄罗斯妹子。题目：M x N large board, with only white and black blocks, all black blocks are connected (vertically or horizontally), find the minimum rectangle boundary that contains all black blocks.
妹子笑的好甜，全程一直在笑，还好心地给了提示和假定。感觉交流互动非常好，可惜最后差了一点，没能想出O(n^2)以内的算法。
我们首先要找到第一个black de block，然后对black的block做DFS或者BFS，然后找出上向左右能碰到的最大的black block，然后就能找到矩形的边界了。
4. 美国小哥。题目：Design a algorithm to initialize the board of Candy Crush Saga. With M x N board, Q types of candies. (Rules: no 3 for run after initialization, must contain at least one valid move at the beginning)
小哥说话很和气，先让我介绍了一个project，于是兴致勃勃地讲了做过的一个游戏。他于是拿出手机给我看了这个，说那就出一道游戏题吧。。游戏可以参考（
http://candycrushsaga.com/how-to-play），这道题很开放，没有固定模式和答案，感觉答的还不错。
第一面，一个很屌很拽的三哥。上来就聊social newtwork，讨论里面的connection怎么去assign weight，没什么经验，直接各种脑洞，也不知道说得有没有道理。然后让写一个从一个social graph中找出N个朋友的function，这里我一直以为要用着那个edge的weight，结果开始往最长路径上去想，结果就GG了。后来就写了一个BFS到N个的时候就停止，结果被指出来一堆bug，比如visit的节点忘记加入set了，没处理null的情况，没处理N为非正数的情况啥的。主要还是一上来就被问懵了，这一面感觉就跪了。
List findNFriend(Person p, int n) {
if (n <= 0) return null;
if p == null return null;
List res = new ArrayList();
Stack stack = new Stack();
stack.add(p);
while(stack.isEmpty() && res.size() < n) {
Stack nextLevel = new Stack();
while(stack.isEmpty() && res.size() < n) {
Person np = stack.pop();
res.add(np);
for(Person n : np.friends) {
nextLevel.push(n);
}
}
stack = nextLevel;
}
return res;
}
第二面，一个中年白人。第一个题返回一个字符串中出现次数最多的字符，然后把这个题用MapReduce重新写一遍。第二个题写二叉树的最深深度。第三个题是leetcode上那个把二叉树每一层的节点水平的连接起来。第四个题写N！中0末尾0的个数。这一面感觉没什么bug的地方，感觉一般。
Map Reduce:
Map(String key, String Value) {
foreach word in value {
outputTemp(word, 1);
}
}
Reduce(String key, List value) {
int sum = 0;
foreach int in valueList {
sum++;
}
outputFinal(key, sum);
}
0的个数取决于2和5因数的数量，2的数量一定是大于5的，所以我们应该去找5的数量。N有多少个5的数量呢？个位数是每5个数就有一个，10位数则是每25位有一个，100位数是每125位有一个，这样推进下去。
int fives = 5;
int numZero = 0;
while(n >= fives) {
numZero += n/fives;
n /= fives;
fives *= 5;
}
return numZero;
第三面，一个很geek的三哥。实现SQL里面的group by的functionality，用最直接的方法实现后，更改一下文件的存储方式从而实现更快速的方法。最后拓展到distributed storage上面去，有多个machine在运行你的database，问怎么设计文件存储的方式，从而使你的query尽可能快的完成。这一面感觉一般。
第四面，一个年轻白人。自己设计接口，使得支持两个funciton：onUpdate(timestamp, price) 和 onCorrect(temistamp, price). 可以理解为有一个时间流，每一个timestamp都对应一个股票的时间，每次调用一次onUpdate的时候，就对我们设计的那个类更新对应的timestamp和price， onCorrect就是修改之前的一个timestamp的price。最后，我们的类要能返回latest price， max price 和 min price。一开始题目描述的太模糊了我都不知道到底要干啥，墨迹半天才知道是想设计一个类，然后中途也写的乱七八糟的，用了两个Deque来存储一个递增和一个递减的序列，类似窗口题的方法。当onCorrect的时候就去看队列里面有没有对应的timestamp，有的话移除然后重新入队。感觉这面面的也不是太好。
class Stock{
int id;
String name;
Double latestPrice;
int lastTimeStamp;
Double maxPrice;
Double minPrice;
Map map = new HashMap();
public stock() {
this.map = new HashMap();
maxPrice = Double.MIN_VALUE;
minPrice = Double.MAX_VALUE;
}
onUpdate(int timestamp, double price) {
map.put(timestamp, prices);
if (price this.maxPrice) {
maxPrice = price;
}
if (timestamp > lastTimeStamp) {
this.lastTimestamp = timestamp;
lastPrice = price;
}
this.map.add(timestamp, price);
}
onCorrect(int timestamp, double price) {
}
}
今天下午4:15面的，估计是个白人大哥，人挺耐心但自己水平太差被虐的体无完肤。。。
问一个二维数组表示的n*n的矩阵，找出一条连续的最长的路径的长度。
比如
7 8 6
9 4 5
2 3 1.
最长是2,3,4,5,6，返回长度5.
想到是DP但初始状态不知道怎么确定，以为和lc的 Minimum Path Sum 很像，结果他说不一定从（0， 0）开始就崩溃了。。。写了个暴力算法，让优化，估计GG了。。
O（1）的delte，update，add
Hello World 