Massive Algorithms: Google Interview Misc Part 9

http://www.1point3acres.com/bbs/thread-166355-1-1.html
求string str1中含有string str2 order的 subsequence 的最小长度
举个例子： str1 = "acbacbc" str2="abc", 那么最小subsequence长度应该是4，对应的subsequence是“acbc”

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

那道题要用array或者hashmap记录char出现次数，找到一个合适窗口后，尝试移动左边缘缩小窗口。这道题找到一个合适窗口倒不难，但是该怎么optimize窗口大小呢
http://massivealgorithms.blogspot.com/2014/07/finding-minimum-window-in-s-which.html

http://www.1point3acres.com/bbs/thread-175393-1-1.html
http://massivealgorithms.blogspot.com/2014/07/find-number-of-islands-geeksforgeeks.html

numberIsland找不同形状的Island的个数
比如
1010
0100
0000
1010
0100
这样上下两个岛形状一样，return

http://www.1point3acres.com/bbs/thread-208224-1-1.html
然后狗家的OA除了题目里的testcase，其余的一个testcase都不给。不像hackerrank是有testcase但是看不见testcase是什么，狗家是完全不给要自己写。所以大家准备的时候最好把corner case也想一想！
开始OA之前建议大家试下practice test熟悉界面节省时间~
http://www.1point3acres.com/bbs/thread-210173-1-1.html
第一轮：给一个array, 返回下一个比当前元素大的离当前元素有多远：比如［10，8，6，8，8，11，9］，返回［5，4，1，2，1，－1，－1］第一个10，下一个比10 大的是11，距离为5。没有就为－1. 先让写了naive的 o（n^2）. 然后写了 o（n） stack 实现。
stack 直接 push index 就可以了
是从后往前遍历，然后遇到比栈顶大的就push index，遇到小的，就一个个和stack里的比吗

我是从左到右。如果比栈顶小或等于就push index，如果比栈顶大，就一直pop（）到小于等于栈顶为止。并且对于每个pop出来的index，算出结果。

第二轮： thesis
第三轮： external sort，让自定义读写文件的api，写了merge k sort list，没写完，白板写不下了。第四轮： lc 417 没刷过。给了个 dfs的解法，跟bfs相同复杂度。
http://massivealgorithms.blogspot.com/2016/10/leetcode-416-pacific-atlantic-water-flow.html

第五轮： lc 308 没刷过。先说了unmutable 的方法。然后给了个o（n）的amortized 方法。然后给了个o（logn）update， o（n）query 的递归方法。让写了简单的伪码，没时间了。面完以后发现稍微改下就是both o(logn ^2) 的方法。
http://massivealgorithms.blogspot.com/2015/11/leetcode-308-range-sum-query-2d-mutable.html

http://www.1point3acres.com/bbs/thread-210141-1-1.html
1. LC308; max holiday
2. 有向图找环3. 验证矩阵按对角线对称，follow up是矩阵特别大的时候怎么验证，连一行或者一列数据都放不下的情况下4. LC289 加一些空间放不下的follow up - game of life
5. LC298 加一些空间放不下的follow up
http://massivealgorithms.blogspot.com/2015/10/leetcode-298-binary-tree-longest.html

http://www.1point3acres.com/bbs/thread-158678-1-1.html
第一个是infrastructure组的小哥，问了我java和c++区别然后看我简历问我compiler做到什么地步
一轮问的问题是，在网络中传输的一堆字符，找一个最长的包含M个distinct字符的子串
我做了一堆的assumptions然后简化成了leetcode原题敲了出来
LeetCode 340 - Longest Substring with At Most K Distinct Characters

小哥接着跟我讨论如果输入是characters不是strings，以及如果最长子串没办法被存起来怎么办
我说既然那样就保存hashmap和对应顺序就好了
其实我真觉得小哥会给我negative feedback没想到还给我了positive

记录第几个飘过的字符是范围的开始和结束，如果最大子串太大没法记录就再过一遍这个流

对的hm，重复没考虑，我的做法的结果肯定是最后出现的那个
懂了，是一边记录，一边用一个StringBuilder,当不一样的字符数目>M时，就按照StringBuilder上面的字符顺序，去Map里找并删除，直至Map中不含这个字符，对嘛？
还有一个trick,面试官会问你时间复杂度怎么证明它是线性的，因为这个维护窗口是两层嵌套循环，不过实际确实是线性时间复杂度

二面是个三姐特别和善做ads的问了我简历上recommendation system是怎么做的
我稍微说了一下
编程题是1一个字符串可以shuffle和delete字符，找一个longest palindrome2输出所有可能的longest palindrome我2没真写，但是说了backtracking的思路带着三姐模拟了一遍

我是弄了个hashmap记录字符-频次，奇数频次的只允许在中间，只允许出现一次，其他奇数频次的都减去1频次变成偶数频次，偶数的则对半插在字符串开头和结尾，java记得用stringbuilder

http://www.1point3acres.com/bbs/thread-206762-1-1.html
http://massivealgorithms.blogspot.com/2015/10/leetcodegame-of-life.html
只有一道题，关灯开灯的问题，给一个n*n 2d array，表示light on/off，求下一个state的状态，规则是8个neighbour里，有两个on的不变，有三个on的变成on，其他变成off。。follow up：
1. after k steps，求状态
2. n is very large
3. k is very large
要求自己选数据结构写方程，我就用的vector。。除了遍历没想出别的办法。。k很大的时候可以用hashmap纪录找pattern。。n很大的时候说了bitmap，然后又说n有million级怎么办
依稀记得开关灯的题有些数学方法可以提高效率

http://www.1point3acres.com/bbs/thread-205549-1-1.html
- dfs+trie
有一些string 比如 “ata”,“tat”,“ata”他们仨可以组成一个square

ata
tat
ata

让第1，2，3行和第1，2，3列分别相等。
上面的例子是长度为3的，这样的square可以由n个长度为n的string组成。
Input是很多string，长度不等（要自己问出来）。然后返回所有的square
Output形式比如vector<vector<string>>
我想了没到30秒面试官就不耐烦的提示 trie了虽然他没说这个词需要一个function返回某prefix某长度的所有string

忘了说trie我刚要提笔写他让我定义每个function头就行了

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

http://www.1point3acres.com/bbs/thread-209578-1-1.html
第一题给你个数相邻的两个digit均值round up求最大值。暴力解决。第二题一个字符串找最长路径leetcode388。用stack解决

话说第一题是不是从左到右找第一个比右边相邻的数字小的替换掉就行了？全都不是的话就直接去掉最后一位。
我的是两个相邻的数字替换成avgerage round up。。这个题有变形
是呀，我说的也是这个意思，比如623354就把2,3换成3，因为从左到右第一个小于右边的数就是2。如果是654320这种递减或者不增的，就直接换掉最后两位变成65431。应该算是贪心吧，不知道对不对？
嗯哼全都试一下就好。最后O(n)
是这道题不看，题目要求里明确写了，保证正确性即可~
http://www.1point3acres.com/bbs/thread-202132-1-1.html
这题是简化债务关系，就是给一堆人的账面交易记录，求最少交易次数使得账面平衡。
http://massivealgorithms.blogspot.com/2016/11/leetcode-465-optimal-account-balancing.html

这题一般有两个思路，一个是把一个人当做中转站，所有人都跟他交易；第二个思路是把所有人的待结款项算出来，然后排序，用two pointer做。

然而这两个方法都不能保证所有情况下交易次数最少，这题实际上是一个NPC问题，可以归结为，在当前集合待结款项正数和负数两个集合中，找到两个不相交的最小子集，使得二者刚好能够结余。不停地寻找这样的子集，删掉，就能够得到最优。然而 subset sum 是NPC，我没想到这一层，结果跪了。

另外大家平时在做简单题的时候能够注意一下常数优化，比如减少不必要地循环次数，以及内外层循环计算等问题，我面试的时候这个被问了很多次。

假设有A, B, C D, E五个人，债务情况是
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

