Massive Algorithms: Google Interview Misc Part 8

Google Interview Misc Part 8

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

给一个List<String[]> pairs, 里面的array是长度为2的pair,双向的。
然后输入两个query, 每个query都是一个String[], 要判断这两个query是不是一个叽里咕噜叽里咕噜
条件就是这两个Array对应位置上的String要么一模一样，要不就是pair.
Follow up: 用一个全局变量做pair的map, 因为真对会有很多，另一个是优化pair储存，有连续性，a -> b, b - > c, 要也能存a - > c

返回一棵树里面所有的爸爸->我->儿子的序列
我就是DFS做的，想办法查重就好了（如果你的方法有重的话）
Follow up: 因为我查重了所以，他问我，把一个Node作为Key放到一个Map里面的时间复杂度。

同学做过的，返回一棵树里面所有相同子树的node,List<List<Node>>, 每一个list里面存的都是拥有相同树结构的树根。
把所有节点下面的书都seralize, 然后存成 Map<Stirng, List<Node>>.
Follow up: 时间空间复杂度，如何优化

一大堆Task有开始时间和结束时间，要把这些工作派给不同的工人
每个工人有一个list存放自己要做的Task
要求把这些工作尽可能的安排给少的工人，存在他们的工作List里面
最后返回这些工人

第一题的话很简单，就是两个String Array比较，合法就返回true，不合法就返回false.
第三轮我也没说出什么好的优化，跟他讨论了一下，说时间空间现在都是O(n)，他说空间上，Map的key会很长，我说是的诶，但是不可避免的我需要存下来unique的树结构的所有信息用String,他说那好吧，其实他也没答案。
第四题工人存放的是安排给他的工作，就是所有工作安排给所有工人，然后所有工人组成的list就是结果。
我一上来就是Meeting Room 2 的思路
在meeting room2 里，最常规的思路就是分开看，开始时间和结束时间，然后做完了就可以做新的，有会还在开的时候就得加一个会议室，这里跟这个很相似，我每次都找到所有现有worker中工作最早做完的那一个，然后跟最近开始的工作的开始时间作比较，如果来的记做就安排给他，来不及就加个新的。当时时间紧也没有细想对不对。。。

http://www.1point3acres.com/bbs/thread-212094-1-1.html
因为面的不是很好，所以进入了加面。
加面一共问了五道题目，真心没想到会问这些类型的题目。
第一题：求多边形的顺序点集，求多边形的周长
第二题：根据Q1写的程序，写一下Unit Test。因为之前没写过，所以答得很不好。
第三题：“what is refence counting?" C++ 中怎么实现？
第四题: 可能是根据第三问来的，给一串字母，求每个字母出现的次数。
第五题：输入：www.google.com, 问在网络中都有那些操作？（有一个前缀，具体记不清了，就是不是输入在浏览器里）。
http://www.1point3acres.com/bbs/thread-208431-1-1.html
1. 实现浮点数数组求平均值，明显不可能加和这么简单，多问了一句是否保证不溢出，果然不保证，于是保存当前平均值，记录count，用加权的方式做的，感觉没问题，但是他还是说有问题，让我看，我没看出来，就过了。。。

第一题楼主的做法是前k个平均数为a_k, 然后前k+1个就变成(k*a_k + n_(k+1)) / (k+1) ?
感觉这样大数a_k*k加小数n_(k+1)会导致精度丢失，特别是k大的时候

如果要精度的话一般是分治来做吧，不过这时候复杂度就上去了
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出，假设前k+1个数全部是最大浮点数这样就溢出了，我想了一下但是没有办法处理精度，大家给看看精度怎么处理：
第一个是 average(k) + (nums[k+1] -average(k))/(k+1) 这个也会溢出，在average(K) 为最小的负数， nums[k+1] 为最大正数的时候.
第二个是 nums[0]/len + nums[1]/len + .....+ nums[n-1]/n 这个不会溢出但是精度就太差了。

对，面试完了我想到涉及浮点数肯定有精度问题。。。但是面试的时候没想到。。。
不知道你加了长度判定的优化没有。
2. 第二题是字符串判断是否由重复字符串组成，感觉leetcode做过，可我属于一面试就极紧张的，脑子一片空白，问最直接的暴力算法行不行，他说先实现最好，我觉给了个暴力算法直接不同长度试，然后还有10分钟让我优化，想了个DP的方法不知道对不对，repeat数组存当前字符结尾的重复字符串的长度。。

比如abab，返回真，aba，返回假，a返回假，就这个意思。

写完代码他说我觉得很clear了，时间到了，你有什么想问我的吗？问了自己比较关心的，你认为在狗狗一个好的SDE最重要的是什么素质？他说要能够搞清楚自己应该做什么的能力，还有沟通能力，当然smart也很重要。

http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/
用的是KMP构造prefix array

http://www.1point3acres.com/bbs/thread-212592-1-1.html
1.number of island 2. 这题刷过时间太久了我给忘了。。用union find做了，中间有个地方出了个bug，我也是醉了。。。
2. 亚裔小哥。输入一个file: [A, B, 0.6], [C, D, 2].... 代表A = B* 0.6， C= D* 2.....
第二个file: [A, C, "_"], [D， F， “_”], 要求根据第一个File, 把第二个file第三列的空格填上。规则和第一个file的一样。
DFS BFS都行。用BFS，小哥要求不能记住当前所有路径，要用BFS with path reconstruction。有点蒙蔽，写出了一坨翔。
小哥要求我先找到最短路径再根据path求路径的总weight. 所以就是再bfs的时候存下来到每个node的previous node（最短的），然后找到target以后reconstruct path。
就是再bfs找到路径以后在往回reconstruction path. 不能用queue记住所有从start到当前层的路径，太费空间。
division evaluation
对这就是个directed graph. 因为assume不会出现invalid的情况，也就是不管什么路径，找到的accumulative weights 一定是一样的，所以dfs bfs都可以。

3. 美国大叔。大叔一上来丢给我个c code，让找BUG。楼主蒙蔽表示不会c，大叔说没关系，看看吧。。。看了N久终于发现了一个弱智bug: string qual 只比了开始地址。。。大叔的表情就是：谢天谢地你终于找到了，来来我们快来正式抠腚
题目是：有个很大的word list，里面全是length为 5 的word。里面有个target要我们猜。来写个猜的策略。每次猜过以后会返回一个feedback表示在哪个位置的哪个Char猜对了。
假如word list 里是： trips, trick, treat; 目标是：trick, 你猜的是treat, 结果会返回 tr_ _ t。我提了几个策略都被否定了，没说到大叔心坎里。最后草草写了一点code，也是一坨翔。。。
第三题，因为treat中 t出现了两次，只要是在target里有这个char，结果中就会出现，不管在target里的什么位置。

第三题我说先看一遍List，统计一下每个char的出现次数，然后根据这个来找一个含有最多char出现次数的word，也就是争取在每次guess的时候eliminate 最多的错误Word。然而说了半天感觉他并不赞同。
我的意见是如果我上次guess的词跟答案对的某几个char那么我在我当前的word里面每一个跟上次猜的词比较。如果对的char跟答案与猜词对的char不一样的一定不会是答案就从words里面删除。一直到最后只剩下一个词可以猜。。。
那如果我的target 是 "ttttt",岂不是trick, treat, trip,或者ttttt都返回 "ttttt“。这样就找不到target了。
没错，如果你的词是ttttt就是会这样。但是需要注意的是你知道Word list，所以你也不会猜不在list里的词。

关于第3题，如果input是这个样子的: target=ababa, list=[abbab, abaab, aabbb, ababa]. 那么因为feedback不关心字母的位置，所以对于任意的猜测词list [ i ]，feedback都是list[ i ]本身，这样的话，不就无法解了么？还是说1.假设不会出现这种情况，2. 出现这种情况返回null？

还有就是，如果feedback完全不考虑顺序的话，那我岂不是可以总是这样猜: {abcde, fghij, klmno, pqrst, uvwxy, zabcd}。比如得到feedback序列{a____e, _____, _____, __r_t, _a___}, 这样我就知道target中肯定有且仅有t, r, e, a四个字母。然后再扫一遍原word list，找到符合条件的词即可。无论word list多长，只需要最多猜测6次，在原word list中并未出现字母表中所有字母的情况下，猜测次数可以进一步减少。

对，我感觉这个题的目的是根据word list的char出现的情况来决定每一次猜测的最优策略

4. 印度小哥和一个shadow。flip game 2稍微变形. 我又醉了，都是刷过的忘了的题。写了个暴力Recursion，让优化。我提出可以减小连续+号的长度，或者消去成对的减号。说了一下可以memorization。小哥让问问题。

http://www.1point3acres.com/bbs/thread-206515-1-1.html
1. 给一个int，根据一定规则替换相邻的两个digit，返回替换完成的int。
1.1 replace two adjacent digits with the larger one， return min (e.g. 233614 -> 23364)
1.2 replace two adjacent digits with the round up average， return max (e.g. 623315 -> 63315)
1.3 choose a group of(at least two) identical adjacent and remove a single digit， return max (e.g.223336226 -> 23336226)
2. 给一个代表文件路径的string，根据具体题目要求，返回图片（.jpeg or .png or .gif）路径长度。
e.g. Given String s = "dir1\n dir11\n dir12\n picture.jpeg\n dir121\n file1.txt\ndir2\n file2.gif";
 So image paths are /dir1/dir12/picture.jpeg and /dir2/file2.gif
1.1 return longest image path to root (return 11, /dir1/dir12)
1.2 return longest image path to imgae (return 24, /dir1/dir12/picture.jpeg)
1.3 return total image path to root (return 11 + 5 = 16, /dir1/dir12 + /dir2)

1.4 return toal image path to root (return 24 + 15 = 39, /dir1/dir12/picture.jpeg + /dir2/file2.gif)
思路：
1. 我用的brute force，只是局部优化了一下。应该有更好的解法，之前尝试了一下，有点晕，遂放弃挣扎。（oa只要求结果正确）
2. 自己定义了一个treenode，然后dfs。之前看了地里前辈们的解法，很多用stack的，乍一看没太看懂就没仔细看了。
第二题可以去leetcode 388练习下.
http://www.1point3acres.com/bbs/thread-212708-1-1.html
我的题是1.2 round up average; 2.1 longest image path to root
http://www.1point3acres.com/bbs/thread-208043-1-1.html
Given a page of website, count the number of unique reachable pages.
例子： '+'代表算 '-'代表不算
+google.com
/link to
+google.com/a
/link to
+goole.com/b
 /link to -------------------/link to ----------------------------link to
