## Wednesday, November 30, 2016

### Google Interview Misc Part 9

 类似于 LC 76. Minimum Window Substring。 但需要保持order

http://massivealgorithms.blogspot.com/2014/07/finding-minimum-window-in-s-which.html

http://massivealgorithms.blogspot.com/2014/07/find-number-of-islands-geeksforgeeks.html
 numberIsland找不同形状的Island的个数比如101001000000. 鍥磋鎴戜滑@1point 3 acres10100100这样上下两个岛形状一样，return

stack 直接 push index 就可以了

http://massivealgorithms.blogspot.com/2016/10/leetcode-416-pacific-atlantic-water-flow.html

http://massivealgorithms.blogspot.com/2015/11/leetcode-308-range-sum-query-2d-mutable.html

1. LC308; max holiday
http://massivealgorithms.blogspot.com/2015/10/leetcode-298-binary-tree-longest.html

LeetCode 340 - Longest Substring with At Most K Distinct Characters

http://massivealgorithms.blogspot.com/2015/10/leetcodegame-of-life.html

1. after k steps，求状态
2. n is very large
3. k is very large

- dfs+trie

ata.1point3acres缃�
tat
ata
. 鍥磋鎴戜滑@1point 3 acres

Output形式比如vector<vector<string>>

1. public List<List<String>> getSquares(List<Integer> strs, int len) {
2.         List<List<String>> result = new ArrayList<>();
3.         List<String> cur = new ArrayList<>();
4.         for (int i = 0; i < len; i++) cur.add("");
5.         dfs(result, cur);. Waral 鍗氬鏈夋洿澶氭枃绔�,
6.         return result;
7.     }
8. . 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
9.     public void dfs(List<List<String>> result, List<String> cur) { 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
10.         int m = cur.size(), n = cur.get(m-1).length();
11.         if (m == n) {
13.             return;
14.         }. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
15.         String pre = cur.get(n);
16.         List<String> list = getStrsByPrefix(cur.get(n), m);
17.         for (String next : list) {
18.             cur.set(n, pre + next);
19.             for (int i = n + 1; i < m; i++) {
20.                 cur.set(i, cur.get(i).substring(0, n) + next.charAt(i - n));
21.             }. Waral 鍗氬鏈夋洿澶氭枃绔�,
22.             dfs(result, cur);
23.         }
24.     }
25.     public List<String> getStrsByPrefix(String prefix, int len) {...}
26.     public static void main(String[] args) {
27.         System.out.println((new SquareTrie().getSquares(null, 3)));
28.     }

http://massivealgorithms.blogspot.com/2016/11/leetcode-465-optimal-account-balancing.html

A, B, 2
A, C, 4
B, D, 5
C, D, 4
D, E, 7

A, -6
B, -3
C, 0
D, 2
E, 7
. 1point 3acres 璁哄潧

A -3,
B -2,
C, 0
D, 2
E, 3.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�

1. 给n个集合比如{a, b}, {1}, {x, y}. 从每个集合里面去一个数组成新的集合，输出所有这种集合，比如例子就是：{{a, 1, x}, {a,1,y}, {b,1,x}, {b,1,y}}.2. 写完后开始聊多线程，聊完就说你写个死锁吧，然后就写了2个线程和2个锁来读写文件的死锁情况，他也很满意，然后问怎么解死锁，我说用一个锁就是了。

1. 给你n个coins和一个value比如1000，输出这些coins能组成多少种value小于1000， 每种coin可以用无限次。直接完全背包秒杀了。

3. 给你两个string s和t, 问s是否能删除小于N个字符，使得结果是t的一个子串，比如 "book, aook", N = 1, return true;看完直接懵了，因为最近做two points太多了，就朝那个方向想，一直想去用O(N)，最后他说不行，我也发现不行，然后45分钟一到，直接就说拜拜了。