这时候C不用参与支付，省下A, B, D, E需要找到最少的支付次数来达到这个状态。最简单的情况是 A ->B -> D -> E (6, 9, 7)，需要3次支付。但是如果最终的状态是
A -3,
B -2,
C, 0
D, 2
E, 3
那么只需要两次支付就能达到这个状态A -> E (3), B -> D (2)。

类似的，我们可以把所有结余为负的人看成一个集合，例如{A, B}，同样的，所有结余为正的人看成一个集合{D, E}。对于正的集合，假设我们能找的一个划分，使得划分后的每一个小集合都能对应到负的集合的一个划分中的一个小集合，那么就能减少需要支付的次数。那么此题就转为求两个集合的最大数量的划分，使得划分中的所有子集都能找到另一个集合的划分里的一个子集。

例如集合{A, B}可以划分为{{A}, {B}}。如果能分别对应到{D, E}到划分{{D},{E}}中的两个子集，即A + E = 0 并且B + D = 0，那总的支付次数会少一次。到这里应该就是楼主说的NPC问题了。
回到这道题，我能想到的一个搜索方法的方式是，对于正负两个集合，找到所有的子集的和，然后在这些和中寻找相等的一对子集。比如我们找到A+E = 0和B＋D ＝ 0。那么就可以递归的去求最多的划分次数。这里涉及到重复计算的子问题，可能自底向上更好解决。不知道有没有高手能想出更好的解法

这题的做法就是，算清各自应得/应付账款之后，分为正数负数两个集合，0扔掉，然后在正数里面找最小的子集，负数里面找另一个子集，使得存在两个不等于全集的子集，他们的和是相反数，然后合并这两个集合，这样一定是最优的。而找子集的过程就是subset sum，目前看只能穷举，要是你多项式时间做出来，那就图灵奖了。

http://www.1point3acres.com/bbs/thread-208931-1-1.html
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可以用无限次。直接完全背包秒杀了。
2. 给你1,000,000个数，求有多少个pair的和小于给定的数K, 直接排序加二分做的。follow up: 找三个数怎么办，我没多想就说对于排序后对每个数做一遍前面的问题以为没有了，说完test case还有15分钟的样子，结果就来第三题了：
3. 给你两个string s和t, 问s是否能删除小于N个字符，使得结果是t的一个子串，比如 "book, aook", N = 1, return true;看完直接懵了，因为最近做two points太多了，就朝那个方向想，一直想去用O(N)，最后他说不行，我也发现不行，然后45分钟一到，直接就说拜拜了。
第三个题真的太紧张了，下来一想就是一个二维的dp也不难。

def solve(s,t):-google 1point3acres
ls = len(s)
lt = len(t)
dp = [[ls for j in xrange(lt+1)] for i in xrange(ls+1)]
#max value is ls as empty always be substring of other strings.鐣欏璁哄潧-涓€浜
for i in xrange(ls+1):
dp[i][0] = i # when t is empty, we need make s empty too
for j in xrange(lt+1):
dp[0][j] = 0 #when s is empty, s is substring of any string
for i in xrange(ls):
for j in xrange(lt):
if s[i] == t[j]:
dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j])
else:.鏈枃鍘熷垱鑷�1point3acres璁哄潧
dp[i+1][j+1] = min(dp[i+1][j+1],dp[i][j+1]+1)
ans = ls. From 1point 3acres bbs
for x in dp[ls]:
ans = min(ans,x)
return ans
.鏈枃鍘熷垱鑷�1point3acres璁哄潧
print solve('okok','okok')
print solve('book','aooksbooks')

比如  dp[1][1] 的值按照楼主的逻辑应该得0吧但如果 s = "book" t = "aook" 从b 到 a 应该删除1吧

补充内容 (2016-11-8 01:26):
我的是
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

我明白你的意思了，但当 s != t[j] 的时候，这个i不一定要删除吧？有一种情况是 i 匹配[0 : j -1]里面的字符，所以 d （i+1）(j+1) = 最小的 d(i)(j+1)+1, d(i+1)(j)。比如 s= boo t = aook 当 i= 最后一个o j 等于k的时候这时候o 就没必要删除吧？

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情况就是线性的.
我感觉好多题目dp都是实在没有解法的时候才考虑的

只不过我建议楼主在没把握的情况下，不要上来就奔着最优解去，像你说的，一卡住就很容易紧张，面试官也不了解你的思路也只能在旁边干看着，最后他就完全有理由给你个negtive feedback. 另外我想了一下第三题，跟LC的edit distance有点类似

http://www.1point3acres.com/bbs/thread-206926-1-1.html
第一轮：简化版的LC358，rearrange string使得相邻字符不相同，输出一个即可，用heap＋greedy写完；还剩十五分钟，口述了LC340，以及follow up：string太长内存装不下怎么办
记录每个字符最后出现的index
http://massivealgorithms.blogspot.com/2016/04/leetcode-340-longest-substring-with-at.html
第二轮：1. 给一个排好序的数组[a0, a1, .., an]，固定的值C，和可变的T，对数组求和，规则是ai = ai if ai < T else T，问能让总和小于C的最大T是多少，用二分做了；
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
不用扫一遍，直接二分可以到logn
求和是o（n）, 在二分阶段只要logn就能求出结果了

2. 两堆个数相等的石子，给了部分石子之间的的重量关系，问能不能判断第一堆石子比第二堆重。用暴力的backtracking做了，做完时间到了，面试官说还有更好的算法，回去查了下是类似二部图的完美匹配问题
第一堆[A, B, C] 第二堆[D, E, F] 如果我知道A>F B>E C>D, 那么可以断定第一堆比第二堆重；如果我知道A>D, E>B, C>F,那么就不能断定；题目输入是部分A, B, C, D, E, F之间的关系，问能不能断定第一堆比第二堆重
看看图论里二部图的部分吧，backtracking就是穷举，很容易想到的，当然这类问题是有专门的算法的

第三轮：找到数组里长度为3的subsequence，输出任意一个即可；followup是长度为k，没写代码只是讨论了一下
o(n) 做法类似lc334
我指k的情况下应该要nlogk

第三轮subsequence要求increasing。。手滑打漏了

第四轮：先问了hash的基本知识，然后面筋题，给一个双链表1<>2<>3<>4<>5, 输入是几个node，比如1，2，5，问有几个connected component。用了union find。其实这题用LC128的hashset方法即可，并不需要搞那么复杂，虽然复杂度基本一样。

http://www.1point3acres.com/bbs/thread-210961-1-1.html
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)的空间优化。
4.Domino Game（没听说过这个游戏，规则基本靠问），Domino牌定义为一个只有两个int的array，按d(i)[0] == d(i-1)[1] && d(i)[1] == d(i+1)[0]的顺序连起来，先是很笼统的说去实现这个game的add和length，写了个add(Domino d)之后又问add first怎么办，实现了add first之后又问add中间怎么办，总之最后就是各种followup，最后还要把add变成O(1)（本来用的Collection List这样就不能用了，后来想想面试官中间说了一嘴说他不是很熟悉java，所以可能还是希望能看到自己写的数据结构吧）

这次面试前recruiter就说了只考算法和datastruture不考system design,然后题目虽然不难但是感觉沟通的磕磕绊绊的还是希望能送hc，而且感谢之前地里的面经压到了一道原题（面的时候心里千恩万谢地里的前辈），所以刚面就来汇报了，而且听说面试官其实都只考一道题（一般没跟之前的人重复就不换题），希望大家也能好运

哦哦题目给了一个5-letter word的dictionary(自己选择用什么data structure表示我用了Set),然后要最少次数的调用makeGuess方法来得到那个Picker选择的String。我最后用的HashMap存之前的String-int pair然后iterate dictionary来找，每个iteration里面跟之前的String算一下相同的char个数，和map里的value不同就略去，最后worst case 还是O(n^2),只是recruiter也没问优化了。