-external.com +news.google.com/ -newsgoogle.com/
给了一个api, already implemented
vector<string> parseLink(const string &url)
e.g. parseLink(''google.com/b") return {"external.com", "new.google.com", "newsgoogle.com"}

implement this one
//e.g. crawl("google.com") return 4
int crawl(const string &url);

基本上对于给的url，用parseLink找到所有的链接，在返回的所有的链接里逐个跟url比较，看看算不算合法的链接，然后再recursive call crawl（”链接“）这个function，注意要求是unique的

一开始想用trie找到链接里的prefix跟url相同的，然后他就给我举了+news.google.com/ 和 -newsgoogle.com/ 的例子，见我实现起来比较困难，又给我一个已经实现的api

bool sameSite(const string &url1, const string &url2);
//return true if the two URLs are part of the same site.
// e.g. sameSite("google.com", "google.com/a") return true

然后问那些test case, cyclic webpages要包含，例如：faceboo.com --> facebook.com/login --> facebook.com
最后我问了1个问题：
这个组做的东西主要是内部使用还是外部使用？
跟地里看到的帖子差不多，基本上都是内部使用
http://www.1point3acres.com/bbs/thread-212729-1-1.html

generic tree。每個node 有自己的id， parent id，和 value。給一個array of tree node。求出每個node 的subtree 和。

我的理解：generic就是说是一般的tree，每个node的child nodes个数不定。用哪一种种数据结构只是表现形式不同，并不是generic的定义。这里用数组和定义id只是与传统意义下用child指针的表现形式不同而已。
这里的"每個node 的subtree 和"是指以每个node为根节点的subtree节点value之和吗？不知道id的类型是什么，我就用template写了一个统一的（假设id类型hash和equal operator已经存在，i.e.,可以用作hashmap的key）。就是把每个node的value加到自身和以及沿着parent链的每个node上。

template<typename T>
struct Node { T id, parent; double value; };
unordered_map<Node<T>*, double> subtreeSum(vector<Node*>& tree) {
unordered_map<T, Node<T>*> nodes; unordered_map<Node<T>*, double> res;
for (auto& x:tree) nodes[x->id] = x;
for (auto& p:nodes) {
auto node = p.second;
double v = node->val; res[node] += v;. 1point 3acres 璁哄潧
while (node->id != node->parent) {
node = nodes[node->parent];
res[node] += v;
}
}
return res; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
}

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

1. bayes thm. 算p(disease | positive)

2. 3 个温度计前两个var ＝1 最后一个 var ＝2，怎么测量oven温度。如果最后一个var ＝0.05 呢？

3. 下雨的概率是p，cost function：＝k 如果被淋湿，＝2 带了伞没下雨，＝1 带了伞下雨。怎么决定带不带伞。

然后就是hypothesis testing 的assumptions 要很清楚
感觉平常做作业不要只输出答案做题前想想你想要看到什么结果看到结果后你有什么comment
很可惜我平常就只要有答案就完了所以面试也跪的妥妥的
r code 都是比较基础最后就是多听听不同口音
http://www.1point3acres.com/bbs/thread-212843-1-1.html
第一轮：白人大哥，设计贪吃蛇，我一直没有看过设计题，在对于蛇的data structure上跟小哥纠结了很久，最后用coordiantes解决了但是也没有写完，小哥在那边非常不耐烦。
第二轮：一个非常nice的烙印？问的问题简单的不能再简单了。
1. s = 'ABCDE', t = 'ABxCDE', 找出inserted character。用two pointer做的，又写了几个test case。
2. follow up，如果t被shuffle了怎么办。用dictionary做的。
3. 树的alternate level order输出。用BFS做的。
http://www.1point3acres.com/bbs/thread-203122-1-1.html
还好看了一眼题目，发现条件不对头，面经是『623315』把两个数字换成较大的，然后使结果最小，我遇到的是把两个数字换成平均数，向上取整，使结果最大。
第二题也有小变化，面经是求文件的最长路径，我遇到的是求最长路径但是不包括目标文件，就是只包含『/dir1..』这种，gif文件什么的都不包括。
http://www.1point3acres.com/bbs/thread-211188-1-1.html
binary search，如果numbers服从uniform distribution，怎么优化。
OOD。
求进pool。
OrzOrzOrz
http://www.1point3acres.com/bbs/thread-167833-1-1.html
Phone Interview:
1. 一个sorted的linked list，最后一个node会link回第一个node（相当于是一个loop），现在要把一个新的node插入其中，使整个loop仍旧保持一个sorted的状态。
2. 如何测试Gmail。
On-site Interview:
第一轮，美国女：
给出一个String，要求rearrange这个String，相邻的两个characters不能相同。如果String不能满足这个要求（比如abbbb），就返回空String。

第二轮，美国小哥：
做code review。给出几个class，用来连接数据库、建立table、获取数据等等。要review的code是一个连接database，根据给出的key去fetch data，然后输出结果的function。

（Code review之外，面试官提到了在做test时每次到database去fetch data都要很久，问是否有优化的方法。另外，因为给出的class本身是implement了一个interface，所以面试官询问了一堆Java interface相关的问。）

第三轮，中国小哥：
一个graph，如果把其中一个点挪动位置，得到一个新的graph。看起来这两个graphs好像“长得”不一样，但是实际上是相同的。给出两个graph，要求编程判断这两个graphs是否相同。（complexity不计，也就是说可以完全不考虑时间空间复杂度，只要能够解决问题即可。）

第四轮，美国小哥：
1. 给出一个integer array，求其中consecutive的sub-array的最大长度（LeetCode原题，No. 128）。
http://massivealgorithms.blogspot.com/2015/08/jiaxins-leetcode-longest-consecutive.html

2. 给出一个tree（不一定是binary，也就是说每个node的children个数不定），求其中元素是consecutive的最大长度。——类似Leetcode原题No. 298，区别是这里的tree不一定是binary tree。
http://massivealgorithms.blogspot.com/2015/10/leetcode-298-binary-tree-longest.html

3. 如果题2中的tree大到memory无法运行，要怎么办第五轮，中国女
给出一个binary tree，其中有一个node出了问题，它链接到了一个illegal的位置——比如说，C是D的child，但是有一个链接把C又连回了D，相当于D又是C的child，这不是一个valid的binary tree。要求编程找到这个出错的node，相当于Validate a Binary Tree。
http://www.1point3acres.com/bbs/thread-207688-1-1.html

右移array k 位, in-place

input: {0, 1, 2, 3, 4}, k = 2

output: {3, 4, 0, 1, 2}

这题几分钟写完了。用的是三步反转法，

reverse(nums.begin(),nums.begin()+left);

reverse(nums.begin()+left,nums.end());

reverse(nums.begin(),nums.end());

这个算法变量赋值是O(3N)次。

接下来他一直叫我优化到变量赋值是O(N)次。

个人感觉这题加面电面题三哥问的不过分，的确是很正常的followup。3次reverse的解法已经很常见了，如果就凭这个当作加面结果肯定不合适，所以面出这种程度的followup是意料之中的。

其实换一个角度想，如果你不知道3次reverse的话，你会怎么做呢？其实有一个非常straight forward的做法：不是要移动K位么？那么我先存下a[ 0 ], 然后每次让 a[ i ] 和 a[ (i + d) % n ]交换就行了。这个做法的确能过掉很多input，但是对于n和k不互质的情况，模拟一下就会出问题。问题出在哪？出在交换了已经移动的位上了。怎么办？多模拟几组互质的数据就会发现，当我交换着交换着发现我回到了起始点的时候，就可以停下，然后从起始点下一位开始再开始相同的交换过程就可以了。

上面这个解法就是所谓的最大公约数解法，因为最终其实分成了 gcd(n, k) 组。但是掰开了就是一个最简单情况的优化而已，而且只要面试官给点提示肯定能做出来。

巧妙的解法容易被记住因为这种解法往往是把不相关的点联系在了一起，然后我们却绝对不能忘记应该如何一步步的从最原始的解法优化到一个满足各种限制的解法。能想出巧妙解法却无法追根溯源的人，你能信任他能够把一个慢吞吞的服务一步步优化到亿级服务么？

http://www.geeksforgeeks.org/array-rotation/

http://www.1point3acres.com/bbs/thread-210668-1-1.html
第二面应该是个美国白人小哥，上来写个check回文热热身，然后说不能只会python，来用c++写个多线程的程序，我说不会跳过。然后让我写了求根号的程序，LC上有，简单的题费了半天劲。之后又做了个coding题，是给你一个string，求最长的substring，是另一个substring的prefix。比如"abcab", "ab"出现在两个地方，所以是符合条件的
后缀树，搜longest repeated substring
http://www.1point3acres.com/bbs/thread-212675-1-1.html
第一轮，一个m*n的matrix , 从左上到左下有多少种走法。用dp
follow up 1 : 有一个点(x,y)必须要经过，有多少走法。然后优化内存，用rolling array
follow up 2 : 有一个set的点都要经过，有多少走法。我说要用HashSet来快速找点，然后问Point class怎么做hashing，写了hashCode function
matrix中每一步有要求，必须要向下走，同时水平方向上每次有（-1,0,1）三个选择

到每一行，看这一行有没有必须要经过的点，有的话只保留那个格的步数就可以了，其他都是0，没有就正常dp，有超过两个就直接return 0吧

第二轮，先是两道特简单的字符串题，然后面试官说"Here comes the real question"
给一个字符串的abbreviation ，就是把一些连续的字符转成数字，比如apple -> a2l1 , 然后让写一个函数验证一个带数字缩写是不是另一个字符串的缩写。two pointer秒过第二道是给一个排好序的字符串数组，有n个字符串，还有一个前缀prefix字符串，长为m,要求函数返回start index和end index，其中所有字符串都以prefix开始，先用binary search，达到m*log(n)复杂度，面试官挺满意，然后我又给了个Trie树预处理O(所有字符串长之和)，之后每个prefix都可以有O(m)的查找。面试官挺高兴，又聊了聊java 8的新feature，保证lamda和stream api。

题挺简单的，代码都写完了，后来想起来个exception,面试官下线后趁还没把我踢出去给改了

画一下简单的Trie示意图，然后说一下怎么从prefix的最后一个Trie Node出发找start index和end index. start index一直向最左走，直到遇到第一个index , end index一直向最右到尽头
http://www.1point3acres.com/bbs/thread-208462-1-1.html
首先是两个关于实习project的问题。
后面是三个问题：
1. 有一个方块，四点坐标分别是(0,0), (A,0), (0,B), (A,B)。方块内有一波浪线，线下的点都是logical value True，线上的点都是False。问线下的面积和其他的followup question。
我用的monte Carlo，但是听领导说用数学方法会更容易？数学不好，只能想到monte Carlo simulation。。。
2. A/B test
比如怎么衡量你的方法是不是准确
请问楼主A/B test会问到什么深度阿？是让你design test吗？

3. logistic regression on basketball player, predicting whether put into Hall of fame
http://www.1point3acres.com/bbs/thread-212930-1-1.html

1. 两个bst找common nodes，不知道怎么才能优化
2. twitter design，跟烙印讨论了好久怎么处理offline user收到message
3. java debug＋怎么爬网页纪录网页里的http link
4. abbreviation题目很简单。。忘记了
5. 一个set里面有a，b，c等若干个char，设计random函数，得到某个char的概率和它
的出现次数成正比。

請問第一題是先FLATEN兩個TREE 然後TWO POINTER找COMMON NODES嗎？這樣應該是O（N+M）

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

Dynamic programming, maximize vacation days, want list of offices

上来直接问题，一直做了52分钟，挺容易想到DP。但是在实现的时候有很多细节需要考虑。楼主这面面的不好，虽然状态转移方程写出来了，但是实现的时候被指出了很多bug。首先要注意初始化，其次是填二维表的顺序，最后是result存在哪里。面完面试官觉得还过得去，因为毕竟代码写完了。

第二轮，烙印：

上来问了简历，楼主简单地说了下most challenge project，然后开始做题

timestamp, color, find first occurrence of color and reserve the original order

由于上一轮多用了时间，这轮问的这题比较简单。就linear scan，期间用hashmap去重就可以了……不知道他出这题啥用意

overlapping meeting intervals, return the first overlapping interval

这题楼主先说了brute force的解法，O(n^2)。然后提出先sort的解法，O(nlogn)。然后楼主就开始沉思是否有O(n)的解，想着想着被烙印打断。他说nlogn的解法is acceptable，然后叫我实现下。我心里就想着这不是很简单吗……就乖乖地开始实现了。实现完了以后，他就问我你的code是不是有bug？我看了半天说没bug啊，他看没时间了，就给我指出来一个edge case。所以提醒大家遇到简单的题，还是得好好想仔细了再code。

music list, if shuffle is possible or not, test cases

这轮比较扯淡，国男带着自己的电脑过来的。问完题目就自己闷头开始debug，可能在赶deadline……题目不难，但是所有需求没有马上展开，是在我和面试官不停地交流过程中发现的一些隐藏需求。然后被要求code，我就开始写代码，没有一遍bug-free。面试官看了下说有bug，然后又干自己的事去了，我改好给他看，他又说还是有bug，来来回回几次，他才说好。然后他一看还有15分钟，说自己也没next problem了，叫我要不写下test case。写完时间也差不多了，叫我问他问题，问完结束。

. Waral 鍗氬鏈夋洿澶氭枃绔�,

第四轮，亚裔 + 白男shadow：

上来先问了下简历，花了大概5-7分钟时间说了most challenge project

这个edge case是说同一个时间点，排序的时候结束要排在前面吧

wiggle sort

这题我面试前就准备过，听完题目描述，我便成竹在胸。于是小演了一下，先给了sorting的解；然后若做沉思，再给的O(n)解答。面试官很满意，可劲喊good。

longest path length from node to node

这题和leetcode上的max path sum很接近，也算半个原题。我讲了思路，写了code，面试官表示赞同，并拍了照。
. from: 1point3acres.com/bbs
面完最后一轮正好2：30pm，结束了一天的面试。感想是Google这种上午2轮，下午2轮的面试形式很好，面完并不觉得疲惫。之前面的公司都是下午一气四轮，那四轮下来真是心力憔悴。另一个感想就是Google onsite并没有想象中那么难，面试前一天，楼主准备了surpasser, iterator of iterator, quadtree intersection, threaded binary tree, popular number, maximum submatrix sum等题，都没有考到。既然题目简单了，楼主觉得面试过程中的交流和对一些edge case的细心就挺重要的。

另由于楼主有pending offer，HR答应帮楼主accelerate hiring process（两周）。顺便说下Google的hiring process：

1. HR collects feedback from interviews (including phone interviewer)

2. HR hands in all the data to hiring commitee 1

3. Pass first hiring commitee

4. HR hands in all the data to hiring commitee 2

5. Pass second hiring commitee

6. Potential Offer

This process usually takes 3-4 weeks.

你有一个music的播放列表，里面的歌曲unique，但是播放列表的长度未知。
这个音乐播放器APP有两个模式：random模式和shuffle模式。
random模式就是每次随机播放列表里的一首歌；

shuffle模式就是shuffle列表里的歌，然后顺序播放，放完以后重新shuffle，再顺序播放；
现在给你一个播放历史记录，要求你写一个函数来判断用户使用的是random模式，还是shuffle模式。

是的，就是hash一遍……这题主要是和面试官交流题意。。因为最开始的需求面试官说得很模糊。
上周店面1，面的是青蛙跳
http://www.1point3acres.com/bbs/thread-206451-1-1.html
一面国人小哥，oo design，设计一个set 支持O(1)的add, remove和getrandom
二面，给一个binary tree，每个节点是一个char，每个leave to root path构成一个字符串，输出其中最小的一个。
http://www.1point3acres.com/bbs/thread-208420-1-1.html

http://www.1point3acres.com/bbs/thread-210420-1-1.html
第一个面试官10点10分才到，是一个岁数较大的亚裔大叔，一上来没废话，直接出题，给两个tree A和B，判断A是不是B的sub tree，讲完思路后写代码。

第二面试官是一个华人大哥，直接出题，LC313，楼主做过这个题但是思路记不清了，囧，想了好久才理明白思路，最后花了5分钟写完代码，walk through了一个case验证代码没问题。
http://massivealgorithms.blogspot.com/2015/12/leetcodesuper-ugly-number.html

第三个面试官是一个白人大哥，人很nice，题目是搜索的分词，参数是一个搜索字符串"girlsandboys"，一个hash set作为词典如{"girl", "girls", "and", "sand", "boy", "boys"}，根据词典，返回任何一个分词结果均可，比如"girl sand boys"，后来用了另一个hashset做了优化。题目很简单，也没花多少时间，主要是讨论了好多搜索分词的东西，比如google的搜索分词是怎么设计实现的。

第四个面试官是一个白人小哥，人也很nice，LC17，和LC271，全部秒掉。然后闲聊了一会，他把送出门就走了。
http://www.1point3acres.com/bbs/thread-212896-1-1.html
第一轮在匹斯堡做google shopping的面试官，两个easy题（1） 00111100110101 integer的bit表示形式中最长连续1的sequence的长度和开始位置（2）读一个file，里面全部char （ASCII value），要求输出sort后的文件内容到另一个文件，文件内容太大，一次读不进RAM。感觉因为快放假了面试官在在放水？

第二轮就有趣了，先是问简历，然后问javascript, java, c++谁快和编译时候都经历了什么。。。楼主说了下C++的，js 和java不太懂，面试官给了些提示，就过去了（这里有必要说一下面试官是在G家呆了11年的牛人，但是这风格太不google了），然后上题（1）斐波那契数列 recursive + memorization + iterative （这真的是面google？）面试官第二题让我用javascript写代码，虽说我简历上有写会一点javascript但是已经全部忘光了，，，就坦白说不会，结果面试官说那我们换一道，然后出了一道找两个string array里duplicate的string的水题，是不是我太无药可救了

http://www.1point3acres.com/bbs/thread-205342-1-1.html
1. Leetcode 163.
leetcode 163: Missing Ranges

2. 找到一个binary tree中最深的node，(如果有多个最大深度node，返回最左边的node)，我一开始用了recursive的解法，后来的follow-up是使用iterative怎么解，应该是用BFS，等到queue里面只剩下一个node并且这个node没有left child 和right child的时候，返回这个node。
lz第二题如果用bfs的话应该是先放right,再放left到queue吧，不然最深的node> 1的情况没法返回最左边的node

TreeNode *getDeepestNode(TreeNode *root) {
if (root == nullptr) {
 return nullptr;
}

TreeNode *deepest = nullptr;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
 TreeNode *node = q.front();
 q.pop();
 deepest = node;
 if (node->right != nullptr) {
 q.push(node->right);
 }
 if (node->left != nullptr) {
 q.push(node->left);
 }
}
return deepest;
}