2.         ls = len(s)
3.         lt = len(t)
4.         dp = [[ls for j in xrange(lt+1)] for i in xrange(ls+1)]
5.         #max value is ls as empty always be substring of other strings.鐣欏璁哄潧-涓€浜
6.         for i in xrange(ls+1):
7.                 dp[i][0] = i # when t is empty, we need make s empty too
8.         for j in xrange(lt+1):
9.                 dp[0][j] = 0 #when s is empty, s is substring of any string

10.         for i in xrange(ls):
11.                 for j in xrange(lt):
12.
13.                         if s[i] == t[j]:
14.                                 dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j])
15.                         else:.鏈枃鍘熷垱鑷�1point3acres璁哄潧
16.                                 dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j+1]+1)
17.         ans = ls. From 1point 3acres bbs
18.         for x in dp[ls]:
19.                 ans = min(ans,x)
20.        return ans
21. .鏈枃鍘熷垱鑷�1point3acres璁哄潧
22. print solve('okok','okok')
23. print solve('book','aooksbooks')

if s == t[j]:.鏈枃鍘熷垱鑷�1point3acres璁哄潧
dp[i+1][j+1] = min (dp[j],dp[j]+1).鏈枃鍘熷垱鑷�1point3acres璁哄潧
else
dp[i+1][j+1] = min(dp[j+1]+1,dp[i+1][j]. From 1point 3acres bbs

1. coins那个题目跟combination sum完全一样啊，dp不是最优解。如果给的比如是1,5,20的coins，那么跳跃非常大，dp是差劲的解

2. 楼主二面最后一个题，跟edit distance有点像，但是简单太多了，我不知道为什么要用dp，因为是要求subarray，而且只有删除一个操作，直接把s里面不满足t的全都删除掉，看次数是不是小于N就行了，我粗略举了个例子，idea就是把t的char和indices读一遍，存到map<char, minHeap<index>>里面，然后对s线性走一遍，如果不在map，删，如果在map，poll掉minHeap的top，这样average情况就是线性的.

http://massivealgorithms.blogspot.com/2016/04/leetcode-340-longest-substring-with-at.html

arr=[1,2,3,4,5], C=10 , if T=2, sum = 1 + 2 + 2 + 2 + 2 = 9合法, if T = 3 sum = 1 + 2 + 3 + 3 + 3 = 12 > 10不合法，求合法的最大T

2. 两堆个数相等的石子，给了部分石子之间的的重量关系，问能不能判断第一堆石子比第二堆重。用暴力的backtracking做了，做完时间到了，面试官说还有更好的算法，回去查了下是类似二部图的完美匹配问题

o(n) 做法类似lc334

1.Leetcode course scheduleII简化版，不会有环=>一定有一个sequence。
2.（地里前几天的面经有）Guess string(jargo game?)给一个dictionary,一个Picker选一个词并返回guessed string和该词的相同char的个数（给了int makeguess(String guess)），implement Guesser的guess()  method,使得尽量少调用makeguess()方法
3.给一个target Node和sourceNode,判断两个是否相连（Kary tree），自己定义Node, follow-up：如果你可以process given data structure优化search的time complexity，先想到用hashmap,又说能不能在O(1)的空间优化。

1. 假设一个文件从storage的提取有0.1的可能0.1秒完成，0.4的可能1秒完成，问如果当用户提取文件的时候是随机从三份备份中选择一份，问消耗时间的概率分布是怎样的，而且要用r写出来。

2.云存储每天要存入大量的文件，我们有很多硬盘，希望存储文件的数量能够尽量均匀。问需要什么statistic能知道我们的算法确实work了--大概就是文件数足够均匀

|
1500|^^^^^^^^^^^^ 95%quant
|
900|^^^^^^^^^^^^median
|
—————————— t. v

Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32, find the maximum result of a[i] XOR a[j].http://massivealgorithms.blogspot.com/2016/10/leetcode-421-maximum-xor-of-two-numbers.html

lz到最后一行代码都没写，绝逼是没戏了。

example：
input:
aaa
bsdf
fas
aaa
aaa
bsdf
fas

1. 给一个2d matrix，顺时针方向从外往里trace一遍里面的element。举个例子. 鍥磋鎴戜滑@1point 3 acres
1  2   3  4 . 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
5  6   7  8
9 10 11 12

1 2 3 4 8 12 11 10 9 5 6 7

2. 写一个iterative version的BST的in order traverse. 用stack可以写出来 但是面试官要求不能在tree里面加mark所以我当时没憋出来

1. check two binary tree are similar

1.        5
2.    2      4
3. 1   3   null   6

4.       5
5.   2       4
6. 3   1  6    null

1. public boolean helper(root1, root2){
2.     if(root1==null && root2==null) return true;. from: 1point3acres.com/bbs
3.     if(!(root1!=null && root2!=null && root1.val==root2.val)) return false;
4.     return (helper(root1.left, root2.right) && helper(root1.right, root2.left)) || (helper(root1.right, root2.right) && helper(root1.left, root.left));  .鐣欏璁哄潧-涓
5. }

. 然后5分钟写完了.

binary tree的inorder recursive and iterative 两种写法， 如何测试。

2. 中国年轻美眉. from: 1point3acres.com/bbs

1. public class P000_FunnyIterator implements Iterable<Integer> {
2.         List<Integer> data;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴

3.         P000_FunnyIterator(int[] input) {
4.                 if (input == null || (input.length & 1) == 1)
5.                         throw new IllegalArgumentException();
6.                 int n = input.length;
8.                 this.data = new ArrayList<>();
9.                 for (int i = 0; i < n; i += 2) {
10.                         for (int c = 0; c < input[i]; c++)
12.                 }
13.         }

14.         @Override
15.         public Iterator<Integer> iterator() {
16.                 return data.iterator();
17.         }
18. }

1. public class P000_FunnyIterator implements Iterator<Integer> {
2.         int[] data;
3.         int curPos = 0;
4.         int curCount = 0;
5. .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
6.         P000_FunnyIterator(int[] input) {
7.                 if (input == null || (input.length & 1) == 1)
8.                         throw new IllegalArgumentException();
9.                 for (int i = 0; i < input.length; i += 2)
10.                         if (input[i] < 0)
11.                                 throw new IllegalArgumentException();. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
13.         }
14. . visit 1point3acres.com for more.
15.         @Override
16.         public boolean hasNext() {
17.                 while (curPos < data.length && data[curPos] == 0)
18.                         curPos += 2;
19. .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
20.                 return curPos < data.length;
21.         }

22.         @Override
23.         public Integer next() {
24.                 int ans = data[curPos + 1];
25.                 curCount += 1;
26.                 if (curCount == data[curPos]) {
27.                         curPos += 2;
28.                         curCount = 0;
29.                 }
30.                 return ans;
31.         }.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�

32.         @Override
33.         public void remove() {
34.                 throw new UnsupportedOperationException();
35.         }
3. 白人小伙
Number of island II

4. 印度老汉。

String findMin(String s, k){}
e.g.
input
s=pineapple, k==3,

output: ale
ale is the lexical order smallest subsequnce of length 3.
http://massivealgorithms.blogspot.com/2016/09/leetcode-402-remove-k-digits.html

1. find the first occur position of distinct char.
2. then start from that position.
3. dfs to find lenght==3, subsequence(dfs, combination way); . visit 1point3acres.com for more.
4. find the one with smallest lexical order.

pop的时候需要看后面还剩几个元素了

f->e->d->c->cb->cba
5. 印度小伙， 同时参看上的图. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴

input:
a. 有n个城市， 每个城市之间有飞行时间，
b. 给个飞行时间，
c. 给个vacation array, 代表每个城市每周的假期
d. 从第一个城市开始

1. 去掉那些飞行时间超过给定飞行时间的边。
3. 然后bfs, 暴力求解。
4. 没写完。。。。。。

.1point3acres缃�

week1, A, sum=2; . From 1point 3acres bbs
week2, B/C, sum=sum+1;
week3, 回到A, sum+=3
total sum =6

4贪心就可以了
4就是把输出string当个栈，如果当前进来的字母比栈顶的小，就把栈顶的扔掉，小的放进去

p->i->in->ie->a->ap->app->al->ale

5可以dp的

for 第k周
for 城市c
计算第k周在城市c的话，前k周最大享受的假期数
for loop里面那个计算可以递归根据第k-1周，城市c'的结果来算

5就是算前x周，假设你最后一周在城市c的话，最多的假期数。

.1point3acres缃�

|n - i| <= v
v等于是这个题目的第三个input

boolean checkExist(int n, int k, int v)

. From 1point 3acres bbs

"This is a dog"

"This is a dog "

Number of Island ||

. from: 1point3acres.com/bbs

"This    is     a     dog"

"This is a dog           "

k element那题不要求distinct的。

（1）白人小哥1，上来问会不会多线程，咱们写一个多线程的题吧。楼主有点懵这个真没有专门准备不过好在好在题目不难，

- delay queue

http://massivealgorithms.blogspot.com/2016/06/leetcode-361-bomb-enemy.html
http://massivealgorithms.blogspot.com/2015/11/leetcode-311-sparse-matrix.html

（4）白人小哥4，LC原题317，只不过房子变成了职员和咖啡机，找到一个摆放咖啡机的地方和所有职员距离和最短，问好了限制条件比如员工可不可以跨过员工什么的开写

Follow up一下上周和HR约了半小时聊一下feedback，他说我是positive and negative mixed review, negative 主要是问题是ask too many hints， 看起来就是第五轮国人小哥时候有点懈怠，确实是经过了提醒才写出来的

. LC 226 invert binary tree

2. LC91 decode ways

(0,0)-(1,0)-(1,1)-(0,1)-(0,2)-(1,2)-(2,2)-(2,1)-(2,0)
(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,1)-(1,1)-(1,0)-(2,0)

follow up：n*n的迷宫墙的数量是多少(2*n*(n-1) - (n - 1)) 这个不应该等于n*n - path length吗？还是我想完全偏离了？

. From 1point 3acres bbs

309 digits,相当于 2^1024
. 1point 3acres 璁哄潧
The fuel control mechanisms have three operations:

2) Remove one fuel pellet
3) Divide the entire group of fuel pellets by 2 (due to the destructive
energy released when a quantum antimatter pellet is cut in half, the safety
controls will only allow this to happen if there is an even number of
pellets)
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.