如果第一次guess abcde,返回1,然后找到第二个单词axyzq,也是返回1,这种情况该怎么办呢？有可能a是属于被猜的单词的，也有可能不是啊。如果axyzq返回0的话至少能证明a一定不是被猜的单词。
这样就调用makeguess并且把结果存在map里啊～
应该…可以？我大概问了下assumption就跟他说了iterate dictionary的方法，面试官说那你implement吧…
最后好像不要排列，从字典里找一个由相同字母组成的单词。
加上开始面试官强调了两次是希望找到调用makeguess最少的方法，就没有考虑这种方法了

不是问两个node是否有共同parent，而是判断这两个node是否直接相连（source是否能通过向下找到target)现在想想当时好像强行把问题简化了，面试官开始只说判断两个是否connect，我问是指用从source开始找children，找到target就可以了吗，面试官说是…就

嗯嗯～他的意思应该就是让我通过改一下我的node的structure来实现优化吧…最后在他的提示下我说那我直接把parentnode存在node里好了他让重新说了下找的过程就没followup了…

http://www.1point3acres.com/bbs/thread-193424-1-1.html
面试官是做云文档存取的，两个题全是情景问题。
1. 假设一个文件从storage的提取有0.1的可能0.1秒完成，0.4的可能1秒完成，问如果当用户提取文件的时候是随机从三份备份中选择一份，问消耗时间的概率分布是怎样的，而且要用r写出来。
一直以为会是类似投硬币的问题，于是跟面试官吵吵了十分钟才弄清这是个原始概型是怎么样的，大概是我理解能力太差。

2.云存储每天要存入大量的文件，我们有很多硬盘，希望存储文件的数量能够尽量均匀。问需要什么statistic能知道我们的算法确实work了--大概就是文件数足够均匀
楼主答了随机抽取一部分硬盘计算新文件数的分布75%quantile，中位数之类的，看如果两者差的不多就是算法work了，感觉这一问姑且是答对了
然后，面试官手画了一个图，大概是这样
   |
1500|^^^^^^^^^^^^ 95%quant
   |
  900|^^^^^^^^^^^^median
   |
      —————————— t
面试官问有这样一个图是否能知道算法是否work了，我说我还需要看standard error, 否则不能确定，后来想想左面的1500和900差的实在很多，这个图基本可以说明算法出了问题。这两个题目说完时间就到了于是就结束了。

http://www.1point3acres.com/bbs/thread-202685-1-1.html
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

我说brute force肯定行，他说你不用写这个太简单了。接下来我就想，那异或XOR吗，你看最左边的位呗，然后就说你开32*N的数组，记他们BIT的信息。
接下来就说根据第一位分两大类呗，0一类，1一类。就问我那后面31位怎么办？
我想法是根据第二位分类，以此类推，最后做32个候选的union。结果想想不对，intersection也不对。

最后我不知道怎么办了，服输了，问他，他说你在31位里面已经分好的0的大类里面，继续分1 分0，recursively做，可是我想了想那也不能出一个数啊，是两个数配对的啊
期间我也想是不是3维DP做。也没说，一直在这条路上走，也不对，我也不知道了。
交流吧，我感觉题都不会，也没什么交流了。
lz到最后一行代码都没写，绝逼是没戏了。

http://www.1point3acres.com/bbs/thread-210564-1-1.html
直接问了我一连串关于abstract，interface 的问题，磕磕绊绊答上来了。
然后就给题，具体题目记不清了，反正就是要用abstract class。题目一出来我就惊呆了，abstract怎么拼我都快忘了居然还让我写代码？小哥给了很多hint，但最后还是没写出来。
这个时候就剩下十分钟了，问我一个很大的文件该怎么去重，我说用hash呗，小哥说可是这文件很大很大呀，我又蒙了，心想难道这是不让我用hash？于是开始漫无边际的扯其他的，后来小哥hint了一下还是可以用hash的，遂想到可以只保存key。但是完全没时间写代码了

一个文件有很多行，我们需要去掉里面重复的行，然后把没有重复行的文件打印出来
example：
input:
aaa
bsdf
fas
aaa
aaa
bsdf
fas

文件很大的意思就是极端情况下这个文件可能有非常多行，并且里面没有重复的（或者只有几个重复的）

我觉得如果特别大的话用trie比hash会省空间吧
有大神说用bloom filter
http://www.1point3acres.com/bbs/thread-210985-1-1.html
1. 给一个2d matrix，顺时针方向从外往里trace一遍里面的element。举个例子
1  2 3  4
5  6 7  8
9 10 11 12
那 return的就是
1 2 3 4 8 12 11 10 9 5 6 7
注意这个matrix不一定是square martirx
面试官白人小哥超级nice，我刚开始没想出来一步步引导我来着

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

附带之前software engineer 电面的题：
给一个BST 的node，写一个next function，return它的下一个node（就是比它大一点的那个）
http://www.1point3acres.com/bbs/thread-210955-1-1.html
1. check two binary tree are similar

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

复制代码

即root要相等, left/right可以交换. "交换"可以进行多次.
首先想到的就是recursion遍历, 相等则继续比较, 不相等就交换着比较.

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

复制代码

对面一直在纠结空指针怎么办, 然后我说前两个if就能排除空指针的可能性, 然后他举了几个例子, 觉得没问题, 就问了复杂度. 这里我先说复杂度是O(2*N), 然后感觉不对, 毕竟涉及到recursion, 赶紧改口说应该是O(N^2). 对方说不对, 说可以用数学的方法证明, 我说哦, 那就是 master theorem, 他说对, 不过也没继续问.
感觉按照代码应该是 T(N)=4T(N/2) + O(1) master theory 或者换算应该是 O（N^2）复杂度？

这时已经过去33分钟了, 他说那我们问一个简单题吧, 俩list, 交叉打印.
我说如果只有2个, 可以two pointer, 如果有多个可以用queue装多个, 他说两个就好. 然后5分钟写完了.
这时已经过去了40分钟, 我问了俩问题, 然后就结束了. 感觉第一题做得不好, 估计要跪, 求onsite.

http://www.1point3acres.com/bbs/thread-202732-1-1.html

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

2. 中国年轻美眉
实现一个iterator, input 是一个array{3, 8, 0, 12, 2, 9}, 希望输出是 {8, 8, 8, 9, 9}, 也就是eventh number代表词频， oddth number 代表词， {3, 8, 12, 0, 2, 9}，就是3个8， 0个12， 2个9. 和美眉商量了输入不用array, 用个List<Integer> 简单好多。
如何测试。

public class P000_FunnyIterator implements Iterable<Integer> {
List<Integer> data;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
P000_FunnyIterator(int[] input) {
if (input == null || (input.length & 1) == 1)
throw new IllegalArgumentException();
int n = input.length;
-google 1point3acres
this.data = new ArrayList<>();
for (int i = 0; i < n; i += 2) {
for (int c = 0; c < input[i]; c++)
this.data.add(input[i + 1]);
}
}
@Override
public Iterator<Integer> iterator() {
return data.iterator();
}
}

不用额外空间的话也可以

public class P000_FunnyIterator implements Iterator<Integer> {
int[] data;
int curPos = 0;
int curCount = 0;
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
P000_FunnyIterator(int[] input) {
if (input == null || (input.length & 1) == 1)
throw new IllegalArgumentException();
for (int i = 0; i < input.length; i += 2)
if (input[i] < 0)
throw new IllegalArgumentException();. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
this.data = input;. more info on 1point3acres.com
}
. visit 1point3acres.com for more.
@Override
public boolean hasNext() {
while (curPos < data.length && data[curPos] == 0)
curPos += 2;
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
return curPos < data.length;
}
@Override
public Integer next() {
int ans = data[curPos + 1];
curCount += 1;
if (curCount == data[curPos]) {
curPos += 2;
curCount = 0;
}
return ans;
}.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
@Override
public void remove() {
throw new UnsupportedOperationException();
}

3. 白人小伙
Number of island II
如何测试。

4. 印度老汉。
给一个string, 找出lexical order 最小的， size==k的， subsequence, (note, not substring)
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);
4. find the one with smallest lexical order.