第二题用recursive的方法，需要记录叶子节点的深度吧。如果最深的有多个，怎么才能返回最左边的节点呢

可以用inorder的顺序遍历，然后如果当前node 深度大于最大深度，才更新最深node
哦哦，等于的时候也不需要更新

http://www.1point3acres.com/bbs/thread-212907-1-1.html
1. LC46，返回所有permutations。我也傻，直接问n大不大。人家说特别大，内存装不下。我一下蒙了。然后秉承“不抛弃不放弃”的原则,不会做就自己加条件。所以告诉他，我想先assume可以再内存里。他说好。我就写了。然后开始想怎么优化。现在冷静下来想想，其实有特别多方法。比如10个数，做前5位的permutation。存起来，然后再逐条读出。每条再做后五位的permutation。
当时我灵光一闪，想到的是nextPermutation。面试官好像没有想到这种笨办法，所以一直要我写main函数。
非常简单。 input = nextPermutation(input). 这样来回n!次就全部输出了。问Time Complexity. 我竟然说O（n）。发现他说是整个程序。就是O（n* n！）

面试官一开始就没有说存到list里只是说print。然后我没有仔细读题直接存到list里了然后return了

我猜想面试官提出来n特别大的这个问题只是想告诉我你不需要return list 只需要当时print 就好。他应该不是成心想难为我或者问我内存相关的问题所以他也不是真正期待一个解决方案

我电面也是generate 所有permutations 中国小哥面试官也是问我 n非常大怎么办？我没太懂他的意思最后他说你直接print出来就可以不需要返回 list of strings

2.比较不同version。每个version有一个号，比较两种那个是new version。主要是要考虑很多神奇的case：
1.123.23 > 1.1.99.11111111111111111111.1
5.00.0 == 5
2.000000.0 <2.000000.1
这个题面试官对很多细节非常抠。注意一下就好。

http://www.1point3acres.com/bbs/thread-191771-1-1.html
第一轮是个典型白人大姐，人挺nice，题目就是LC 对称数1 followup是2，不同的是需要返回所有长度1 - n的而不是只返回长度n的。LC 247......

第二轮是个白人大叔，感觉像刚嗑药似的非常嗨，不过人不得不说非常的helpful。。LZ代码基本上是他一步步指引着写出来的，只是感觉他在旁边比我还激动。。。题目很麻烦是他们现在在做的maps的一个功能，大概是一个四叉树，然后让你调用他们已有的API，寻找距离最近的前几个饭店，主要是讨论，code时间很短。

第三轮是reverse shadow，国人大哥面的，题目就是给你一个matrix，里面的数字代表bar的高度，现在说降雨量如果高于bar的高度水可以漫过去，降雨量0开始每天+1这样，问最早第几天水可以有一条路径从src漫到dst。这轮也是讨论optimization很久，最后用bfs写一个subproblem。
http://massivealgorithms.blogspot.com/2016/06/water-flow-days-moonstone.html

第四轮是一个印度大姐面的，人挺nice的必要的时候也给hint，题目就是单链表版addOne，不允许修改原链表，然后要求时间O(n)，空间O(1)。

two scann O(n)...找到连续的9的部分如果这部分在end of the list，记录这部分的初始位置，然而第二遍从这个位置开始+1.
http://www.1point3acres.com/bbs/thread-212920-1-1.html
2. find unoccupied intervals
3. every people has two field: father and mother. given 2 people, determine if they have blood relationship应该是 check(A, B) || check(B, A)
4. recover binary tree
MS:
1. implement C++ manner vector
2. lc76, lc104
3. lc121
4. lc68
5. design DNS service
Uber:
1. Behavior why uber...
2. Behavior resume-related
3. lc239, lc17
4. lc398, lc253
5. lc417

G:
1. lc394, inorder travesal

lc394做完以后还剩几分钟又做了个inorder travesal

http://www.1point3acres.com/bbs/thread-211163-1-1.html
每个node都有left，right，还有parent指针
3. given positive number n, find all of the sequences, so that the difference of neighbor elements
are power of 2 and the greatest number is not greater than n.

vector<vector<int>> generate(int n) {. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
vector<vector<int>> result;
vector<int> path = {0};
helper(0, n, path, result);.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
return result; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
}
private:
void helper(int k, int n, vector<int>& path, vector<vector<int>>& result) {
if (k >= n) {
result.push_back(path);
return;
}
for (int delta = 1; delta + k <= n; delta *= 2) {
path.push_back(delta + k);
helper(delta + k, n, path, result);
path.pop_back();
}-google 1point3acres
return;
}
};
.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
int main() {
Solution solution;
vector<vector<int>> result = solution.generate(4);. visit 1point3acres.com for more.
for_each(result.begin(), result.end(), [](vector<int>& v) {
for_each(v.begin(), v.end(), [](int& i) {
cout << i << " ";
});
cout << endl;. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
});
return 0;
}

举例 n = 3, 那么结果就是:
[0, 1, 2, 3]
[0, 1, 3]
[0, 2, 3]

举例 n = 4, 那么结果就是
[0, 1, 2, 3, 4]
[0, 1, 2, 4]
[0, 1, 3, 4]
[0, 2, 3, 4]
[0, 2, 4]
[0, 4]

4. RPN
RPN是逆波兰表达式，面试时具体的题目是这样的：
输入"(* 1 2 3)" => 输出 6
输入"(+ 1 2)" => 输出 3
输入"(* 1)" => 1
输入"(+ 1)" =>
输入"(+ 1 (* 2 3) 4)" => 11
输入"(+ 1 (* 2 3))" => 7
5. solve maze, 自己想输入输出的数据结构

1. 给定一个数组，从每个元素向后面查找，计算出后面比它大的元素的个数，返回最大个数的元素的index
比如
[5, 2, 4, 1, 7, 6]

那么计数之后就是
[ 2, 3, 2, 2, 0, 0]

最大计数是3，返回index就是1

复杂度需要 O(nlogn)

2. given a valid no-duplicates binary search tree and a TreeNode, find the TreeNode that has the smallest larger value than given TreeNode in BST