Write a function called answer(n) which takes a positive integer as a string
and returns the minimum number of operations needed to transform the number
of pellets to 1. The fuel intake control panel can only display a number up
to 309 digits long, so there won't ever be more pellets than you can
express in that many digits.

For example:
answer(4) returns 2: 4 -> 2 -> 1
answer(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1-google 1point3acres

EDIT:这个最后使用java 里面的BigInteger,不够时间也不确定python怎么做类似的事

1. 关于License Key，就是给一个字符串包含'-'，现在重新给一个K，要求 reinsert '-' 把字符串分隔成若干组每组K个字符第一组可以少但是至少有一个
2. 给一个二叉搜索树，求一个包含节点最多的子树，要求子树每个元素都在给定的区间内[A, B].

reference letter是推荐信吗? 我没有推荐信哎. 我是在周三的时候,hr让我赶紧给她提供我现在单位的三个reference联系人信息, 然后周四就马上让这三个人填对我的review啥的, 他们submit完了才给的offer

Leetcode原题Plus One

public static List<Long> getTopKCandidates(List<Vote> votes, int k, long t)

class Vote{
long candidateId;
long timestamp;
}
(candiateID, timestamp)
(500, 4000)
(600, 5000)
(600, 3000)
(500, 8000)
(300, 2000)
(300, 1000)
k = 2. visit 1point3acres.com for more.
t = 6000

return (300, 500)
heap复杂度是O(nlogk)，k-select会好一点O(n)就好了
O(N) to partition array smaller than t, bigger than t

guess这个function是自己写的，问了一下使用什么数据结构，我说map, array 或者bitmap, 感觉在考察对数据结构的理解。 follow up 如何优化，我就说你可以先猜频率高的词，因为人们倾向于选择自己熟悉的词做secret word。

2.用什么model和test来回答产品经理的问题，为什么选这个方法而不是其他的，然后根据我的回答追问了几个不同测试结果情况下怎么得出结论
3.如果现在加入年龄和性别这两组数据（我提议的数据收集方法是针对每个司机的），你用他们得出什么新的不同的结论，我说可以根据这两组数据分组来进行比较再做测试，然后问了如果年龄这一个数据有3个LEVEL 怎么做测试。

1. 设计数据结构存一堆int，写存的时空复杂度，还有搜索一个数在不在的时间。。

2. 就是dfs或bfs遍历一堆node。。。多用一个hashset存已经访问过的点。。
Coding Sample是两道题目，第一道是：给你一串不知道什么码，例如 "4-15oz-8Tr32" 这样的string，再给你一个int k, 比如说 k = 4, 然后output的效果必须是 "41-5OZ8-TR32"。也就是说，你的新生成的码是要以k个char为一个group，再用“-”连接起来的，而且大家注意所有的字母都要大写哦。还有值得注意的是，第一个group的char可以不是k位，例如上面这个例子，第一个group就只有“41”两位。其实很简单啦，楼主用了非常brute force的方法15分钟搞出来了，有一些corner cases没考虑到最后居然用了25分钟才过的也是悲催啊... 楼主用了1 pass拿到一个不含任何“-”的string，然后string.length() % k拿到第一个group的位数，接下来的事情就好办啦～需要我细讲的孩纸可以在下面评论～这一题楼主用了Java，因为java的.toUpperCase()实在很好用，掺了数字在里面也不影响。

1. 给一堆选票， 选票包含候选人名字，时间stamp，求出给定时间内得票最多的候选人（return 任一）
2. 给一堆选票， 求出给定时间内的得票最多的一堆候选人（return 全部）
3. 给一堆选票，求出给定时间内前K高的一堆候选人
4. 给一堆根据票数多少排序的候选人list, 给一堆选票， 求出哪个时间内可以从这堆选票中得出这堆给你的候选人的list.

Sorry 第四题还有个Input是k， 就是他告诉你了给你的一堆候选人是前k高排序的， 我用votes里的每个时间点 用第三问的那个function 得到一个list, 用这个List与Input list对比，完全一致就是这个时间点。

timestamp是6就是0 - 6， 不会是 2 到 6 这样，所以不是范围，BIT没有必要吧？

is_same_permutation(a, b)

http://massivealgorithms.blogspot.com/2016/11/check-if-two-arrays-are-permutations-of.html

http://massivealgorithms.blogspot.com/2016/04/leetcode-340-longest-substring-with-at.html

1. vector<string> getAllLongestPalindrome(string& s) {
2.   unordered_map<char, int> freq, halfFreq;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
3.   string odds;.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
4.   for (char c : s) freq[c]++, halfFreq[c] = freq[c] / 2;
5.   for (auto& p : freq) {
6.     if (p.second > 1) halfFreq[p.first] = p.second / 2;
7.     if (p.second % 2) odds += p.first;. 1point3acres.com/bbs
8.   }
9.   vector<string> half = getDistinctStrings(halfFreq), res;
10.   for (auto& x : half) {
11.     string rx(x); reverse(rx.begin(), rx.end());
12.     if (odds.empty()) res.push_back(x + rx);
13.     else for (char c : odds) res.push_back(x + c + rx);
14.   }
15.   return res;
16. }

- O(n)
find item where left are smaller, right are bigger

1. 给了一棵树，让写出前序，中序，后序遍历的结果
2. 前序遍历recursive版-
3. 前序遍历iterative版
4. 后序遍历iterative版，这个写的有点纠结，写完50+分钟过去了，就没test