我就是说了个大概.
pop的时候需要看后面还剩几个元素了
元素不够的时候就含泪不pop了，直接push进去
比如你说的例子，其实是
f->e->d->c->cb->cba
5. 印度小伙，同时参看上的图
最大假期问题，之前面经看到过这个，但是没有具体的描述，就放过了。结果就命背的被考到的。。。。。。。。。。我来详细描述下
input:
a. 有n个城市，每个城市之间有飞行时间，
b. 给个飞行时间，
c. 给个vacation array, 代表每个城市每周的假期
d. 从第一个城市开始
意思就是每个周你可以呆在一个城市，然后享受那个城市的假期。
还有个限制，就是城市与城市之间的飞行时间不能超过给定的飞行时间
求x weeks 你能享受到的最大假期总和你自己设计输入的数据结构

描述起来真他母亲的繁琐，怪不得没看到详细的说明。
我的大概想法：
1. 去掉那些飞行时间超过给定飞行时间的边。
2. 用adjancey list做的，
3. 然后bfs, 暴力求解。 4. 没写完。。。。。。

如图所示，最大的应该
week1, A, sum=2;
week2, B/C, sum=sum+1;
week3, 回到A, sum+=3
total sum =6

最后两轮都没回答好，可以说写出来80%。估计是挂了。发现碰到没做过的题，容易慌，容易去套已经做过的题。。。，然后思维混乱，就会开始朝令夕改。还是应该不去套已经做过的题，就从个BF 的方法开始。我都是想搞个优化，结果最后又回到最初的暴力。。。。，郁闷。。。。。。。。。

4贪心就可以了
4就是把输出string当个栈，如果当前进来的字母比栈顶的小，就把栈顶的扔掉，小的放进去
比如pineapple
p->i->in->ie->a->ap->app->al->ale
擦，这个不就是那个https://leetcode.com/problems/create-maximum-number/，
其实是新出的remove k digits

5可以dp的

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

5就是算前x周，假设你最后一周在城市c的话，最多的假期数。
http://www.1point3acres.com/bbs/thread-211045-1-1.html
第一轮看脸感觉是个韩国小哥，一路不怎么跟我沟通这轮面的很吃力题也是四轮里面我感觉最难的

这题分成三个部分都是基于一个integer的data stream
第一题是问说给定一个integer n有没有曾经在data stream里面出现过
这里我就用个HashMap纪录曾经出现过的integer然后有k进来的时候就去看有没有在map里

第二题是同样的input n但是只考虑过去的k个element里面有没有出现n

这里我是用了个Queue去纪录过去的k个元素，当Queue的长度到了k之后就pop掉第一个的元素，同时如果是有曾经出现过的元素在Queue里面出现了还要把它挪到Queue的后头，找到Queue的方是就是用，感觉有点像是LRU的概念，但是我没有自己implement doublely linked list这个复杂度应该是O(n)了
因为当有新的element进来的时候，透过Map就算可以找到该element在Queue当中的node还是没办法直接O(1) remove的

第三小问才是最难的，同样的input n，要找过去k个element里面存不存在integer i st.
|n - i| <= v
v等于是这个题目的第三个input
想像成
boolean checkExist(int n, int k, int v)

我当时想的办法是原先用来记载元素的HashMap改成用TreeMap，这样就可以直接用TreeMap去ceiling跟flooring去看一个range里面有没有存在node。

我感觉面试官非常不喜欢我的解法，从第二小题就感觉走错方向了。毕竟多维持一个queue还要回头维持map就有很多要细节感觉我都没有写好。

第二轮大概是一个越南大马或泰国的妹子
题目是design一个class可以判断一个围棋的棋子是不是被围住了经过一番讨论之后决定就是implement一个function在假定棋盘已经摆放很多旗子的情况下，给定任何一个位置跟那个位置的颜色（黑子或白子）判断一下那个棋是不是被包围了这题其实就是个DFS，但是就是要同时考虑input可能是两种颜色，然后还有可能是空格，还有边界。整体来讲，我思路大概是对的，但是code写得很乱，觉得这轮应该也没办法拿到strong positive。

第三轮是一个在Map组工作很久的美国人
一上来就先问了我整整大概20分钟的behavioral。其中一个比较有趣的问题是，他说如果他现在打电话给我intern的manager，他会如何形容我。大家参考一下哈哈

题目很简单
就说如果给你一个字符串 char[]
"This is a dog"
就是很多个中间有至少一个以上的空格
类似这样要把它变成
"This is a dog "
就是一个two pointer的问题去解就好了，一开始想的有点复杂，稍微花多了一点时间，然后写出来的时候时间差不多就用完了。但是面试官感觉还是挺满意的，原本期待这轮可以拿个Strong positive，但是或许是题目太简单了吧...

基本上就是一个
Number of Island ||
但是是要设计整个class，能够支持快速地知道当下有几个island，然后还可以随意在任何一个点添加island。
就这个小变动，让我有点乱了方向，竟然决定constructor跟addIsland()写成两个分开的function，都做了差不多的事，最后基本也没时间写到addIsland()。因为在constructor的时候可以只需要看他的上面跟左边就好了，因为之后走到下一个的时候他会回来看左边跟上面。为了这件事情我还花了很多时间说服那个小哥。然后当我在想着要如何实践Union and find纪录parent的那个array的时后，小哥还出来打断我，问说我在干嘛，叫我直接用Union(X, Y) Find(X)这种抽象的interface写一下就好了。把抽象的code塞进真正的java code就变得好混乱，最后又是留了整个白板的烂code。哎

狗家的bar还是好高，光解决问题是没用的，code要快要漂亮才行

补充内容 (2016-11-17 13:03):
第二輪打出來怎麼格式跑掉了
"This is a dog"
就是很多個中間有至少一個以上的空格
類似這樣要把它變成
"This is a dog "
第二轮完全围住定义是啥围住的中间还有空格算吗把棋围到一个角落算吗？
围棋那题被围住的范围里面还有空格的的话不算围住。另外，被逼到墙角也算是被另外一个颜色包围。

第一轮第二题 k个element要求distinct吗？不管怎么样直接queue加hashmap 每次把queue的头pop掉然后相应在表里的也pop掉不就行吗重复的push的时候不push 根据k distinct与否决定count加不加一
k element那题不要求distinct的。
你这么一说我才想起来我当时好像就是在Map里面存count的。只有count减少到0的时候我才把他从Map里面pop掉。所以我的作法应该是没有什么问题，不用考虑更新queue的情况，每次有新的item进来只要把queue的头pop掉，然后去hashmap里面把它对应的count--，如果等于0从map里面remove掉。
第三小题虽然改成TreeMap但是我也是这么做的。
http://www.1point3acres.com/bbs/thread-203811-1-1.html
今年狗家二进宫，吸取了去年的经验教训今年早早就开始准备。楼主非牛人不过去年算刷过一遍题，从今年四月开始备战，上培训班提高算法和系统设计的能力；重刷lc和面经，到九月刷了190左右高频面经和两遍lc；请了模拟面试老师专门模拟狗家onsite；临近onsite请了两周假在家专门强化复习。和版上其他在职同学一样不得不说在职刷题真是很累，可惜结果还是悲剧心里有点失落

（1）白人小哥1，上来问会不会多线程，咱们写一个多线程的题吧。楼主有点懵这个真没有专门准备不过好在好在题目不难，
就是设计一个producer consumer原理的数据结构，有很多个producer不停地生产带开始时间戳的task，只有一个task executor按照task的时间戳顺序执行task，设计这两个thead class。关键就是要在consumer里面设计个数据结构可以按照时间戳顺序排列接收到的task并一一执行，楼主写了个PriorityQueue并加上了BlockingQueue的特性，用wait, notify实现。写完之后小哥提出了几点，中间要避免busy waiting什么的，比如现在队里的所有task开始执行时间都小于当前系统时间，你的consumer该怎么做，我想了想也就只能sleep了这段时间差再继续。这轮答的中规中矩吧。
- delay queue
恩后来发现可以直接用PriorityBlockingQueue,按时间顺序排序。要注意有可能来的新task可能在未来，所以每次从队列取得时候，consumer先peek一下，如果是未来的task就sleep时间差，producer放新任务的时候也是先peek一下，如果发现peek到的任务是未来任务，自己现在要放的任务比这个未来任务的时间靠前，就打断consumer的sleep。