不是，题目的输入只有一个参数，就是BST中的一个节点，不一定是root

TreeNode findNextLarger(TreeNode node) {}

http://www.1point3acres.com/bbs/thread-212747-1-1.html
一共五轮，可以用白板，准确地说是一面白墙，也可以用chromebook.我基本上都是在chromebook上写的，因为我感觉打字要快多了。于是每一轮面试官都把我给的答案发送到他们的邮箱里了，估计是事后比较方便验证吧。
第一轮，英国人，LC418, 当时给了个O(mn)的解法，后来follow up他说要是m, n 都比较大怎么办，然后我给了个O(m)的解法。

LeetCode 418 - Sentence Screen Fitting

第二轮，美国小哥，第一题问了一个数据结构的题，把一个某种格式的inputstream,利用你设计的数据结构转换成另外一种形式并输出，算法上很简单。我implement完后他看了一下也没有提什么问题就直接复制发送到了他邮箱。
第二题问了H-index，秒掉之后他验证了几个edge case, 找不出问题后 follow up 问算法复杂度多少，我说O(n), 然后他follow up说如果citation 如果本来已经排好序的话怎么做，我说可以用binary search。

第三轮，应该挂在这一轮了，美国小哥，pull char to head, 给两个String anagrams, str1 和 str2,每次只能把str2里的某一个char移到最前面，问最少需要几次这样的操作。比如给的String是 “anagram"和“naagram”,可以把第二个String的第二个‘a’移到最前面，最少操作是1.

我当时给了个BFS的解法，然后感觉他不满意，说是不需要每一种情况都要go through一遍。后来想问他给点提示，但是他和我打太极，说他也不确定。
第三轮我觉得是找 Longest Consecutive Sequence
http://massivealgorithms.blogspot.com/2015/08/jiaxins-leetcode-longest-consecutive.html

第三題我也先想到可以bfs，後來仔細想一下，好像可以先判斷str2中，擁有最長的str1尾端的字串。例如anagram, gramana，那就是str2裡的gram。然後再一個一個把剩下的字都往前推。在推的時候，如果會額外產生match的字串，就要扣掉次數。例如aabaaaa, aaaabaa，str2的b往前移動之後，就會產生額外的matching字串，那就要扣掉那兩個aa的移動次數。每移動一個字的時候，都會增加1個或0個matching字串，但可以都視為增加一個matching字串，因為遲早會增加回來。例如像agagram, ngramaa，matching字串要到移動最後一個a的時候才會一次加三，但遲早都會加回來的。

补充内容 (2016-11-21 13:19):
bfs的話會有O(n!)的time complexity，如果是一個一個移動的話，就是O(n^2)

找longest suffix of str2 and also subsequence of str1可以证明就是最佳解的:
假设对str2经过k次操作后与str1匹配(解一定存在的，例如k=length)，那么就是说有index S = {i1,i2, ...,ik}是[0, N)的subset，使得
1. str2[i1], ...str2[ik]是str1.substr(0,k)的anagram，
2. 并且str2在剩余集合[0,N)-S的字符与str1.substr(k)完全匹配（包括顺序）。
其实若满足条件2的话，条件1自然满足，因为原始str1, str2彼此就是anagram。而条件2的str1.substr(k)就是长为length-k的suffix. 要k最小就是要找最长的满足条件2的suffix.

int minMovesToFront(string& s1, string& s2) {. Waral 鍗氬鏈夋洿澶氭枃绔�,
int maxSuffixLen = 0, i1 = s1.length()-1, i2 = s2.length()-1;
while (i1 >= 0 && i2 >= 0) {
if (s2[i2] == s1[i1]) { maxSuffixLen++; --i1; } . From 1point 3acres bbs
--i2;
} .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
return s1.length() - maxSuffixLen;
}

第四轮，不太确定是哪个国家的，应该是混血，第一题要设计一个list iterator,记得比较清楚的是比如给一个list, 是{1，2，3，4}的话，iterator 给的输出应该是 2，4，4，4意即奇数位表示偶数位的value要重复的次数，input list不一定valid,要handle各种Exception。

第二题也是一个设计题，要判断一个人（node）是否能access一个file, 这个node有两个member，一个是userId, 另外一个是他能access的file的list，但每一个file可能也包含多个其他file。给出思路后没有让实现，然后问了他几个问题就结束了。

第五轮，美国小哥，LC317 变种题，敲代码的过程中大脑一抽把visit过后的点的visit[i][j]写成了false, 被他指出来了，敲完答案和和他一起过了一遍，没有发现问题然后他问了下复杂度，然后复制发到他邮箱了。

面完后的第二周周四HR打来电话，说是有一些Strong data但是feedback的discrepanycy比较大，决定不送HC。

想了一下应该是Longest Consecutive Sequence的变形
找str1里面最长的suffix使得在str2中有最长的Sequence
例如str1 = "abcdefg"
str2 = "eafbgcd"
str1最长的suffx且是str2的sequence的是"efg", 次数就是str.length - 3 = 4
实际上的做法就双指针从str1根str2的尾端往回扫就好了时间复杂度是O(n)

如果直接找Longest Consecutive Sequence的话会因为你只能移动str2导致结果错误. Waral 鍗氬鏈夋洿澶氭枃绔�,
用上面当例子, Longest Consecutive Sequence是"abcd", 得到结果为length - 4 = 3, 但3次移动是没办法让两string相等的

http://www.1point3acres.com/bbs/thread-212589-1-1.html
给一个fair coin，对任意正整数n，如何模拟出1/n的概率。follow up:简要证明，然后写这个程序。
二进制？

这样行吗，取一个数k = ceil(log2(n))，扔k次，把这k次的结果看成一个binary number，这个数小于等于n-1的概率是 n/(2^k)，反复投掷知道这个数小于等于n-1为止，然后再看这个数是否等于0. 证明就是楼上说的条件概率吧
如果投掷k次，把每次投掷的结果看作0或1（正或反），那么投k次的结果就可以用一个k位的二进制数表示，这样会得到2^k个数，而且得到每个数的概率是一样的。但是题目要求模拟1/n的概率，所以就要设法以均匀的概率产生n个数，那么产生其中一个数的概率就是1/n。.

这个方法就是，选一个k使得2^k >= n。然后这样模拟1/n概率：
1. 投掷k次，产生一个数m，范围是0～2^k - 1
2. 如果0 =< m <= n - 1, 停止投掷，跳到3。否则跳回1
3. m等于[0, n - 1]其中任意一个数的概率就是1/n.

P(A=0 | A < n) = P(A = 0 and A < n)/P(A < n) =P(A = 0)/P(A < n) = (1/2^k)/(n/2^k) = 1/n 我的理解是这样，不一定要是0，任何在0和n-1直接的数都可以

是这样的，因为投掷多轮直到结果落在[0, n - 1] 之间为止，所以得到的这个结果是[0, n - 1]中的某个数，在满足了这个条件之后，它是[0, n - 1]中任意一数的概率是1/n。

http://www.1point3acres.com/bbs/thread-204531-1-1.html
面试前，因为房间被占用，所以我们俩在外交流了下。我起初不知道他是第一位面试官，还向他问了面试技巧的guidance。=.=
第一道是把数组向右移k位。我慢慢做，还讲了如果k是negative就意味着像左移。
第二道是找BST第二大的element。用reverse inorder traversal做了。
http://massivealgorithms.blogspot.com/2015/06/algorithm-second-max-in-bst-stack.html

第三道是把c string去除空位。
感觉这一轮应该是hire / strong hire。因为三题都bug-free。
我最怕名企的烙印，之前在亚马逊实习时被印度mentor黑得很惨，面微软时有一轮印度面试官也是百般刁难。
这一轮有可能被黑，大家帮我分析下。

第一题是给一个数组：1，1，7，8，8
1，1是一个pair；8，8是另一个pair。请返回7，因为7仅出现一次。
我说用xor，他说能更快吗？
O(lg n)？怎么可能？后来才问明白pair的元素都是adjacent的。例如两个1都是彼此靠近。但记得很清楚他只说pair，又没说一定要adjacent。
写了个binary search给他。bug-free。

第二题Android Unlock Patterns他从最原本的问题问起：走完9个键盘有多少种可能性。我分析了下，给了9 factorial。
他接着问给个range（例如，4到9）又会有多少种可能性。我分析了下，给了9 * 8 * 7 * 6 + 9 * 8 * 7 * 6 * 5 + ...
他就问了leetcode的版本。我解释了下，然后有趣的事发生了：他不给写代码，说时间要到了。
我感觉有问题，一直不direct的要求，最后还是给了写。说他看错时间了，还有10分钟。
我写得不好，有3个bugs：一个自己发现，一个是漏了个for loop因为误会问题，一个他指出给了几次hint我才答对。=.=

有种感觉被黑，因为写完后找出bug后还有1分钟问他问题。。。最后我还提醒他拍下照。:)

吃完饭他把我带去wrong room。是吃饭前的room，但已经被另一位Google engineer霸占了。
后来他帮我问了coordinator发现地点改了。。
第三轮的面试官也来错地方。。

第三轮、（应该是）华人面试官（有可能是ABC或韩国人）
Rate Limiter，跟leetcode的那题不同，这题如果一秒内超过query per second限制需要wait一下。
给个class
class RateLimiter {
void setLimit(int query_per_second);
void wait();
};
wait()是要有block的semantics。其实这一题打得很不好，在他的提示下找到了要wait多久（有个formula)，最后用了queue给了个O(n)解法。

他接着问O(1)解法。
时间用完了、代码改了好多篇依旧无法找到O(1)解法。。
他给了提示用bucket，我也尝试做了：把queue分为10个部分，每个代表100 millisecond。但有burst时依旧O(N)。
最后第四轮面试官来敲门了，他给了提示说可以把一个bucket内的queries都设为同样timestamp。
我当时才领悟到，原来可以如此。
回家后想了下：O(1)解法不是要牺牲correctness吗？之前有讲到不同granularity，但把bucket内的queries设为同样timestamp不能保证limit正确啊。
他又没说可以不准确，我要怎样想得出啊？？Granularity这个词implicitly imply? LOL
记得去年电话面试Google时面试官有说他想要个更快的但可能会出错的解法，但这轮面试官没说啊。
感觉上这一轮就是一直想O(1)解法，一直判断出还是O(N)。
我一直都在wrong direction，而面试官却一直说嗯嗯嗯。=.=

第四轮、华人女生面试官（应该是中国女生）+ 白人shadow
问题很简单，但这一轮的面试官是我的interview anti-loop。无论如何沟通，她还是无法了解我的approach。。。

给某一天的file，记载着questionnaire回答者的讯息：
{UserId, Timestamp (minute), City}
{100，201608080003，“NY”}
{101，201608080102，“CA”}
{102，201608080102，“CA”}
{103，201608080154，“IL”}
{104，201608080154，“CA”}
Timstamp是有序的。请打印过去一小时的city ratio。例如走到user ID 104要打印：
(101, 3/4)
(102, 3/4)
(103, 1/4)
(104, 3/4)
因为走到104时，user ID 100的entry已经expire。剩下有三个CA，一个IL。

她讲得不清楚但给了类似以上的例子，但我开始时误会了问题。
面试官说timestamp是based on minute的，所以误会timestamp的最后四个号码代表的都是minute（当时想了下60 * 24，一天有1320分钟）。
但其实是小时和分钟。例如201608080003是2016年8月8号00时03分钟。
后来clarify后，慢慢改成用queue + hashmap + hourly city count variable的解法。
解释了好久，面试官依旧不清不楚。说了好多次用queue是为了去除expire的entries。
讨论了好久，她还是在问相似的问题。。
最后没剩多少时间写了下代码，一个loop没counter++，一写完还没来得及查看就立即被她指出。
然后写完queue的代码，她说pop operation后array index会变。我听不明白，跟她解释了许久，她之后才发现我在pop queue。。
我当时心里想：开玩笑吗？我一边写了多行queue的代码，一边讲到口都要沙哑了，之前解释时也提到了queue很多次。
现在因为时间剩不多，字体有点乱，写了queue的pop operation，怎么array index会变啊？

看来我跟面试官沟通不来啊。如果不是有shadow，我会要求用中文跟她解释。=.=

结束前我问了下engineer如何合作解决棘手的问题，她答非所问，好像在说自己不知道。我心里都凉了。
旁边的白人shadow立即圆场，回答了我的问题，说会有meeting什么的。
我真的无话可说。白人shadow能明白我说的英文，但华人面试官听不明白啊。。

我不觉得面试官有黑我的意思，但这种程度的沟通等于没戏了。。
想不到准备了5个月，竟然栽在communication。。
(1) 如果stuck，一定要更加积极问hint。有些面试官在你in the wrong direction时也相当被动，一定要积极用example来搞清楚问题。
(2) 沟通很重要。不管面试官英文好不好，都要有能力让ta明白。

第四轮如果input是array或者list可以直接用two pointer？
我觉得two pointers可以，但还是要个hashmap。

block的semantics是指在限定的时间内如果qps超过就不能再query。
不是考多线程。
http://www.1point3acres.com/bbs/thread-211139-1-1.html

第四轮：这题真是前所未见的，
题目：double[][]矩阵，值表示高度，所以是一个3D的地图。现在无限远处平行光射入（任何角度），
求矩阵上那些点被遮盖住了。懵逼。开始各种分析，我以为是设计题，就3D阴影建模。
正要开始写class的时候，然后得到hint：从每个cell看向太阳方向，所以想到现在2D上，
对一条光路ax+by=0，求哪些cell相交（这个挺难算的，在hint和反复的question下，
我最后给出了三条平行线算计算相交cell，面试官表示肯定）。
然后跟面试官negotiate得到只需要考虑中心点被覆盖，同时相交cell之间的距离就近似成中心点的距离
（因为要计算tanA*distance(p1,p2)得到高度）。。。。总之到最后是给出了一个算法，
写了一点点中间步骤的代码，但是整个代码是没写的。结束的时候考官问我感觉怎么样，
我说没有想到是这种数学题，他说我们希望看到你分析这个题然后写成代码的整个过程，
我说可惜我还是没写完代码呀，他点点头说嗯（我就觉得完蛋了）。
最后朋友圈大神说这是计算机图形学最后几章的问题，什么z buff scan算法。。。。

最后一轮竟然考gpu算法。玩游戏的知道关了阴影特效会流畅很多就知道这个复杂度挺高的了。

好的就这样，等待HR反馈。。。。我个人觉得已经发挥我所有实力了，但感觉依然有风险。。第三轮followup不好，
第四轮只分析出来算法没写出代码。

第一轮：topological sort。我写了上百遍了（DFS wik版本），但是华人大叔没太看懂为什么有两个visited set，所以解释了好久。

第二轮：
int[][]矩阵，求是否满足性质：左上角到右下角的斜线上的值都要相等。比如(0,1)(1,2),(2,3)这些要相等。小伙伴告诉过我这题，所以我知道follow up是矩阵很大，每次只能读一行怎么办，
所以我一开始就写了两行两行比较的算法，
面试小哥有点蒙蒙，依然也给了这个follow up，秒了。

然后还剩二十多分钟，小哥就给了第二个follow up：现在一行都太大没法读进来，
但是可以允许算法不是100%准确的。然后我也不知道为什么灵光闪现，想起来大四的时候跟实验室同学聊天知道的
一个压缩矩阵保持feature的方法，然后给出了：每次取出matrix的一小块，
算一个signiture（比如乘一个vector就能压缩到一维向量），然后整个矩阵就可以压缩，保持一定的feature，
最后用前面的算法做，有False positive，但是满足性质的matrix一定是返回True的。
小哥说每次读一小块太昂贵了（因为有不同行，从disk的一个条带上读的话跨越太多），
只能一行一行读，每次读一小点。我说那就能读多少读多少（比如读N），
signiture简单乘上一个固定的vector（大小N）压缩成一个int就好了，
这样整个大矩阵也可以每行一点一点压缩（每行压缩的时候要有offset，因为是斜着比较的），
如果压缩一次不够的话，还可以递归压缩，直到内存足够读入一行为止。最后小哥让我写代码，
写完表示非常非常非常满意。

第三轮：LC394，剩十分钟follow up是反过来encode，求最短encode（跟我说前面那个是warm up，这才是真题）。
懵逼，给了个贪心+memory的算法（代码非常乱），也不知道能不能得到最优解。没做出来。。。
最后结束的时候她说这题很难很难，让我don't worry，用DP做（分析题目的时候我试了一下，她没有hint所以我没继续下去），
然后我才想到用dp[k][i][j]做应该可以。。。但也没时间写了。。

我觉得brute force都很难想。。主要是S[i..j)加上S[j]的时候，要往回check是不是可以encode挺麻烦的。。我当时想的是从j到i检查，
每次算[k,j]是不是S[i,k)的结尾的substring。。这样复杂度非常高。。但也没想到别的办法。。。dp[k][j]是这样想的，
k代表pattern的长度，一段一段的去检查（因为可以压缩的pattern是相连的），但是也没想出具体要怎么算。。

求问楼主，第三题的follow up的话，如果是输入是“accaccacc",输出应该是3[a2[c]]还是3[acc]呢，第二个其实更短一些~~~

第二个，要包括中括号的长度

dfs加一个memory储存见过的string大概就变成dp了吧

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

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

Given a word, find the minimum number of steps required to convert word to a word with SS pattern. (each operation is counted as 1 step.)

e.g : cdcc -> cdcd 或者 ccc ->cc

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

LC 72变种，SS pattern我现在都没搞清楚什么意思，大概就是你输出的word里只能是abababab,dcdcdcdc这种类型的？Anyway，DP学得很烂，只把edit distance重写了一遍，SSpattern当时死活听不懂，中国大哥表示很无奈。

第一题brute force肯定可以，分成两个substring，作为parameter调用edit distance。但是感觉上可以用KMP。

第二题，

给你好多点的坐标((0,1),(2,1),(4,1)(3,6)(7,9)(5,0)(0,6)(8,3))，问你这些点能组成的长方形中，面积最小是多少？

GG，不会，扔了个brutal force的4个for loop在上面，然而并没有写完。

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

1. 已知一个字符串，由圆括弧()们组成，括弧之间可以嵌套并且可以在一层括弧内有多个括弧，例如(()()), ( ( () ) ( (())() ) ).要求简化括弧使之成最简形式。简单说，((()))这样单个括弧外面又是单个括弧的应该简化为(), ()()这种并列关系就保留原样

第一题用stack过一遍就可以了吧

2. lc #22

二面：
用程序算Android锁屏界面一共有多少种画法。
然后问了我写的一个helper function怎么测试。我听得一脸懵逼一直不知道在告诉我答案还是问我问题

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

第二題基本上是edge length 為1的graph. Shortest path 經典解法是bfs

3. 设计一个class，用array来保存整数。比如1829保存为［1, 8, 2, 9 ], 再写一个increment 的方法，往里面加数字。第二题让我写一个 2D matrix， reverse each row。

4. 设计一系列函数（is_used(), set_used(), release_used(), next_available()），用来保存所有被占用的电话号码。我说用hashset保存占用的号码。面试官说ok，

Follow up：找next_available需要 o(N), 如何improve。我说可以设计把所有号码段分成K个区域，用一个array来存已经使用的号码个数，这样在找next available时一个先找一个没用完的区域，在往里找，达到O(N/K), 如果每个号码区域再向下分sub 区域，最终能达到 O(nlogn), 面试官说可以。

Follow up 说如果希望next_available达到O(1), 需要怎么做。一开始说用两个hashset分别存 used and unused 号码，但被面试官点破说hashset找任意element也需要O(N). 说可以用hashtable 加 linkedlist的数据结构，面试官说可以。之后说还有10分钟，让我写了leetcode 的spiral matrix，10分钟内写完

第四题可以hashtable加queue

5. Find relative in archive. 给你一系列child －> parents 关系的dict (A - > (mother1, father1), B -> (mother2, father2), mother2 -> (mother3, father3))，写一个method，决定两个人是否有关系relative。先问我什么数据结构，我说用tree，面试官说可以，我画图设计时发现不行（两个node一个有相同的child），说该用graph，面试官说可以。之后写了个DFS的算法找各自的ancestry，让后比较。写完后面试官问可以怎么改进，我说可以用BFS同时search两个人，让后再每一轮BFS时比较，面试官说可以，写了代码

第五题直接union find dfs bfs 你这样做太复杂

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

1. 不记得太多了，有一道 Leetcode 17。

2. 开放性题目。面试官在黑板上画了一个迷宫，用bar做边界和隔板。有隔板的地方不能通过，从一个方向走只有碰到隔板和边界才会停下来。让设计一个算法找出起始点到终点的path。上来先说用什么来数据结构来保存迷宫信息，我说用hashtable，面试官说OK。之后我说这题需要用DFS来求解，面试官问用什么方法，说了半天才知道他想问我可以把迷宫当成graph。让后把example化成了graph的形式，让我写了dfs的算法。之后有讨论了DFS和BFS在这个问题上的优缺点，我说DFS找一条路径较快，他不认同。这轮总体答的优点僵。

3. 设计一个class，用array来保存整数。比如1829保存为［1, 8, 2, 9 ], 再写一个increment 的方法，往里面加数字。第二题让我写一个 2D matrix， reverse each row。

4. 设计一系列函数（is_used(), set_used(), release_used(), next_available()），用来保存所有被占用的电话号码。我说用hashset保存占用的号码。面试官说ok，Follow up：找next_available需要 o(N), 如何improve。我说可以设计把所有号码段分成K个区域，用一个array来存已经使用的号码个数，这样在找next available时一个先找一个没用完的区域，在往里找，达到O(N/K), 如果每个号码区域再向下分sub 区域，最终能达到 O(nlogn), 面试官说可以。Follow up 说如果希望next_available达到O(1), 需要怎么做。一开始说用两个hashset分别存 used and unused 号码，但被面试官点破说hashset找任意element也需要O(N). 说可以用hashtable 加 linkedlist的数据结构，面试官说可以。之后说还有10分钟，让我写了leetcode 的spiral matrix，10分钟内写完

5. Find relative in archive. 给你一系列child －> parents 关系的dict (A - > (mother1, father1), B -> (mother2, father2), mother2 -> (mother3, father3))，写一个method，决定两个人是否有关系relative。先问我什么数据结构，我说用tree，面试官说可以，我画图设计时发现不行（两个node一个有相同的child），说该用graph，面试官说可以。之后写了个DFS的算法找各自的ancestry，让后比较。写完后面试官问可以怎么改进，我说可以用BFS同时search两个人，让后再每一轮BFS时比较，面试官说可以，写了代码。

总体来说LA office的面试还属于比较简单的，没太多难题，主要在于和面试官交流。LA office虽然比MTV比小不小，但离Santa Monica沙滩很近（据说就两条街），大约7動office，基本设施gym也都有。准备面试时基本靠地里涮面积，现在也来出份力。希望自己能拿到offer，地里朋友也加油。

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

1. LC 249
2. 8*8国际象棋棋盘，给定Knight的起始和结束位置，输出最短的从起点到终点的路径。
需要找到路径，不是长度

https://en.wikipedia.org/wiki/Knight_(chess)

The knight move is unusual among chess pieces. When it moves, it can move to a square that is two squares horizontally and one square vertically, or two squares vertically and one square horizontally. The complete move therefore looks like the letter L. Unlike all other standard chess pieces, the knight can 'jump over' all other pieces (of either color) to its destination square