（2）白人小哥2，LC原题361，楼主很开心的绘声绘色的默出了代码。接下来follow up是如果这个地图很大，很多点都是空的没东西，你怎么优化你的算法。楼主想了下稀疏矩阵乘法那道题就说用一个二维矩阵矩阵来记录每一行中，各个位置中不为0的列数和其对应的值，然后遍历这个新矩阵
http://massivealgorithms.blogspot.com/2016/06/leetcode-361-bomb-enemy.html
http://massivealgorithms.blogspot.com/2015/11/leetcode-311-sparse-matrix.html

（3）白人小哥3和shadow的国人小哥1，也是一个很简单的design题，简化出来就是输入给你很多task和值，一个task可能对应多个值。然后给定一个task和值的组合，找出第一个比这个输入值小的已存值是多少。这题就是存好map后对给定task所有值简单的二分找, 这里还专门用了二分找第一个大/小的模板保证不丢值，小哥看完很开心，问了下什么时候sort，就说看put调用的多还是get调用的多，在调用的少的那个里面sort
（4）白人小哥4，LC原题317，只不过房子变成了职员和咖啡机，找到一个摆放咖啡机的地方和所有职员距离和最短，问好了限制条件比如员工可不可以跨过员工什么的开写

（5）国人小哥5，感觉这轮答的最不好，题目很简单判断所有反对角线上的数相等，楼主这时脑子有点僵而且看到国人心里有点放松竟然写了半天涂改了好几次。Follow up是如果矩阵很大没法一次存入内存怎么办，楼主弱了开始也没想到，提示后想到就是不要一次判断一整条对角线，两行两行的读矩阵再斜着判断这一小段的对角线，看还有时间迅速写出了代码。
恩就是简单的一个个判断，就是考怎么取出来反对角线而已

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

http://www.1point3acres.com/bbs/thread-210949-1-1.html
. LC 226 invert binary tree
然后问各种test case，说了一堆不是他想要的，然后他问我如果有cycle怎么办。。。如果有cycle我的代码能work吗，我是用recursion写的，当时一下子懵了，还说可能可以吧。。。。小哥说是不行的，然后和我解释。
接着就是写个函数判断binary tree里面有没有cycle, 我用visit set 做的
2. LC91 decode ways用DP写好后让优化成O(1) space的，分析复杂度。
3. decode ways的follow up吧，让输出所有的数字，我是用backtracking做的，然后让分析复杂度
http://www.1point3acres.com/bbs/thread-210652-1-1.html
第一轮：Find common element within 2 arrays. follows: 1.如果一个很大一个比较小怎么办（binery serach in larger array），如果larger array can not fit in mem?(truncate into files and binery search in the target file), what if larger array is even larger that on machine can not store? (master - slave, and parallel searching in each slave machine), what if both arrays are very large?

第二轮：lc 394, follow, how to encode, ex abcabcd => 3[abc]d, follow up没答完，这轮搞不好要差评了。
第二轮follow up之前地里有同学报过，当时没仔细琢磨，不会还是不会，这次吃了大亏了。小伙伴们要好好利用面经呀。

第三轮：一个binery search tree，删除某个layer的所有node之后重新construct一个新的BST, 要求新tree是complete的。我的做法是1.先tree level traversal 原来的tree，删掉一层之后所有node合到一个array里面sort。2. 创建一个新的complete tree with x nodes, where x == length of the previous array in step1. 3。in order traverse 新tree，把第一步得到的array值填进去。面试官表示满意

第四轮：如何创建迷宫，需要保证只有一条路径到出口并且所有tile都能reach. 面试官比较nice，每当想偏了的时候都给了关键提示，最后顺利做出。
大致方法是从起点开始dfs，keep一个visited matrix，下一步上下左右的顺序是随机的但是保证上下左右都走一遍。每走一步就把走过的路径加入到一个path dictionary里面，pathDic = {fromTile : toTile} 任何不在这个dict里面的两个tile不能走过（中间🈶墙）,问了个follow up问题是n*n的迷宫墙的数量是多少(2*n*(n-1) - (n - 1))，他只准备这一题，做完后还有15分钟，
前面有个type，迷宫墙总数是(2*n*(n-1) - (n*n - 1))

从起点开始DFS，正常的DFS方向是固定，这里DFS方向顺序需要随机，然后每个格子只走到一次，走过就记录在visited matrix里面以后再也不能visit这个格子。所有DFS走过的路径就是通路，没有走过的路径默认是墙。可以用一个hashmap来存所有路径，我用的形式shi是 {(1,2): [(2,2), (1,3)]} 表示(1,2) 可以走到(2,2), (1,3)

看LZ的DFS意思相当于是找所有不自交的从起点到终点的路径（不在路径上的就自动设计为墙）。如果是这样的话，这种迷宫只能保证存在一条路径到出口并且所有tile都能reach，没法保证路径唯一性啊。
例如3X3迷宫从(0,0)走到(2,0)的两个不自交路径：
(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)
这样3X3网格无任何墙的迷宫本不具有路径唯一性的，但却有不自交路径经过所有节点。
follow up：n*n的迷宫墙的数量是多少(2*n*(n-1) - (n - 1)) 这个不应该等于n*n - path length吗？还是我想完全偏离了？

面试官问的是n*n的迷宫里面有多少面墙，有多少个通路（可以看做两个格子之间有个门）
我一般认为墙或空格都占据一个格子。。。呵呵
那么这个就是一笔画问题了？从起点到终点无重复地走遍N*N个格子(Tiles)有多少走法？这样顺序不同就代表打穿的墙是不一样的了。那我觉得就是我在12层的code Line 2中加上只有当前路径长度ps.length()==n*n-1（不算终点）时再加到结果中去吧。. 鍥磋鎴戜滑@1point 3 acres
但好像也有无解的情况吧，2X2迷宫，起点(0,0) 终点(1,1). 还是我又想偏了，呵呵。。。

那么所有墙总数=2N*(N-1)，路径长度必然N*N就打穿N*N-1面墙，所以还剩2N*(N-1)-(N*N-1) = (N-1)^2面墙

又做了一道比较简单的题，基本上属于浪费一下垃圾时间

第五轮：问题是有个data feed实时收到[timestamp, value]， ex：[1, 5.23], [2, 6.32] ... 不过有可能会收到之前时间的value update.比如又来个[1, 5.77], 这时timestamp 1的值就从5.23 变成5.77. 问题是如何keep track of the largest value so far. 我的方法是keep 一个合理大小的heap保存前n大的value，问了一些问题关于如何选择heap size大小之类的，都属于言之有理即可的

如果先来了n个feed (1,2),(2,2)...(n,2),这时候你的heap有n个2，然后来了(n+1, 1.5)，这时候不会被放入堆中，之后又来了n个更新的feed(1,1),(2,1)..(n,1)的话，你的heap就只剩下n个1了，这时候max value就不对了
你说得对，面试的时候跟跟面试官讨论如何选择heap size，如果update频率比较高heap就要选的大一些，当然也可以重新扫一遍所有结果重新生成heap
为了时间效率，是不是应该再存一个hashMap mapping time->heap iterator来保证O(1)时间查找heap中的某个元素? 我不熟悉Java请见谅。
. From 1point 3acres bbs
若是C++的话（C++ priority_queue不支持iterator和remove）,我用set<pair<int,double>>来存pair(time, value) ordered by value（insert时间也是O(logN)），再用unordered_map<int, set<pair<int,double>>::iterator>来指向set中的位置。这样当收到一个以前的pair(time, value)时才能O(1)时间将旧的value从set中删除，再将新的加入。

至于这个heap size，若要即时询问当前最大值的话感觉必须是O(N)空间啊。我的假设是这个feed就是个stream, 每次只能读取一个，若当前不存的话以后就再也找不回来了。不知面试时有什么假定？

http://www.1point3acres.com/bbs/thread-211038-1-1.html
309 digits,相当于 2^1024

The fuel control mechanisms have three operations:

1) Add one fuel pellet
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

EDIT:这个最后使用java 里面的BigInteger,不够时间也不确定python怎么做类似的事
情,一开始用BFS给出了答案,后来遇到big integer这个问题,最后用bit operation来做
这道题是得用BigInteger的add, divide 函数嘛？否则直接overflow了，bit operation怎么做?还是基于BFS嘛？
http://www.1point3acres.com/bbs/thread-210962-1-1.html
第一题设计一个统计投票的系统，统计谁赢。当时有点懵拿算法题写了Hashmap什么的。面试过后回想觉得应该是让设计data structure 然后可以输出任何一个时间点得票领先的人。
第一题已知candidates的数量吗，如果数量小是不是可以用boyer-moore voting algorithm: https://discuss.leetcode.com/topic/17564/boyer-moore-majority-vote-algorithm-and-my-elaboration

第二题设计google map 以优化搜索功能，比如搜附近的cafe什么的

二轮，三姐，进来直接做题。两道lc原体，h-index 和 paint fence。
四轮，国男，具体题目忘了，用binary search做的，最后test的时候有个bug，调了一下。大家注意一下validate input的时候，不要受lc影响太深，如果MAX_VALUE什么的都是possible output怎么check，应该写个try-catch block。
五轮，白男聊research。本来最有把握的一轮，以为会是相关专业的人来讨论一下，因为之前还要了thesis abstract 和导师推荐信，没想到来的人完全不懂我做的东西。最后跟他大概讲明白了，他似乎觉得我做的东西对他们产品不太相关。我跟他解说这种统计模型很常见，可以有很多其他application，感觉他还是坚持他的第一印象。
六轮，国男，跟着一个superviser白男。这位哥哥刚进公司不久，好像第一次面试，拼了命的表现给旁边人看，题目是给一2D-matrix，找从左上travel到左下的最短路径，每次只能move到下一个row的正下以及旁边，比如从(i, j) 到 (i + 1, j - 1) 或 (i + 1, j) 或 (i + 1, j + 1)。用dp写的，然后follow-up说只能用O(n) extra space 最后没写玩。

第一轮问题还请map达人指点
我觉得面新题看思路挺好的。像FB那种原题倒是原题，要求严格bug free的感觉不make sense
嗯，我明白是要一个实时系统，input不是一个static的vector<string>，但是如果candidate pool的大小已知({"Hilary Clinton", "Donald Trump", "Gary Johnson"})就可以用voting algorithm做。要是不已知，投任何名字都可以的话，感觉hashmap已经是代表投票状态的最优的data structure了啊

可以投任何人。面试官没说啥就下一题了。但是我觉得她应该是想问怎么存这些信息，然后方便search，注意输出“任何一个时间点领先的人”，如果是搜过去的时间(１小时前)呢?
我当时和你想的差不多，当做algorithm题做了

http://www.1point3acres.com/bbs/thread-209541-1-1.html
1. 关于License Key，就是给一个字符串包含'-'，现在重新给一个K，要求 reinsert '-' 把字符串分隔成若干组每组K个字符第一组可以少但是至少有一个
2. 给一个二叉搜索树，求一个包含节点最多的子树，要求子树每个元素都在给定的区间内[A, B].
http://www.1point3acres.com/bbs/thread-144709-1-1.html
首先电面一般要简单些, 你leetcode才刷完一遍的话, 最好在这一周里多刷几道题, easy和medium为主, 不是说要背答案啥的,而是把这个手感维持下去,大脑处于勤思考的状态, 对面试帮助比较大.
最重要的是千万别紧张,就当做今天只是跟一个人一起做道题的这种心态就对了. 千万别学我,那么简单的题就是因为紧张,啥都不会了...
面试的时候遇到新题,首先肯定是不会的...但是我的话一般会重复一遍这个问题, 问他这个问题和return值我的理解对吗? 这个过程就是找思路的过程,需要你对数据结构很熟悉(这里又要强调数据结构了咳咳...),题目无非就是用相关的数据结构解决. 你要看这道题给了你什么条件, 要求得到什么, 这时候你在脑子里就过一遍所有数据结构的特性, 哪种数据结构有一样的特点能用于这道题. 心里想了一遍之后, 一定要跟他说出来你刚才的思想过程, 即使不对他也会知道你在积极思考,而不是傻等着什么也不会. g家面试官是水平最高的, 看的就是你聪不聪明基础扎不扎实, 所以多说话总没错.
等你LC刷到第四遍你就懂了~ 在一次次因为小bug而run不过case以后,很多bug自己就都能发现了... bug free我觉得基本谁都做不到,但是自己快速发现并且解决它是很关键的.
刷到第四遍开始投简历. 因为是在职找工作所以只能准备的非常充分了才开始面的. 这样我保证了每一个phone interview都有onsite, 不会错过机会. 后来发现以赛代练效果也很好, 建议先拿一两个小公司练手, 因为第一次面试还不适应,很大可能会比较糟糕

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

白人小哥.给一个Interval的class, 就是一个区间,左闭右开,比如 [1, 3) 意思是从1到3除了3的所有interger. 让我在这个class里implement一个method, 判断与另一个Interval是否有overlapping.
第二问是写一个method, 返回在Interval 1而不在Interval 2的区域.

Leetcode原题Plus One
如果现在Google要release全新版本的Chrome, 我要怎么保证这个新的Chrome全方位的work? 意思就是测试些什么,怎么测试这个新版本的Chrome,才能放心的release出去.

第一题, 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n

第二题, 知不知道binary search? 但是现在array是unsorted的可是依然看做sorted array来做binary search, 返回在array里面所有可以在这种情况下binary search出来的数.第二题漏了一个点. 除了array是unsorted以外, pivot也是随机的. 也就是说不是严格的binary search每次的pivot就是中间点, 这个binary search的pivot是在array里面每次随机给你找个点

对~ 其实用一个 boolean[]或者hashset来记录每个数是不是符合要求就行.
从左往右扫一次,记录全程最大值,如果当前值小于左侧最大值,就不符合要求
同理再从右往左扫一次,记录全程最小值,如果当前值大于右侧最小值,就不符合要求. 所以扫两次O(n)就可以了~

第二轮
经典的地里出现过的String压缩编码解码类似题, 后悔当时看到没有好好写过一遍.给一个String比如"abcdfffffffxyz", 写两个methods, encode和decode. encode就是比如"fffffff"变成"7xf",decode就是要变为原字符串.我说"ff"怎么办,他说变成"2xf"你不觉得更长了吗? 我才明白了,应该是encoded后的String要比原来的短,不然为啥要encode,的亏我问了这个问题...然后又问他,如果原String本来就是"5xt"这种结构, decode不就无法辨认了吗?他说很高兴你提出了这个问题,但是不用管它,一会再讨论,先写吧.
写完以后他就问我如果原String本来就是"5xt"这种结构,我encode应该怎么处理? 我就傻了... 因为一直觉得encode后的字符串长度一定要比原来的短,所以根本想不出来他要的解法. 说了四五种方法他都不满意, 最后给我hint说,要是有个"1xt"这样的你怎么处理? 当时脑洞大开想出来了... 其实是要变成三个"1xt"这种结构, 比如原String就是"5xq", 就encode成为"1x51xx1xq"就好了. 但是这种方法违背了encode后要变短的rule,所以我是真没想出来.....
还讨论了好多种情况, 最后一种是"1aaaaa"这种情况怎么变, 我说"1x15xa". 他说这是6个字符,能不能只用5个? 实在想不出来,这时候第三个小哥进来了,韩国哥哥就过来告诉我说,其实看做1a和aaaa两部分encode就好...