两题都是瞬秒了，然后面试官都说有小BUG，遂讨论之，都是面试官想错了...
做完两道题还剩15分钟，聊天十分钟，结束面试。

Round 2
1. Valid Number
2. LC 356, 但是直线可以是任意直线

我当时给出的解是对所有可能的两点间的直线分组，然后判断是否有一组包含所有点..

挂掉电话以后，想到了解... 应该是对第一个点和所有其他点，求垂直平分线，然后判断其他点的距离是不是对称分布在直线的两端，奇数个点的话，可能第一个点在对称轴上，这种情况需要另外再选其他端点

当时给出的解法是，对于每一个点对，计算其垂直平分线，用约分的(a,b,c)表示唯一的直线ax+by+c=0，对于所有n^2的点对，用(a,b,c)作key来用hashtable分组，最后看看是不是有哪一组包含所有的点。现在想了下似乎也没错？不知道各位怎么想...

楼主任意直线怎么做？我想到的时候对于一个点A,遍历点集合，组成pair以后，pair的中垂线是候选直线，然后用o(n)的时间看是否ok.总时间复杂度n^2

我昨晚仔细思考了这个问题，你的这个做法是我想到的第二个做法。但是如果允许点在对称轴上的话，两个做法都不行。

试想，所有的点都在一条直线上，而且关于其重心不对称，那么是没有任何中垂线能对称分割的。所以应该是p1和任意pi的中垂线，以及连线作为候选，来判断是否可行

是的，我的确没有考虑到p1在对称轴的情况。

我觉得"p1和任意pi的中垂线，以及连线作为候选，来判断是否可行" 这个思路会有一个case过不了，不知道我理解你的意思对不。比方说p1 = (1, 0), p2 = (2, 1) p3 = (2, -1) 这时p1在对称轴上，但是p2 p3和p1的中垂线或者连线都不是对称轴。

我想解决的方法是选两个点p1 和 p2，分别对剩下的点做中垂线检验。如果这些都不满足，那么如果存在对称轴，只有可能是p1 p2均在对称轴上，再看p1 p2的连线是否是对称轴。

这样总复杂度还是n^2,但是计算量变成两倍了。

你的解法是不是两个点 pi, pj求中垂线，这样的话复杂度是不是(n^3) ?

求中垂线是n^2, 然后对每条中垂线的验证是o(n).这个是不是应该是o(n^3)?

如果是对p1, pi 中垂线，然后验证p1, pi的连线的话这个是o(n^2)。但这个是不是少考虑了一种情况？

也就是p1自己在中垂线，然后其他点以这条对称。举个例子也就是p1, p2, p3. 三个点，然后p2, p3, 对称，p1在p2,p3的中垂线上。比如p1(0, 1), p2(-1, 3), p3(1, 3).. visit 1point3acres.com for more.

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

第一题输入一个String S（只包含- 和字母）和 int K，重新组织String，从末尾开始每k个字符加一个”-“。O（n）时间

第一题输入一个String S（只包含- 和字母）和 int K，重新组织String，从末尾开始每k个字符加一个”-“。O（n）时间
我不确定这个输入的string可不可以pass by reference. 如果可以的话就可以O(1)空间（in place swap）.
我的想法：对于string& s用一个slow index从右向左扫描(slow = n-1; slow >= 0; slow--)，再用一个fast index寻找可以和当前的s[slow]交换的前面的char的位置：
1. 当slow的位置不是(k+1)的整数倍时：若s[slow]是字母，忽略；否则和slow前的最后一个'-'交换；
2. 当slow的位置是(k+1)的整数倍时：若s[slow]是‘-’，忽略；否则和slow前的最后一个字母交换。
注意有可能给的input string根本就无法完成要求，那么我的默认就是当找不到可以交换的char时就直接返回了，这样尽量把右边可以交换的string部分整理好就行了。例如 "qwd--rgf---r" k = 3, 返回 "---g-wdr-gfr"
该算法还保持了字母char的相对顺序在调用后是不变的。O(N)时间（应为slow, fast都至多扫描string各一遍），O(1)空间（若string pass by value or const，重新创造string空间O(N))

void rearrangeString(string& s, unsigned int k) {
int n = s.length(); //if (k == 0 || n < 2) return;
int slow = n; // current index of char to check
int fast = n - 2; // last index of char before current to swap with
while (--slow >= 0) { // scan s from right to left
// not at multiple of (k+1)th position, but encounter '-'
if ((n - slow) % (k+1) && s[slow] == '-') {
// find last index of letter char before current to swap with
while (fast >= 0 && s[fast] == '-') fast--;. 1point3acres.com/bbs
if (fast < 0) return; // if no desired char, we have to quit
swap(s[slow], s[fast]); fast--;
}
// at multiple of (k+1)th position, but encounter a letter char
else if ((n - slow) % (k + 1) == 0 && s[slow] != '-') {
// find last index of '-' before current to swap with
while (fast >= 0 && s[fast] != '-') fast--;. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
if (fast < 0) return; // if no desired char, we have to quit
swap(s[slow], s[fast]); fast--;. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
}
}. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
}

public static String convert(String s, int K){. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
StringBuilder sb = new StringBuilder();
for(char c : s.toCharArray()){
if(c != '-'){.1point3acres缃�
sb.append(c);
}
}
int len = sb.length();
while(len - K >0){
len = len - K;
sb.insert(len, '-');
}
return sb.toString().toUpperCase();. 1point 3acres 璁哄潧
}.

Google OA 变题了，说好的路径呢

请问第一题从末尾开始取 K个字符只能是K个字母是吗？

没错！只能k个不多不少

国女，题目是给一2D-matrix，找从左上travel到左下的最短路径，每次只能move到下一个row的正下以及旁边，比如从(i, j) 到 (i + 1, j - 1) 或 (i + 1, j) 或 (i + 1, j + 1)，求可以从左下角到右下角的path的个数. dp
这轮面ML，俄国老毛子，问了一堆简单的ML的问题，最后说要出个写code的题，问我做分类email spam，有很多boolean features，要按什么顺利问问题保证问的问题最少而能够判别出email是不是spam，我说用decision tree。感觉面试官不是很是很满意，后来让我implement 一个decision tree，也是无语了，凭记忆写了下，写的肯定有bug。
这轮是个慈祥的美国大叔，很nice，先问了一堆小问题，然后出了个类似 word break的问题， dp解之，然后还有一段时间，出了个当时想的问题，说怎么查询UTF8。这轮感觉聊得比较好。
出了个insert circular sorted list. 写了出来，被指出有个小bug，改了下，就结束了。
另外一个印度哥们，出了个挺简单的题，判定一个矩阵是不是Toeplitz matrix（大家可以google），我先说了个用hashmap的算法，虽然知道有空间O（1）的算法，特地问问面试官要不要写出来还是要更好的算法，面试官说要写出来。后来就写出来了，后来又让些空间是O(1)的做法，写了下，当时脑袋不太转了其实很简单，写出了bug。然后又讨论了python怎么存矩阵的问题。最后follow up是如果是stream的时候怎么弄，我说要用que，然后就没时间写了，经验是不要把时间浪费在次优解上，直接上最优解，可以节省时间

http://massivealgorithms.blogspot.com/2016/08/find-if-given-matrix-is-toeplitz-or-not.html

For each element of first row and first column(or last row and last column) in the matrix, we check if descending diagonal starting from that element have same values or not. If we found any diagonal having different values, we return false.

总结是题都不太难，但是没见过的题要写无bug还是要多加训练，感觉有点准备不太足。另外楼主用的是python，写起来简单，但是在白板上注意各行indent

https://en.wikipedia.org/wiki/Toeplitz_matrix

常对角矩阵（又称特普利茨矩阵）是指每条左上至右下的对角线均为常数的矩阵，不论是正方形或长方形的。

a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:

\begin{bmatrix} a & b & c & d & e \\ f & a & b & c & d \\ g & f & a & b & c \\ h & g & f & a & b \\ i & h & g & f & a \end{bmatrix}.

Any n×n matrix A of the form

A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\ldots &\ldots &a_{-(n-1)}\\a_{1}&a_{0}&a_{-1}&\ddots &&\vdots \\a_{2}&a_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &a_{-1}&a_{-2}\\\vdots &&\ddots &a_{1}&a_{0}&a_{-1}\\a_{n-1}&\ldots &\ldots &a_{2}&a_{1}&a_{0}\end{bmatrix}}

is a Toeplitz matrix. If the i,j element of A is denoted A_i,j, then we have

A_{i,j} = A_{i+1,j+1} = a_{i-j}.\

A Toeplitz matrix is not necessarily square.

http://www.1point3acres.com/bbs/thread-213095-1-1.html
1. 给一个string 比如说"abc", 再给一个list<String>，里面都是原来string的substring, 比如 {“ab”, " bc"} 这种的，然后让你返回一个string, 把list里面出现过得string 用 tag 圈起来，比如这个例子的结果就是 abc

再个几个例子， "abcab", {"ab"} return abcab
 "aaaab " {"aaa", "aab"} return aaaab

第二个面试官感觉资历很久了，一开始聊简历的时候也比较nice, 后来做题的时候，
楼主水平有限，一开始都没有理解清楚题意，来来回回纠结半天，最后可算是写完了，但是浪费好多时间，好惨

2. 题意大概是从 /a.html 可以去 /b.html, /c.html, 从 /b.html 可以去 /d.html, /e.html ,
从 /c.html 可以去 /a.html, /b.html, /f.html, /g.html, 从 /f.html 可以去 /g.html
如果start 从a.html开始访问的话，最后最多可以访问几个网页....这个例子应该返回7.

楼主用dfs做的，但是想的太复杂了，最后问了面试官几个问题也就草草结束了，诶，，，，，

http://www.1point3acres.com/bbs/thread-213111-1-1.html
第一轮，二维坐标系给一堆点，找出这些点能形成的最小矩形的面积。
矩形是平行于x轴y轴的
我是先把所有点存起来，然后每次遍历找两个点作为对角线上的两个点，然后算出另外两个点坐标，看在不在集合中

第二轮，珠宝游戏。5种珠宝，10*10方格。规则是同样的珠宝不能连续放3个（横着3个，竖着3个）。
要求初始游戏，所有珠宝的位置随机，种类也随机，放满棋盘

第三轮，LC394。虽然原题，但这轮的面试官一直在各种给我挑错说某些index有问题，花了很长时间带他从头walk through他还将信将疑。说实话一般g的面试官都是比较看重思路的，但是这个人一直在死扣代码，我真是不理解。。。
第四轮，四位数字密码箱。每一位0-9，假如密码是3456，那么输入3456可以打开密码箱，输入123456789....也可以打开密码箱，因为规则是只要输入的密码串中包含正确密码就能打开。要求是设计一个最短的密码串，能打开所有四位数字密码箱。不会。。。

第四题是不是traveling salesman problem? 每个4位密码是一个graph node，node之间的距离是他们之间overlap的位数。求最短superstring也就是最短的所有node走过一遍的path。NPC。。。.

应该跟这个差不多，以前听过bioinfo的课对这个问题挺有印象https://www8.cs.umu.se/kurser/TDBAfl/VT06/algorithms/BOOK/BOOK5/NODE209.HTM

第四题直接backtracking啊...直到找到最短的字符串遍历完所有可能

http://www.1point3acres.com/bbs/thread-168439-1-1.html
第一题：morse code encode
给一个字典或者hash_map, 对现存的字符串进行加密，这个应该很简单。
第二题：decode morse code ，all possible solutions
这个题需要重新建一个逆向dict 或者hash map 来方便查询，我的解题思路就是递归。

public class MorseEncodeandDecode {
HashMap<String, String> hm;
HashMap<String, String> hmd;
public MorseEncodeandDecode() {
hm = new HashMap<>();
hmd = new HashMap<>();
hm.put("A", ".-");
hm.put("B", "-...");
hm.put("C", "-.-.");
hm.put("D", "-..");
hm.put("E", ".");
hm.put("F", "..-.");
hm.put("G", "--.");
hm.put("H", "....");
hm.put("I", "..");
hm.put("J", ".---");
hm.put("K", "-.-");
hm.put("L", ".-..");
hm.put("M", "--");
hm.put("N", "-.");
hm.put("O", "---");
hm.put("P", ".--.");
hm.put("Q", "--.-");
hm.put("R", ".-.");
hm.put("S", "...");
hm.put("T", "-");
hm.put("U", "..-");
hm.put("V", "...-"); 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
hm.put("W", ".--");
hm.put("X", "-..-");
hm.put("Y", "-.--");
hm.put("Z", "--..");
hm.put(" ", "/");
for (String k: hm.keySet()) {
hmd.put(hm.get(k), k);
}. visit 1point3acres.com for more.
}
public String encode(String s) {
StringBuilder sb = new StringBuilder();
for (char c: s.toCharArray()) {
sb.append(hm.get(String.valueOf(c)));. more info on 1point3acres.com
}
return sb.toString();
}
public List<String> decode(String s) {
if (s == null || s.length() == 0) {
return null;
}
List<String> ret = new ArrayList<>();
String list = "";
enumerate(s, ret, list, 0);
return ret;
}. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
public void enumerate(String s, List<String> ret, String decode, int start) {
if (start == s.length()) {
ret.add(new String(decode));
return;
}
for (int i = start; i < s.length(); i++) {
if (hmd.containsKey(s.substring(start, i + 1))) {
decode += hmd.get(s.substring(start, i + 1));
enumerate(s, ret, decode, i + 1);
decode = decode.substring(0, decode.length() - 1);
}
}
}. more info on 1point3acres.com
.1point3acres缃�
public static void main(String[] args) {
MorseEncodeandDecode m = new MorseEncodeandDecode();
System.out.println(m.encode("APPLE"));
for (String s: m.decode("---------------")) {
System.out.println(s);. 1point3acres.com/bbs
}
}
}. from: 1point3acres.com/bbs

第二面：
Interviewer: 纯美音小哥
第一题：unique words abbreviation leetcode 题
第二题：generate all words abbreviation leetcode follow up

第一面讨论我的项目的时候，拓展的比较宽，比如讨论到大数据存储，搜索等。我答的马马虎虎，因为现在的项目并没有可靠的方案来解决他提出的问题。第二轮谈的比较high，介绍的比较详细点，最后问得问题都把美音小哥逗乐了，不知道他对我影响咋样。题目都是很基本的题，刷题还是需要总结自己的刷题套路，把相关的题目系统的刷一边。在头脑中给所有自己做的题留个关键字进行解题思路搜索

开始的时候有可能根据你的简历拓展一些问题，然后写代码的时候keep talking，把自己的想法说出来。短暂的沉默可以的，但是不要一直一句话的不说。怎么克服紧张这个就需要自己慢慢调节了。

http://www.1point3acres.com/bbs/thread-210835-1-1.html
4轮的题目好像都没怎么见过啊，说好google喜欢考DP的，也没有。。。

一个系统不定期抛出错误，每次有错误时会调用一次alter(int timestamp)函数来检查在过去的period时间内出错数是否超过max_e，alert返回bool。可以认为当且仅当有一个新错误，alert才会被调用。.
比如，出错时间为：1,3,3,8,10,13,13,13,20。给定max_e = 4, period = 5，那么每次出错后调用alert的结果依次为：F,F,F,F,F,F,T,T,F。第一个13返回F，因为8-13这段时间内一共3个报错，后面两个13返回T因为分别有4/5个报错。
可以用queue，每次alert就push，然后把过期的错误pop，然后检查size。

由于可能有duplicate，用hashmap存次数，遇到重复的就不push。
代码也是磕磕绊绊，两三个bug在提示下改对了。分析时间空间复杂度，然后分析平摊情况下的复杂度，这里也是给了提示才说出来。

follow up：上面的解法对小period大max_e比较友好，如果period大，而max_e小怎么做？我在面试官说out of time之后才想到，赶紧说只在queue里存max_e大小的元素，然后检查最早的元素是不是超出period。
出题，给matrix，里面只有1/0，至少一个是0。返回一个matrix，每个位置，如果原来是0，返回0，如果原来是1，返回走多少步可以到最近的0。

比如：
1 0 1
1 1 0
0 1 0

返回：
1 0 1
2 1 0
0 1 0

没什么好办法，DFS，复杂度O(n^4)。后来想了想好像有个bug，但面试官当时也没指出来。
multi-end bfs

进来直接出题，给一个matrix of char，只有'-', 'o', 'S', 'X', '-'表示path，'o'表示wall，求'S'到'x'的最短步骤。

比如
o o - o
S - - -
o - o X
o - o o

BFS，不过我做BFS的套路估计小哥没见过，让我解释了一下怎么work的。最后应该是认可我的方法，然后说用queue怎么实现。代码还是有bug，最后改对了。
- ask whether we can change input

做BFS的时候，我把visited位置标记为'*'，小哥说不改原来的matrix，也不新建matrix，怎么搞，那就用hashtable。小哥就顺势问坐标怎么hash。
又问，如果坐标范围很小，比如x在[x0, x1]内，怎么hash。

进来说终于到最后一轮了，人挺nice，还跟我客套了一会。

把一个bit image存在byte array里，比如：
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
就是
0x01 0x02 0x04 0x08

要求左右翻转，得到
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0

函数签名：void flip(int8 *image, int width, int height)

做法是row by row，每个row，用2个pointer相遇，先flip byte，然后swap。每个byte，写个函数做flip。

复杂度是O(N)，不能更好了。

follow up：怎么parallel优化，这里每个row可以独立处理，每个pair of byte可是独立，这两个比较naive。但是byte flip就不懂了，最后讨论了一下写了些公式，但我还是没看出怎么能比原来做的好。

http://www.1point3acres.com/bbs/thread-211354-1-1.html
第一轮： lc 247, 248.
247 Strobogrammatic Number II
246 Strobogrammatic Number
第二轮 : 给一串电话号码, 一个number 和字母的mapping，Map<Integer, List<Character>> map, 和一个dictionary， Set<String> dict. 输出所有可能的在dict里的英文单词。

第三轮： 1. word search. 2. open ended question, mosaic pictures, 怎么用一些小图片拼成一个mosaic pictures。
第四轮： sliding maze。一个迷宫，一个球，球一直走直到遇到障碍物才能停下。问这个迷宫是不是solvable， followup 找最短path

迷宫那题是面经题，就是给一个球，一个起点，一个终点，有四种操作，up/down/left/right, 但球会一直走知道碰到一个wall。然后找从起点到终点的最短路径。要自己先定义maze，我是用一个三维数组来表示迷宫
因为一个cell有四个边，需要用三维数组来表示哪一条边有墙。。。

LZ 请问下迷宫这个题假如已经表示了墙的限制条件（我想可以用一个四位的二进制数表示嘛？每个位置都有一个数，表示四个方向能不能走），球走迷宫，跟正常的BFS走迷宫有啥区别吗？还是就是一样的

第五轮：给一个数据结构
class Purchase{
int id;
int val;
Purchase previous;
}
每个节点指向自己的parent
输入是List<Purchase>, 打印每个节点的及其子节点的value。
Example：
 Node1, 1
 / \
 Node2, 2 Node3, 4
 /
Node4, 1
输出
node1, 8 Node 2, 3 Node 3,4 Node4,1

最后一问咋样o(n)? 从下往上是nlogn吧难度用hash表把父亲节点转换成children 节点这样可以o(n) 肯定有别的o(n)方法求教

可以先生成一个purchase 和 in-degree 的map，然后把leave 节点放入一个queue里，然后更新这个map，找到新的leave
Good 从下往上bfs 确实好只想到dfs了

http://www.1point3acres.com/bbs/thread-212722-1-1.html
有一条公路，长度是m, 中间有k个加油站，由此我们可以得到一个加油站之间的最大距离，然后给你一个数t，这个数代表增加的加油站的数量（往里面插入），求使得加油站之间最大距离变得最小的值，返回这个最小的最大距离。感觉应该是个动态规划的问题

假设有条公路长度为500m，在0,100,200,300,500处有加油站，我们可以得到最大距离是200(300 - 500)。然后我们往里面插入3个加油站，任意位置都可以，求加油站间距最大值的最小可能值。比如我们先插入到350，那么最大距离就变成了150。

http://massivealgorithms.blogspot.com/2016/10/leetcode-410-split-array-largest-sum.html

第一题怎么感觉是维护一个最大堆，保存各个加油站之间的距离。。。每次加入一个堆，就把取出堆顶maxD，然后再把maxD/2或maxD/2+1放进堆里。。。
第一题直接这样做是不对的，我一开始也是这么想的，小哥说不对，但是没给提示。你可以举个例子看看。

第一题贪心算法是不行的，比如两个间距1，9。要求再加2个点。最优结果应该是3，但贪心算法结果为4。因为贪心算法每次只考虑一个点，无法预见二等分以上的情况。

想了一下好像可以根據這個為基礎得到正確的解法等等貼我的想法

DP基本相当于暴力解了,correctness比较显然但效率低。
Max Heap在每次加入点后及时优化自动调出当前的max subinterval（max heap）, 高效率。就是correctness要证明还真不容易。

这个heap的复杂度是O(k*logn)吧，虽然应该也没什么差别. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴证明的话induction可以更清晰一些，可以直接比较最后答案得到结论，不过应该都差不多 DP的话不单调优化确实比较好想，我觉得两种算法都很不错，当然从复杂度考虑确实heap更巧妙一些

第一题：这个题应该可以DP: 假设delta[]是相邻加油站的间距，并且是sorted（这个题与顺序无关，所以若不是sorted那么排序即可，i.e.,sorted假设不失一般性）。设dp[n-1][t]:=对delta[0,...,n-1]增加t个加油站所得到的最小最大间距，那么对delta[0,...,n]时，在delta[n]中必然至少放一个加油站才能让minMax最小，若在delta[n]中放i个(0<i<=t)，那么自然在delta[0,...,n-1]中放了t-i个，所以转移方程就是
dp[n][t] = min(dp[n-1][t-i], delta[n]/(i+1)) 对 0<i<=t求最小。注意到dp[][t-i]对i是一定单调递增，而 delta[n]/(i+1)对i是一定单调递减，所以在[0, i)范围对i binary search求最小（即dp[n-1][t-i]与delta[n]/(i+1)最接近时最小）。时间复杂度O(n*t*log(t)). 不知道还有没有更快的。

// assume delta is sorted and delta[] > 0.0. from: 1point3acres.com/bbs
double minmaxDelta(vector<double>& delta, int t) {
int n = delta.size();
// prev[tt]: minmaxDelta if adding tt points to delta[0,...,nn-1].鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
// cur[tt]: minmaxDelta if adding tt points to delta[0,...,nn]. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
auto prev(vector<double>(t+1)), cur(vector<double>(t+1));
for (int tt = 0; tt <= t; ++tt) prev[tt] = delta[0]/(tt+1); // initialize prev.鏈枃鍘熷垱鑷�1point3acres璁哄潧
for (int nn = 1; nn < n; ++nn) {. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
cur[0] = delta[nn]; -google 1point3acres
for (int tt = 1; tt <= t; ++tt) {
int L = 0, R = tt-1;
while (R - L > 1) { // binary search to solve delta[nn]/(tt - i + 1) == prev[i]
int mid = L + (R-L)/2, i = (int)delta[nn]/(tt - mid + 1);. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
if (i > prev[i]) R = mid; else L = mid;. Waral 鍗氬鏈夋洿澶氭枃绔�,
}
cur[tt] = min(max(prev[L], delta[nn]/(tt-L+1)), max(prev[R], delta[nn]/(tt-R+1))); . from: 1point3acres.com/bbs
}.1point3acres缃�
for (int tt = 0; tt <= t; ++tt) prev[tt] = cur[tt]; // update prev[]. visit 1point3acres.com for more.
}. 鍥磋鎴戜滑@1point 3 acres
return cur[t];
}