我觉得韩国哥哥的意思是, 基本rule是encode要比原来短,但是他也没明说, 有的地方也不一定要遵守这个rule... 所以具体是长是短还是要具体分析...我当时就是死守一定要变短这一点, 所以就没往别的地儿想T T
他就对我说了一句1xt怎么办? 我理解的意思是遇到原本就是"5xt"这种pattern的原String的时候, 在encode时为了能够将来decode回来, 对每一个char都进行encode. 也就是"5xt"拆成三个char分别都encode => "1x5", "1xx", "1xt"

第二轮1a和aaaa 怎么用五个字符表示呀？第三轮被rearrange k次是指用同一个映射关系吗？是不是求周期？

就变成1a4xa就好了

第三轮: 中国小哥.
第一个问题是测试的,比较简单. 测试Calculator,input就是比如俩数一个operator, 都有什么case, 怎么测,应该有什么预期结果或错误.
第二题, 一个array,rearrange成为另一个array, 现在给了这两个array, 求是怎么变化成第二个array的. 挺简单的就用了Hashmap秒了...
然后问我,那现在给你原array,也知道了是怎么变化的了,所以我们现在可以用原array求出变化后的array对吗? 但是我要run这个method好多次比如k次, 怎么最快能求出array被 rearrange了k次以后的结果? 最后我就推倒出求LCM.
面完他亲切的用中文跟我说,我是他见过面的最好的,时间复杂度最低trade off也说的好. 谢谢小哥给了我信心~么么哒~

没错就是周期~ 每个位置上,rearrange成为原始的数字的周期是不同的. 需要计算各个位置的周期, 然后求他们的LCM,就是整体rearrange成为原array的周期了. 然后再把k用这个LCM周期数取模, 就能算出最少要rearrange几次了

第四轮: 印度姐姐.
海上有一片岛, 每个岛就是一个node, 岛和岛之间有的连着有的没连着. 所有连着的岛是一个Group. 求在这片海上, 包含岛屿个数最小的group的岛的个数,和最大的group的岛的个数. 就是返回两个个数值, 肯定就是int[2]嘛. 先讨论了用什么数据结构存储, 跟她说了trade off. 然后开始写.全程想给我挑错, 不断质疑我的代码... 还好我这一轮在高压下还是写的极其顺畅, 一个bug没有出现, 对她也是笑脸相迎, 躲过一劫...
第五轮: 中国大哥. 竟然中文给我面试, 也是感动哭...
第一题, 一个二维数组代表了一个岛. 周围都是海, 岛的左侧和上侧通向Pacific, 右侧和下侧通向Atlantic. 每个数字都代表了那个位置的海拔高度. 现在下雨了, 雨只有从海拔高的地儿能流向海拔低或者一样的地儿. 返回岛上的分水岭的点, 就是在某个/某些点上, 雨水既能流进Pacific, 又能流向Atlantic. 大哥可能也知道白板写不下,让我写纸上. 足足写了4页A4纸,当然字也写的大...手都写疼了...

你的方法我觉得可以~ 两个二维矩阵空间是2n^2, 分别取结果最后取AND一共是扫三次?

第五轮第一题我的想法是建立两个二维矩阵然后DP，然后两个二维矩阵取AND就得到结果了

我的方法也是DP+DFS,只扫一次. 我用了两个HashSet分别用于存放能够流入Pacific或Atlantic的点的坐标. Pacific和Atlantic两个情况在DFS里同时做.
在DFS的时候, 先分别recursion上下左右四个方向, 如果hashset里面记录过就直接返回结果(当然如果用boolean[] visited去记录当前点有没有被扫过肯定更好, 这题元素太多, 当时时间实在不够了...). 然后判断当前点是否能流入Pacific或Atlantic, 如果能, 分别记录在Hashset里.
最后只要看有哪些点在两个HashSet里面都出现就好了.
所以每个点只用扫一次, 空间复杂度就是符合分别能够流入Pacific或Atlantic的坐标个数.

第二题, 给个Google map, 你就测吧...
http://www.1point3acres.com/bbs/thread-211203-1-1.html
给一个List<Vote>，t, k
实现一个方法，返回时间 t 以前所有投票中得票排前 k 的候选人id: List of candidateIds
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
t = 6000

return (300, 500)
heap复杂度是O(nlogk)，k-select会好一点O(n)就好了
O(N) to partition array smaller than t, bigger than t
http://www.1point3acres.com/bbs/thread-211122-1-1.html
第一轮亚裔小哥：leetcode 57 insert interval. 先是让我说如何在一堆interval（他给的叫date range）中search一个日期，我说先sort, merge然后binary search. 然后问如何insert, 我就说咋咋insert, 最后只写了insert 的代码。
第二轮白人小哥：就是那个猜词题，不过我这个是简化版，词长为5，没有duplicate letter, all English word, 还有一个dictionary保证所取的词都在这之中。可以调用一个function guess，返回猜的词和secret word有几个字母相同（只考虑字母相同，字母位置不管）。
guess这个function是自己写的，问了一下使用什么数据结构，我说map, array 或者bitmap, 感觉在考察对数据结构的理解。 follow up 如何优化，我就说你可以先猜频率高的词，因为人们倾向于选择自己熟悉的词做secret word。

第三轮白人大姐:一个有向无环图，求所有根。我在找根的时候有把路径压缩。
题目是，给一个array，一个window size, 你可以任意取任意数量的元素，要保证和最大，条件是任意两个元素的index之差必须大于等于给定的window size（感觉不应该叫window,应该叫step,就是这个地方搞得我一开始理解不了题意），且不能重复取同一个元素（index 相同）。如果一个元素都不取，和就是0。array中可以含有负数。我拿dp做的，但是面试官说他不确定是对的，我也不知道他说真的假的。。最后他说我解释的不好，搞得我觉得这一轮要黑。

总体来说不难，也就是medium的难度，匹村果然简单一些。
给大家一些建议：
一定要说话，不能沉默，第二轮的时候我就沉默，面试官提醒我一定要说出来。
要向面试官确认输入格式，有没有非法输入，否则他最后提醒你处理非法输入就不太好了。要自信，如果不能一下就给出最优解，不妨先brute force，有的面试官就等你说brute force然后再给你提示。

http://www.1point3acres.com/bbs/thread-211063-1-1.html
第一题，是一个非常友好的白人小哥，聊了5分钟他是做什么的，然后出了一道lc原题，具体就是一个数字180度旋转之后还是本身的话，就返回true，spinnable。followup是给一个int数d，找出来在0-10^d的范围内所有的spinnable的数字，返回List<Integer>。

出了一道简单dp，具体是给出来一个array, 一个window size, 对于一个数来说，以它为对称点，距离是window size的数字都不能选，用dp来求出这个数组可以得到的最大值，array中可能有负数。

第三题是一个大姐，题目是一个packaging system, 传送带上有一个个进来的object，每个object都有指定的destination, 在集装箱部分，有m个集装箱，每个集装箱最多能装k个object，每个集装箱都会有一个对应的destination, 对应一个新的object需要分配到集装箱中，每有一个集装箱被装满了，它就自动被送到指定的destination, 然后会有一个空的箱子自动的补上被送出去的箱子。有一种情况是，当m个箱子都已经装了object，即指定了对应的destination, 然后新来的object的destination和m个集装箱里面的任何一个destination都不一样，这个时候就需要把一个集装箱pop出去。

设计的时候需要在package class中加一个timestamp的变量，这样我们pop的时候就可以选择timestamp最老的那个集装箱。这个题目其实非常简单，跟leetcode design tag的题目没什么差别，但是当时脑子抽了，没有马上想出来pop的策略就是加一个时间戳。另外，这个题目我光弄明白就花了快十分钟。最后拖拖沓沓没有完全写完，觉得挺可惜的。

第四题，是给定一个输入框和对应的一个大字典，然后用户输入prefix，找出以这个prefix为开头的所有字符串，答案是trie树的实现，对于trie树，实现都是大同小异

设计TrieNode class, Trie class, Trie class的方法包括insert, startsWith, search. 面试官说了followup是，如果需要支持很多语言的话，应该如何修改这个TrieNode的设计。答案很简单，就是只需要把之前的child 26个元素的数组变成一个hashmap就可以啦

http://www.1point3acres.com/bbs/thread-211952-1-1.html
接着是一道experiment design的题，我就被问了这一道很多follow-up, 不知道是不是答得不够快所以只有一道。
google music 有推出专门给driver收听的radio或者playlist, 现在产品经理想知道这个playlist会不会导致司机收听时候开车速度变快：1.如何收集数据，收集什么样的数据，收集后如何处理，假设你能得到任何你想要的数据
2.用什么model和test来回答产品经理的问题，为什么选这个方法而不是其他的，然后根据我的回答追问了几个不同测试结果情况下怎么得出结论
3.如果现在加入年龄和性别这两组数据（我提议的数据收集方法是针对每个司机的），你用他们得出什么新的不同的结论，我说可以根据这两组数据分组来进行比较再做测试，然后问了如果年龄这一个数据有3个LEVEL 怎么做测试。

当时觉得答得不错，但第二天就被拒了，修为还是不够，感觉碰到这种很应用和开放的问题很考验基础知识的扎实程度。

http://www.1point3acres.com/bbs/thread-210244-1-1.html

先是让我介绍一个自己的一个项目，然后问我知不知道“后缀表达式”，我开始不认识那几个单词，但是后来她解释了一下，我就说“哦哦，我知道，以前本科大二的时候讲过这个，我懂”。然后她问我知不知道二叉树，我说知道啊。她又问那你知道怎么遍历它们吗？我说有三种遍历，然后解释了一下每种遍历。

然后她就在google doc上简单画了一棵二叉树，让我分别写出三种遍历的序列。我就写了一下，顺便解释是怎么来的。

然后她又问我，那如果只知道其中两个遍历序列，如何复原原来的二叉树呢？我就以先序遍历和中序遍历序列举例说，应该怎么样怎么样，blablabla...

解释完了，她说好，那你写一下实现的代码吧，我就开始写了。思路清晰，但是写的比较慢，也有点不太习惯google doc这样写代码的氛围吧。写完以后，自己大致看了一下，说我写完了，要解释一下代码吗（但是我写的时候，在关键部分都有跟她说过这是干啥的），于是她就说不用了。

最后问了我一下时间复杂度和空间复杂度。然后问我有没有问题问她，我想了想也没啥问题，就说没有，就结束了。虽然都答上来了（今天想想程序可能还有一点小bug），但是有种强烈的预感，这个三姐会挂我

http://www.1point3acres.com/bbs/thread-210958-1-1.html
1. 设计数据结构存一堆int，写存的时空复杂度，还有搜索一个数在不在的时间。。
我说了存数组遍历搜索，或者sort二分搜索，或者存hashset和bst，或者如果数是连续的，就存interval的上限和下限，或者数是有限的，类似count sort那种存对应的boolean bucket，trie倒是没想到，应该也可以吧
2. 就是dfs或bfs遍历一堆node。。。多用一个hashset存已经访问过的点。。
http://www.1point3acres.com/bbs/thread-209431-1-1.html
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()实在很好用，掺了数字在里面也不影响。

说给你一个BST的root，再给你一个数字范围[A, B]（2-side-inclusive)，要求找出来一个subtree，这个subtree里面所有的node的value都必须是在这个范围里面，output是subtree当中node的个数。如果你找到多个subtree符合条件，那就返回最大值。

我看到题的时候就懵逼了... 后来想了想第一反应是得借助DFS，再想着DFS得用recursion吧，于是楼主开始试着用了recursion。Turns out到最后我发现我的solution method和我的helper method都用了recursion，一团乱，没想到最后慢慢debug还真过了test cases... 大概想法就是看我的root的值，如果大于B，我就完全抛弃右边的subtree不看了，只看左边；同理如果小于A，我就完全抛弃左边的subtree不看了，只看右边；如果root的value在valid的范围内的话，我就用DFS去查它的每一个children，只要有一个children的value不在范围内，就说明这个root肯定不在最终最大的subtree当中，我就分别看它的left和right （recursion）。至于count我是在helper里面写的，楼主用了c++写第二道题，count pass by reference进去helper function，所以这个不难实现。

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

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

是的每次排序NlgK, N是votes的数量，一共排序N次

第三题就是sort hashmap by value 吧…?
请问前三个是不是sort by hashmap value？ nlogn 然后第三个可以用一个minHeap 优化成nlogk 第四题可不可以考虑用二分查找呢？~ 因为每个人的选票肯定都是随着时间递增的~ 然后每次查找是nlogk 一共找logLen, Len是时间interval的长度一共就是nlogk*loglen 0.0 不知道是不是这样优化

timestamp是6就是0 - 6，不会是 2 到 6 这样，所以不是范围，BIT没有必要吧？
感觉对votes做binary search ? 就是lgN * NlgK, 比如对votes做个sort, 然后binary search, 但是条件怎么判断呢？因为给的input 就是要对比的List<String> = {"candidate a", "candidate b", "trump", "hillary"...>, 然后你求出的那个list = {"trump", "hillary".....} 这个东西我觉得没法判断这种list是要mid 给 start 还是给end

http://www.1point3acres.com/bbs/thread-211946-1-1.html
is_same_permutation(a, b)
给两个list，看它们是不是permutations of each other.
http://massivealgorithms.blogspot.com/2016/11/check-if-two-arrays-are-permutations-of.html

http://www.1point3acres.com/bbs/thread-209202-1-1.html
第一轮，Longest Substring with At Most K Distinct Characters变形题，输入是stream而不是string，所以无法知道输入的长度，而且内存不够，无法存入整个stream，所以维持sliding window来更新最大长度的算法无法解决该问题。最后是通过一个map纪录每个字符上次出现的index来实现。提供了函数streamreader.reader()来返回下一个字符。这一轮表现不好，主要是刚听到题目兴奋了一下，好不容易遇到一个做过的，发现并不是那么回事儿，心情有些波动。
http://massivealgorithms.blogspot.com/2016/04/leetcode-340-longest-substring-with-at.html

第二轮，combinations 外加 longest palindrome string from a give string, 比如“atatdc",可以返回”atdta" /"tadat"/"atcta"/"tacat",这个题目需要返回所有可能的结果。
第二轮: longest palindrome string from a give string: 若假设已经有了从一个char frequency map算所有不同string的算法“vector<string> getDistinctStrings(const unordered_map<char, int>)”，那么是不是就是暴力直接把半个frequency的所有组合再加上一个有可能的中心char的所有组合呢？不确定有没有更快的算法。

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

第三轮，类似于pacific atlantic water flow，follow up是假如输入不是一个矩阵，或者说小岛的形状是真实的任意形状，如何解决问题，需要自己设计一个类

第四轮，类似于longest consecutive sequence,输入是collection,有可能是List，也有可能是set，需要自己转换一下。

另外一题比较绕，花了十几分钟才搞明白，题目是给一个数组，例如【2，1，3，5，4，6，8】，利用binary search 的思想，但是现在数组不是排好序的，而且pivot是任意的，返回值是总能找到的target的个数。比如我们想找5，pivot不一定是mid=3，有可能是index=4，采用binary search的思想，5>4，应该搜索右半部分，即6和8，这样是找不到5的。最后的结论是当前的数字大于等于左边所有数字，并且小于等于右边所有数字的情况下，是可以保证找到改值的。上面例子一定可以找到3，6，8，所以返回值是3.
- O(n)
find item where left are smaller, right are bigger

第五轮，是关于iterator的问题，follow up比较多，但是不是很难。最后还有一些时间，问了一个简单的design的问题，如何处理distribute system里面数据备份保证availability和reliability。
看过几片distributed systems的paper，基本上的思路是master-slave的server-mode，replication在不同地域，不同dag保证reliability，同时需要有transaction log来保证recovery failover，同时还比较了一下strict consistency和relaxed consistency的优劣。

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

Google Interview Misc Part 9

Labels

Popular Posts