一样维持一个最大堆里头放的结构类似这样
class Interval{
int numberAdded;
int distance;
}

numberAdded是“已经在这个区间加入的加油站的个数” 一开始所有都预设为0
distance就是形成著个区间的两个加油站之间的距离

最大堆依照(distance/(numberAdded+1))做比较
每次poll堆顶的Interval出来把该Interval的numberAdded+1, 直到加入了k个加油站
此时堆顶的(Interval.distance/(numberAdded+1)) 就会是答案

补充内容 (2016-11-21 15:02):
堆顶poll出来, numberAdded+1之后还要放回堆里

2. 印度小哥，上来先问了问一个数组全是0，1，应该怎么sort. (bucket sort/ counting sort).
- dutch flag
然后问题： Candy Crush. 假设要设计一个这样的游戏，我们有4种Candy, 然后有一个board(n * n), 规定在任何一行和一列上不能出现连续的3个相同的Candy, 如何设计这个游戏版。这个游戏版是用于游戏的初始化，所以每次要尽可能的使版面随机，并且满足限制条件。

第二题和楼主一样，不过是3种糖果，然后follow up是如何初始化使board一定有可以用一步可以消的棋子(初始化完成后不能直接死棋).... 讨论了很久，但是还是没回答出来，最后面试官说的方法挺tricky的

第二题我的方法不知道对不对，就是建一个VISITED数组，然后用random()函数随机取出一个candy, 然后以它为基准上下左右看符不符合标准，不符合就重新在剩余的set中随机取出一个。他没有说不对，但是我感觉概率上还是不够随机

第二题candy crash: 这个好像就是随机的一行一行从左向右生在board上成均匀随机数{1, 2, 3, 4}。在位置(i,j)时，同时检查若纵向(i-1,j)与(i-2,j)的candy相同，那么(i,j)不能放这种candy；同理对横向(i,j-1), (i,j-2)同样处理。将不允许放的candy从{1, 2, 3, 4}去除然后再均匀分布生成。

// candy at cell[i][j] could be 1, 2, 3 or 4.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
vector<vector<int>> getRandCandyBoard(int n) {
vector<vector<int>> board(n, vector<int>(n)); 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
// options[i][i]: candy options if candy i and j not allowed: O(1) time/space
vector<vector<vector<int>>> options(n, vector<vector<int>>(n));
for (int i = 0; i <= 4; ++i)
for (int j = 0; j <= 4; ++j) {
for (int k = 1; k <= 4; ++k) if (k != i && k != j) options[i][j].push_back(k);
}
// O(n^2) time-google 1point3acres
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
int vert = 0, hor = 0; // not allowed candy
if (i > 1 && board[i-1][j] == board[i-2][j]) vert = board[i-1][j];
if (j > 1 && board[i][j-1] == board[i][j-2]) hor = board[i][j-1];
board[i][j] = options[vert][hor][rand()%options[vert][hor].size()];
}
return board;
}

3. 白人小哥， leetcode 425 Wrod Squares 稍微修改了一下, 有重复，并且每个字的长度不一定相同, follow up : test cases 应该怎么写（DFS + Trie) 没写完
4. 中国小哥，提示很多。有一个数组，类似于：{{'Canada', 3}, {'USA', 5}, {'UK', 2}, {'Brasil', 3}}, 数组的类型是Country, 有两个变量， Country.name, Country.weight. 每个国家都有一个权重，然后给一个output()函数，每次调用这个函数的时候就输出一个国家的名字，要使每个国家被输出的概率相等。我用的方法是平摊weight: {Canada, Canada, USA, USA, USA, USA, UK, UK, Brasil, Brasil, Brasil}, 然后用Random 函数输出。Follow up : 如果这个权重的值很大很大，比如billio级别，应该怎么办。我的方法是类似于线段树，然后再用sum * Random(), 看这个区间坐落在哪里。

第四题说错了，应该是输出的概率和权重匹配，就是canada应该是3/13, USA: 5/13

string getCountryByWeight(vector<pair<string, double>>& cw) {. visit 1point3acres.com for more.
vector<double> pdf = {0.0}; double sum = 0.0; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
for (auto& x:cw) { // create probability distribution function (pdf). Waral 鍗氬鏈夋洿澶氭枃绔�,
pdf.push_back(pdf.back()+x.second);
sum += x.second;
}
for (auto& p:pdf) p /= sum;. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
int i = lower_bound(pdf.begin(), pdf.end(), rand()/RAND_MAX) - pdf.begin();
return cw[i-1].first;
}

http://www.1point3acres.com/bbs/thread-209672-1-1.html
第一题：Binary Search Tree每个node都是int, 要return 一个所有node的sorted array. 用DFS/recursion做，O(N)时间O(N)空间。N是树里节点的个数。
第二题: 已知k个sorted array of int, return 一个 sorted array. 其中每个array的average size是N. 用Heap(priority queue)做，O(Nklogk)时间O(Nk)空间。

http://www.1point3acres.com/bbs/thread-213200-1-1.html
First interview: Design a data structure that stores a dictionary and can return a list of words that has some input prefix.
LC: TrieTree
Follow-up: if a dict has n words, average word length is m, input length is s, what's the time/space complexity?
基本上就是原题, 还好之前刷过, 没什么大问题就过了. 最后硬是聊了10分钟...

Second interview:
先问了Hash, what happen if there is a collision?
然后就来问题了: Given a rotated sorted array, write a function to find the minimum value.
我用了binary search
http://www.1point3acres.com/bbs/thread-210951-1-1.html

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

十月末面的狗家，先上面经：1. LC 425: word square, Trie+dfs做的
2.LC 394: Decode String+一些简单的follow up
3.给一些parent和child关系，判断两个人有没有血缘关系，也是面经高频：应该用union find。这轮做的不太好，
只写了brute force的找到每个点的祖先然后存起来，判断两个人祖先是否一样
4.给一个股票波动图，问怎么smooth这个图让波动不要太大，
后来发现就是LC346 given a window size,find moving average from data stream.
用circular array做的。

follow up是这种方法会出现什么问题，
double类型做多次的计算之后会lose accuarcy, 要定期把window里的sum清零重新sum。

http://www.1point3acres.com/bbs/thread-212960-1-1.html
第一轮三姐，问题是常见的给字典，再给词语前缀，然后返回所有是该前缀的词语，用Trie加DFS做出
第二轮白人小哥，一开始问了一道至今不懂的问题，好像是给一个vector<uint8_t> nums, 然后又给一个256位的vector<int> counts，遍历nums，然后counts[nums]++，问如何进行优化，提示说要用到CPU cache之类的东西(完全不知道)。小白哥见我懵逼，后来又给了一道3sum，迅速做出。. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
第三轮白人大叔，判断两个binary search tree是否相等，一开始的想法是将tree in order转化为vector然后比较，后来大叔说可以写个iterator来从小到大遍历树，按照他的想法写了写

Inorder 输出的数组是排序好的，因为是BST所以肯定可以比较。后面的iterator大叔加了两个条件，一个是知道最小那个数的node，另一个是每个node有个parent，这样就很简单了，implement next与hasnext

http://massivealgorithms.blogspot.com/2014/07/check-for-identical-bsts-without.html
比较两个 bst 只需要比较两个的 preorder 一样

因为知道 preorder，inorder 就已经确定（BST），然后根据 preorder 和 inorder 就可以还原出一棵 binary tree。

第四轮白人大叔，问如何表示稀疏矩阵，一开始可以用两个hash table解决，一个的key 是行数，value是一个key为列数value为值的hash table，另一个是key为列数，value是一个key 为行数value为值的hashtable，follow up，如果想要整行，整列删除，设值该用什么结构？没答上来，应该是用十字链表
稀疏矩阵我觉得就用嵌套hashtable就能解决吧？因为如果是十字链表你也得是 doublely-linkedlist吧，这样你删除整行也得从左到右遍历linkedlist，然后cut与上下节点的link，这样的时间复杂度也是O(n)，操作数也和hashtable方法一样。。而且你十字链表的头指针也得用个hashset存着。。

第一轮
白人小哥，第一题，判断括号是否合法，秒做，第二题，两个array表示两个整数，相加，秒做，第三题很有意思，给一个逻辑运算树，问最少翻转几个运算符可以翻转最终结果，例如，(True && False) || (False || True)，结果是true，若想翻转成false，最少翻转一次(第三个||翻转成为&&)，没写code，讨论下来应该分情况讨论然后recursive做

-google 1point3acres
跪在第二轮，白人大叔，题目是部分sort，即sort数组中一半的元素，例如{9, 1, 8, 3, 0} sort成{0, 1, 9, 3, 8}，本来用quick sort 加个条件解决即可，但是大叔硬是要我用C++的template，语法忘记，结果卡了三十分钟，

http://www.1point3acres.com/bbs/thread-204586-1-1.html
#1 leetcode原题，单向链表，l1->l2->l3->...->ln，变成：l1->ln->l2->ln-1->l3->...

我先说用array存下来，然后重建链表，分析一下时间空间复杂度。然后直接说了最优算法。全部写完大概二十多分钟。
先遍历一遍链表得到长度，之后把后半段reverse一下，然后把reverse之后的后半段插入前半段，复杂度是O(N)但是空间要求只有O(1)
#2 一个matrix存了好多数，支持两种操作
update(i, j, v)：更新坐标为[i,j]的元素
sum(x1, y1, x2, y2)：把[x1, y1]和[x2, y2]所确定的矩形空间所包含的数求和（x1<=x2, y1<=y2）

有三种情形，（1）update很多，（2）sum很多，（3）都很多。可以预处理，在三种情形下怎么设计。
这题不用coding，只要讲思路。最后问了一下工作内容，还有谷歌不同location的工作和薪资差别

https://en.wikipedia.org/wiki/Partial_sorting

Total sorting is the problem of returning a list of items such that its elements all appear in order, while partial sorting is returning a list of the k smallest (or k largest) elements in order. The other elements (above the k smallest ones) may also be stored, as in an in-place partial sort, or may be discarded, which is common in streaming partial sorts. A common practical example of partial sorting is computing the "Top 100" of some list.

Heap-based solution

Heaps admit a simple single-pass partial sort when

k

is fixed: insert the first

k

elements of the input into a max-heap. Then make one pass over the remaining elements, add each to the heap in turn, and remove the largest element. Each insertion operation takes

O (log k)

time, resulting in

O (n log k)

time overall; this algorithm is practical for small values of

k

and in online settings.^[1]

Solution by partitioning selection

A further relaxation requiring only a list of the

k

smallest elements, but without requiring that these be ordered, makes the problem equivalent to partition-based selection; the original partial sorting problem can be solved by such a selection algorithm to obtain an array where the first

k

elements are the

k

smallest, and sorting these, at a total cost of

O (n + k log k)

operations. A popular choice to implement this algorithm scheme is to combine quickselect and quicksort; the result is sometimes called "quickselsort"

More efficient than the aforementioned are specialized partial sorting algorithms based on mergesort and quicksort. In the quicksort variant, there is no need to recursively sort partitions which only contain elements that would fall after the

k

'th place in the final sorted array (starting from the "left" boundary). Thus, if the pivot falls in position

k

or later, we recurse only on the left partition:^[2]

 function partial_quicksort(A, i, j, k)
     if i < j
         p ← pivot(A, i, j)
         p ← partition(A, i, j, p)
         partial_quicksort(A, i, p-1, k)
         if p < k-1
             partial_quicksort(A, p+1, j, k)

Google Interview Misc Part 8

Heap-based solution

Solution by partitioning selection

Labels

Popular Posts