Google interview questions #8

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=478170
第一轮美国白人小哥，一路提醒
自己设计一个SnapShot class 和一个SnapshottableMap class，snapshot要实现get(String key) function，snapshottable map要实现put(String key, String value)，get(String key), createSnapshots(), List<Snapshot> getSnapshots() ，四个function

example：

SnapshottableMap map = new SnapshottableMap();
map.put("name", "John");
map.put("country", "UK");

Snapshot s1 = map.createSnapshot();

assert(s1.get("name").equals("John"));
assert(s1.get("country").equals("UK"));

map.put("name", "Marta");
Snapshot s2 = map.createSnapshot();

assert(s2.get("name").equals("Marta"));
assert(s2.get("country").equals("UK"));
assert(s1.get("name").equals("John"));



第二轮很简单，印度小哥，一路问一路怼，各种不给用，体验不佳。。。

给一串string，找到第一对string，他们的cahracters是一样的，不care count。

["abb", "dsa", "hgd", "ab", "aab"]
那就是[0,3]

第一题我好像用了一个List<HashMap> 太具体也不记得了，这题答的也不好；

第二题就用boolean[][]，把每个string用到的char对比一下。面试官没让用HashMap或者Set

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=444025

第一题： 给一堆interval,每一个对应一个字符: (start, end) char

比如

(0,4 ) X

(3,6) Y

(5, 7) Z

…

将interval细分为不重叠的interval，并输出每段细分interval中存在哪些字符， 不存在字符的区间不用输出。

(0,3) X

(3,4) X,Y

(4,5) Y,Z

(5,6) Y,Z

(6,7) Z

. From 1point 3acres bbs

楼主解法：将原始interval变为（start, 1, char）, ( end,-1,char)， 然后根据首元素sort处理， 遇到start补上元素，遇到end去掉元素。类似lifeand death.  

讲完思路之后在电脑上写完了code

给出一堆点（xi,yi) 如果任意两个点水平坐标或者竖直坐标相同，就能去掉其中一个点，直到无法去掉点为止（即任意两点不水平/竖直共线）， 要求最多能去掉多少点。

楼主开始讲了brutal force的dfs, 白人小哥觉得复杂度太高，在他的提示下用图来解决。 根据point建立graph，如果两个点符合x或y相同的条件，就连一条边。然后union-find查看有多少联通块。 然后谈了一下union-find压缩路径的几种方法和时间复杂度。写出code后接下来讨论了各种小优化。

第三题：地里的面经题。

有一个山洞，可以看作一维height数组。  另外有一堆箱子boxes， 要求将箱子从外面推到山洞里面，问最多能推多少箱子进山洞。

楼主先解释了为什么要先将箱子高度排序，先推矮箱子，再推高箱子。同时山洞的每一个位置i都最多能容许min(heights[:i])的箱子通过。 根据这点建立一个allowedHeight数组，可以看出是单调不增的序列， 因此对每个箱子高度可以bisect寻找allowedHeight里面对应的position index.  讨论了时间复杂度 O(log(len(height))*len(boxes))。电脑写了code后和面试小哥讨论了几点可以优化的地方，最后小哥表示时间复杂度还可以优化，在提示下使用two pointer方法，让两个pointer分别指向最矮箱子的position和最小allowedHeight position, 依次比较二者的大小来分别递增两pointer。 时间复杂度可以变成O(len(height)+len(boxes))

给一个undirected graph, 有两个player A,B 玩游戏，由A先选一个node start,  B在剩下的node中选择一个。

接下来A,B依次选node,但是每次选的node必须和该player已选的nodes中的一个是neighbour。假设玩家都很理性，问player B能获得的最大nodes数量。

楼主就是挂在这题上的，这题是coding最后一题，楼主各种犯困，亚裔小哥也寡言少语，说完题目就冷眼旁观了。

楼主谈了一下brutal dfs的思路，亚裔小哥不太满意，提示问B每次如何选才能剪枝，感觉好像是B每次选A neighbour中潜力最大的node(就是联通剩余node最多的那个)，但是也一时没想到严格的证明，也没时间在电脑上写出code。

这次也算是感受下狗家面试难度吧，以下是准备过程中参考的面经总结：

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

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

还有利特抠里面狗家出现的题号总结

872, 857, 854, 853, 852, 850, 849, 846, 844, 843, 835, 833, 818, 817, 815, 809, 807, 806, 805, 804, 803, 802,

791, 787, 785, 778, 777, 776, 774, 773, 772, 769, 767, 766, 765, 753, 750, 745, 742, 739, 737, 735, 734, 732, 731, 729, 727, 724, 722, 721, 720,

685, 684, 683, 681, 674, 659, 652, 621, 568, 560, 552, 540, 529, 527, 505, 503,

499, 496, 494, 490, 486, 465, 460, 457, 456, 438, 419, 444, 418, 399, 394, 392, 379, 365, 362, 361, 359, 353, 346, 340, 337, 334, 315, 312, 308, 305,

298, 297, 295, 289, 286, 274, 271, 270, 269, 264, 253, 249, 248, 238, 236, 235, 230, 229, 222, 220, 218, 205, 200,

169, 165, 162, 153, 152, 150, 146, 141, 135, 134, 128, 124,121, 115,112, 96, 95, 91, 84, 72, 65, 59, 56, 44, 43, 42, 41, 37, 36, 10

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=511673
1. 随机生成二维的迷宫，迷宫的路与路之间不能重叠，简单来说就是不能有厚度为2的路或者墙吧，要求有尽可能多的branch,就是充分利用空间，不能只生成一个很简单的路。自己定义入口和出口。
     想了40分钟才想出来做法😂，期间想到什么都会和面试官说，不对也没事，面试官也没有给太多提示，但如果方向是对的会给予肯定，10分钟左右写完了代码（还好用的是python）面试官还挺满意，稍微检查了下代码时间就差不多到了。

ㄧ迷宫高频DFS往四周打通两格子

2. warm up是给两个单词 能不能从一个单词转化成另一个单词，本质就是word pattern match。讨论了下有环的情况。没要求写代码
    正式的题是给一个string数组，会不断的更新这个数组某个index的string，写个function take snapshot 然后返回这个snapshot的version, 还有个function去get某个version某个index的string

3. 先来一个warm up, 特简单就不说题了，要求写了代码
   正式的题是一个二维矩阵上面有X， Y，O，问从X到Y的最短距离（曼哈顿距离）
楼主说的应该是有很多的X, Y求其中曼哈顿距离最小的一对pair吧。这个题也看到过很多次了

4. 挺简单一题，给了很多源文件和一些compile出来的文件，compile出来的文件给了他们的dependency. 问如果改了某个源文件 有多少文件需要重新compile。
   简单的dfs就可以做，先写了recursion, 然后又让写了traverse的方法

5. 一个洞穴里面很多格，每一格都是不同的高度，还有一堆object, 每个的高度不同，问这个洞穴最多可以放多少个object，往洞穴放object的话要注意是从洞口往里放，所以靠近洞口的格子的高度会限制后面的高度，因为object会被卡住。。
   每个格子只能放一个object，object不能叠加。

其实好像就是一个个把箱子推进洞里，这样的话因为高度的限制由左至右是只递减不增加的，先把箱子排序一下然后用2 pointers 把矮的箱子优先尽可能往里面推就可以了吧

最后面的题里只有两个单词转化的题是看过面经的。好像还被面试官看出来了，因为他出第二题的时候说please let me know if you've seen this before


ㄧ迷宫高频DFS往四周打通两格子，二是高频照相数组改照相字符串吧，三直觉BFS或Heap，四听起来感觉是要Topo但似乎只是个DFS，五暂时想不到DFS暴力解以为的作法

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=508669
第一轮：印度小姐姐。出了两个题，第一个是一个二叉树 所有叶节点都是用double linkedlist连起来 判断一个节点是否为叶节点。

叶子节点的left和right连接到了其他叶子节点上了

第一题判断node.left.right==node 如果node.left不存在就判断右边，如果都不存在，就是leaf

第二题 面经题机器人左上到右下 先问path的个数再用输出所有path。小姐姐全程敲电脑 我边说她边摇头...

第二轮：通信管道的总容量固定。管道的class里面有个函数是外部可以每次请求某个时间段用多少容量，设计这个class。先花了20多分钟讨论 然后20分钟写代码 应该不是最优解 问印度小哥有啥其他结构优化 小哥说没时间了 你自己回家想...
第二轮或者my calendar iii的解法

第三轮：加上中午带我吃饭的印度大妈，我一度怀疑我和印度人特别有缘分....这一轮是个国人大哥 大哥迟到了10分钟 印度大妈一直安慰我没事 面试官迟到 他会把这个考虑进去的。先互相聊了五六分钟，然后大哥说诶 看你做的比较底层 还跟lock有关啊，我们做个多线程锁的题目吧，如果你觉得不合适我们就换。我说还是换吧 我都是准备算法题没有准备多线程 面试官说还是做做吧 不难的...我有什么办法。。。题目我现在还是有点懵懵的，大家可以搜索下“多线程 十字路口”。这一轮完跪...大哥走之前说了句 我不该出这个题的.....
第四轮：就是最近的面经最方便的公寓。
第五轮：设计两个class，Node和Notebook。每个Node只知道自己的邻居，不知道全局的图和关系，提示Node里主要有两个函数receive（）和send（），要求Notebook上登记所有Node的信息。本质就是DFS，但是和扫地机器人有点像就是要最后返回到最初的Node。有个corner case没有过就是所有的Node的名字 ID啥的都一样，怎么办判断这个Node已经visited了...

白瞎了这两个月把google tag下所有题都刷一遍...完败在多线程手下。。。

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=207550
第一轮，中国小哥，提前15min接我，然后就开始中文blabla聊天了，到时间进去面试，瞬间严肃了，心累累。题目是之前看到的别人面过的题，判断一个围棋棋子是不是alive（当时看的题目是判断一个棋盘是不是死的，感觉更烦。。。）当初看到这题的时候和非cs的室友讨论了半天怎么做，因为当时以为棋子被周围一大圈其他棋子围起来就算dead。面试官一讲完题，心里就拔凉拔凉的，后来不知道怎么镇定下来了，然后就问了一个黑棋被一大圈白棋圈起来算不算dead，他说不算，这下瞬间轻松了哈哈哈。写了个bfs，写完后面试官说我有个小错，后来自己发现改了。之后就是followup，面试官有点解释不清楚，然后就自己说了，然后继续follow up，我自己提了个方法，他不太满意，准备让我写psydo code，不知道怎么的，我问了他怎么做，然后他告诉我了！后来我就把他的方法写了上去，他自己还把我写的敲进电脑里了><后来我还解释了自己的想法是错误的。中国大哥真心赞！！！

第二轮，外国（白人？）大叔，长得有点像三哥，进来的时候以为是三哥吓死我了。还有一个超帅的shadow白人小哥，sd毕业的，他先来的，自我介绍是shadow，最后聊天的时候他说还没面过人，还说我的学校project比他们难，小哥居然看了我的简历。。。题目是topological sorting，和course schedule ii一样，input什么的都不给，我强行拐到course schedule ii的input format。用了bfs写的，写的过程中变量名一直不统一，被大叔一直问，尴尬。。。写完之后让跑test，分析复杂度，居然分析出来是n^2, 最后问我能怎么优化，我回了句，i think all the parts are necessary，大叔以为unnecessary，准备追问，小哥说我说的是necessary，之后就问我知道这个算法叫什么么，我说topological sorting，他问知道optimal solution么，我说不知道，他说fair enough（不太记得了）。。之后就问可不可以用多个machine解决这个问题。感觉这轮还可以，有说有笑的。

午饭，加拿大来的三哥＝＝随便聊聊，lz表示不想和三哥聊天，天真的觉得遇到个三哥之后就不会遇到三哥了。

第三轮，中国大姐，很冷淡。。。吃饭回来在房间门口遇到她了，打了个招呼，用英语聊了聊，感觉没有大哥那么热情。第一题，给一个tree，一个api，check一个node是不是要被delete，返回被delete之后的tree的集合，一看就是recursion，然后边写边说，写完之后发现重复代码太多，然后修改了一下，跑了个test，当时心里还在纠结解法对不对，跑test有点心不在焉，一个test重复了两遍，后来她拍了个照就结束了，长舒一口气。本来以为快要结束了，才发现过了20min，又被甩了第二题，给一个square matrix，一个input k，输出k ＊ k 大小矩阵的 sum结果，相当于computer vision给图像filter一样。看了题也是心里呵呵大。。。提了个解法，用类似range sum的方法保存prefix sum，她说可以就写，然后写的时候也是心累，i j已经要分不清了，过程中自己就一直嘀咕，她感觉就是瞅着我的代码抠，问了两个问题貌似，最后时间到了没写完，问她我的方法对吗，她说对的，只是时间不够了，拍了照走人。

第四轮，“期待已久”的三哥登场了，上来寒暄问我要不要上厕所喝水blabla，之后就问了简历里的project！excume me＝＝然后出了一道鬼知道干什么的题，题目没法描述，哪天画个图片再贴上来，和图形有关的，三角形套三角形，问怎么输出一堆点，然后用已知的画线api生成某一depth的图形，不知道以前面经里有没有这道题。然后就是一直没思路，问hint也没什么有用信息，三哥就说写个简单的情况，然后突然想出点思路，然后三哥一直抠细节，问的心烦，一会问这一会问那，根本没法思考，然后看着电脑的时间不多了，心态也不好了，最后代码就写了一点点，心里当时已经是死灰一片，最后和他repeat了一下思路，貌似之前他还没有理解我要干什么，最后问他怎么做，说我on the right track。出来后感觉三哥就是个坑，占用那么多时间说其他的。。。


https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=490290
美国小哥，面筋高频，给个grid，从左下走到右下角，只能往右走（↗️，➡️，↘️），问有多少条路径。 follow-up： 给一个list of cordinates, 判断有没有路径能经过所有点。 再follow-up, 经过所有点的路径有几条。 只有第一问写了code，follow up 都只是在聊天
2. 美国小哥，面试官自己出的题，给一堆Contacts， Contact 是一个class，里面有list of emails, addresses. 1. dedupe 所有相同的contacts, 相同的定义就是有两个contacts， 他们所有的emails 和addresses 都相同。 follow-up: merge contacts. 如果有两个contact包含同一个email address，就把他们俩merge 起来， 只写了follow up 的code
3. 美国大哥，莉蔻 酒似奇，用union-find做的，面试官是个research team的senior engineer，之后就开始了讨论union-find 如何优化之路。。。没有别的follow-up了
http://massivealgorithms.blogspot.com/2018/11/leetcode-947-most-stones-removed-with.html
4. 国人大哥，莉蔻 散依奇, 特别特别nice，上来自我介绍都没做就叫我快点做题，生怕我做不完哈哈哈。。。一上来就叫做题的面试官都是良心面试官～很快就做完了，大哥也没follow-up，就随便聊了聊天。
http://massivealgorithms.blogspot.com/2016/10/leetcode-416-pacific-atlantic-water-flow.html
5. 看不出来是哪人，口音有点西班牙裔，莉蔻 扒舞奇。背景是买艺术品，换汤不换药。先给了一个warm up是买下所有艺术品需要的最少的钱，然后才是买k个

狗家onsite跪经

1. 雨滴落地，给每个即将下落雨滴的中点坐标，落到地上会形成1cm的湿印。地面范围是0-100cm的线段，要求写函数判断该雨滴落下之后，整个地面是否都变湿
2. 面经题，猜字母，返回几个对且位置正确，几个对但位置不正确，1A3B这种。follow up是根据猜词结果历史，帮助玩家判断下次猜的词是否有可能正确
3. 面经题，字母骰子，六面字母有可能重复，给15个，input是长15的string，给出一个可行解使筛子的排列有可能组成这个15长度的单词。 follow up是如果有可互换的字母怎么判断，比如W可看成M，Z可能看成N等等
4. 面经题，+ * 计算，( * 2 7 ( + 3 4 8 ) 8 )
5. Postfix，这题把所有可能的运算符全扔上去了，比如input = (a+b*c+(d*e^f+h)), output = abc*+def^*h++, 按优先级把运算符甩到两个字符后边去

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=499453

第一轮：算法。应该是新题? 上来先让我描述一下二分法的算法。题目是给定一个无序无重复数组，对数组中的每一个数字，用二分法能不能在数组中找到，返回一个boolean数组显示能不能找到。比如数组[3,8,6,7,5]，target 3, 先找到6再找左边找到3，为true；target 8, 先找到6，再找右边，而8在左边，右边永远找不到，为false；target 6, 第一次二分就能找到，以此类推，最终返回[true,false,true,true,false]。我写了一个暴力解。他好像觉得时间复杂度过高。

第二轮：算法。这五轮里最简单的题。题目是给一个字符串，类似于 “23.45” 转换成数字23.45。我写完他告诉我主要考查的是代码的可读性，可扩展性以及corner case的handling。

吃饭：食堂里全是人，到处排队，于是随便吃了点印度咖喱饭。

第三轮：算法。一道关于切巧克力的题。题目是给定一个数组（一板巧克力），数组里的每一个数字都表示其中一块的甜度。有n个人来分享这巧克力，需要切n-1刀。其他n-1个人会把甜度高的portion都拿走 剩下的留给你。问如何切割这块巧克力你自己尽可能能拿到最高的甜度。比如数组[3,2,3,1,4],3个人分，切成[3,2 |3,1 |4]，你能拿到最多的4。后来问了朋友，听说可以用二分答案来做？

第四轮：算法。题目是给定两个字符串a和b，对a进行多次复制并且删除某一些character，能不能把它变成b，返回boolean。比如a = abdc, b = baccd, 对a复制三次并删去一些字符可以变成b。follow up是最少复制次数是多少。

第五轮：算法。硬币找零。刷题网武艺吧

http://bgmeow.xyz/2017/01/30/google-pittsburgh-onsite/

LeetCode 原题 LeetCode 394 - Decode String 。这是全程最后悔的了，小哥最后一路提示。亏我两天前刚做过，早上出门前还特意瞄了一眼。明明我自己用一个栈做出来了，面试的时候用了两个栈还搞不领情。

给定一串单词即对应的值，要求自定数据结构，并设计算法使得每次可以根据单词值的分布 randomly 返回一个单词。Follow up 是怎么 test 。
举例说：
输入：[apple: 2, banana: 3, orange: 1]
分析：
total = 2 + 3 + 1 = 6
freq(apple) = 2/6
freq(banana) = 3/6
freq(orange) = 1/6
如果持续多次的 call ，那最后得到的单词的分布就是 apple : banana : orange = 2 : 3 : 1 。

我一开始还想着用 map ，最后一排脑瓜用数组代表范围，然后 binary search 做出来了。后来问考点在哪儿，小叔说一个是生成 random 怎么去除 0 值，另一个就是 binary search 。

先是坐下来唠了一会嗑，问我这学期选了什么课，有没有什么学习计划。然后开始做题。小叔先是介绍了数独，我咯噔一下，这题不会。然后他画风一转，你来实现一个帮助我完成数独的方法吧，就是给你某一列的 sum 和这一列的长度，返回这一类所有可行的结果。（数独规则是某一列不能有重复数字，且数字只能是 1~9 ）。
考虑了几个 Corner case 以后开始下手。我用 hashmap + 递归 做的，然后被小叔指出一个 map 的问题，于是做了改进，后来也提出直接用 array 也行。
后面有一小撮时间，看小叔想走了，就随便问了个问题。

给定一串 tuple ，形式为（请求时间，完成时间），系统在每次请求是会将任务放入队列中，完成时将任务移除。给定一个时间 t ，要求返回该时间时队列中有多少个请求。

我这题也挺昏的，一直没有搞清楚他的意图。我一开始想用 Priority Queue ，然后他说这样每次都要initialize 要能够处理很多次连续 call 。然后我问他有没有时间和空间的限制，他说他想要只要一次 initialize ，然后以后每次 call 都只要 O(1) 。我想这怎么可能。然后试了 sort + binary search ，他说这样需要两次 sort ，能不能再快一点。总之最后也没有写代码，一直在改和想。我后面又问他这题实际上是怎么做的，他说，嘛，我就是想给你了解一下时间和空间的 tradeoff ，看你有没有不一样的想法，其实我们也很难达到两个都最优的。= =

然后后面带我去出口也聊了一会加州和匹茨堡哪个更好，我就说，tradeoff 嘛。最后前台小妹说我第一次有 T 恤发，那小叔一脸怨念说我当初怎么就没有哈哈哈。

总结一下：第一轮做过的题目没有把握好，嵌套这些的状态存取和转换很容易混，第二轮前面思路卡顿了十分钟吧，后面代码写的还比较顺，第三轮写代码的时候数据结构换的太多，可能在这里让面试官有点疙瘩吧，食堂的菜还行，最后一轮有点蒙圈。感觉运气还不错，没有做到地里那种魔鬼级别的

https://leetcode.com/discuss/interview-experience/132252/Google-software-engineer-full-time-new-grad/

 1. n-straight, see if a list is a valid n-straight list,
  e.g. 3-straight: [1, 2, 3] return True, [1,2,4] return false, [1,2,3,4] return false, [1,2,3,4,5,6] return true, cause it can be seen as [1,2,3] + [4,5,6]
  if n-straight is valid for at least n continous number.
  
2. given a integer list ,[a, b, ...] and coresponding char['x','u',...] means the number of different char, return every possible combination (unique)
  follow up: just return the number of different combination. and optimize.
3. given a integer array, contain unique number, represent the velocity of the car in the road (the position in the array represent the possition in the road, and there is only one road), the fast car will be block by the slow car, return a array, each number represent the number of car in that group.
 e.g. [4,2,3,1] return [1,2,1] because 4 the is faster and no one  can block it, but 3 will be block by 2, and previous cars are faster than 1, so 1 will not be in the same group with them.
 follow up, add a new car with a new speed into this array , return every possible answer.
 
4.given two string. one has exactly one more letter than the other, find this letter, the input must be valid.
  e.g. s1:'abbc', s2:'bcbad' return d




https://leetcode.com/discuss/interview-experience/189573/Big-mistake-with-Google-telephonic-first-round-Software-Engineer-position/

Lession learned: Don't waste much time in answering "tell me about yourself". I talked extended amount of time on that, I feel, that I didn't leave much time to finish up the code.
Expected time of interview: 45 mins.
Actual time of interview: 55 mins.

Question: you have to implement a time critical hashmap, such that you are given input as: key, value & time-limit. If the time limit gets over and then the hashmap must not return any value. This should be strictly implemented as an Object Oriented code.

https://leetcode.com/discuss/interview-experience/124626/Google-onsite-interview-questions/

1. Given a contiguous sequence of numbers in which each number repeats thrice, there is exactly one missing number. Find the missing number.
   eg: 11122333 : Missing number 2
   11122233344455666 Missing number 5

 - binary search

1. Given a compressed string in which a number followed by [] indicate how many times those characters occur, decompress the string
   Eg. : a3[b2[c1[d]]]e will be decompressed as abcdcdbcdcdbcdcde.
   Assume the string is well formed and number will always be followed by a [].
2. Given a tree representation of a html parsed output, wherein every block is a node in the tree, find if two html docs contain the same text.

struct Node {
       string value;
       bool isMetadata;
       vector<Node*> children;
};

For eg, consider the two documents

sample

Hello world

will be represented as Node1: value sample, children: isMetadata: true Node2: value: children:

isMetadata: true Node3: value:

: children: Hello world isMetadata: true Node4: value Hello world isMetadata: false

and a second document

Hello world

and both documents are equivalent since they contain the same data.

Note: the case of both documents fitting in memory is trivial, since it is just walking this tree list, consolidating data and comparing. As a follow up, solve the case where the whole documents may not be able to fit in memory.
4. Given a 2D matrix M X N, support two operations:Query(row1, col1, row2, col2) such that I get the sum of all numbers in the rectangle ((row1, col1), (row1, col2), (row2, col1), (row2, col2)) and
Update(row, col) to a new number

And query is a very frequent operation and update is a rare operation, so query should be really fast, but update can be slower.

Follow up: How would you solve this in a distributed fashion

5. Verify if a given matrix is a Toeplitz matrix:
   Follow up, assume that the whole matrix cannot be fit in memory and should be read from a file, assume that a few rows and all columns can be read in, how to verify?

https://leetcode.com/discuss/interview-experience/193104/Google-Software-Engineer-University-Graduate-Phone-interviews/

1st interview:

• Write a function which returns length of the longest path in acyclic directed graph.
  Modification: what if a graph had cycles?
  Time and space complexity.

2nd interview:

• Check if the number is a power of 7 (number is of type long)
  Modification: what if there is no log function.
  Time complexity
• https://leetcode.com/problems/frog-jump/

https://leetcode.com/discuss/interview-experience/201403/Google-New-Grad-SW-onsite/

Strictly 45 minute for each round (Interviewer said strict 45min for fair game)
Technical phone screen (45min):
- Merge two linked list in zigzag way

 1st round : Stock price problem for max profit (Buy one and sell one)
 - Had to explain logic very clearly
 - follow up : identify buying stock date and selling stock date

2nd round : Given unsorted array, find how many elements can be found using binary search
- ex : [5,4,6,2,8] -> Ans : 3 -> '6' and '8' and '5' can be found using binary search
- I could not finish coding part, only figured out correct approach for the problem in 30 minutes

3rd round : 
Some note : spent first 10 -15 minutes on wrong problem and interviewer changed problem
-Given unsorted pointers that points to doubly linked list,
find the number of groups can be formed with this pointers ( one group can be formed with all neighboring nodes)
-Note : head is not given, only pointers are given
- ex :None <-> Node1 <->  Node2 <-> Node3 <-> Node4 <-> None     Node5 (disconnected)
- pointers : [point4(point Node4), point2(point node2), point1(point node1), point5(point Node5)]
- ans : 3 -> 1 group(point1, point2), 1 group(point4), 1 group(point5)

4th round : given poker cards, validate if cards can be split into form straights
- ex: cards = [2,9,3,10,4,J,5,Q,6,K] ans : True : [2,3,4,5,6] and [9,10,J,Q,K] form straight

Detail experience:

1. Took long time to explain the logic behind the problem -> Did okay but not quick solving in easy problems
2. Only proposed approach and necessary condition for the problem which interviewer also agreed with the idea -> Bumped disastrously could not finish coding
3. Solved with hint (initially confused with problem) : Did normal but not as quick for this easy problem.
4. Proposed two approach with examples going through step by step and analysed time/space complexity and picked one for coding : Did okay but not as great as

Group size is fixed as 5 with consecutive cards

Google interview questions #8

ref: http://www.mitbbs.com/article_t/JobHunting/33072599.html

是烙印, 问的是LCA of DAG. 全程不让写代码, 就一直问follow up, 问复杂度, 问怎
么做, 为什么要这么做, 用那个为什么不好, 后来问要是有很多pair of nodes 求LCA
要怎么做preprocessing.

解法：

2个node各做bfs，记录走过的node和距离，如果出现重复就记录2个的距离和，直到找到最小的距离和

follow up：
预先计算出每个node到其他所有node的距离。当给定2个node时，找出所有的共同点，计算距离和

--------------------------------------------------------------------------
ref: http://www.mitbbs.com/article_t/JobHunting/33073385.html

x_0 = C (integer)
if x_n is even then x_{n+1} is x_n / 2
if x_n is odd then x_{n+1} to be 3 * x_n + 1

这题的复杂度是O(logC)吗？

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

---------------------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=11377&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

一队人，每一个人有两个值（height，tvalue），其中height代表身高，tvalue代表这个人前面有多少人比他高。现在把这个array of (height, tvalue)打乱，然后要还原这个数列。.

解法：

按height排序，从最低height开始，tvalue就是它在新array里的最终位置。需要注意是，每次都要对之前index前面里已经有多少被放置

最终的index = tvalue + （index之前已经确定的元素个数）

所以复杂度是O(n ^ 2)

nlogn 的解法：根据array的index建立一个bst，附带一个额外的值代表此subtree当前有多少个node被填过

-------------------------------------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=7849&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

#1 把bst变成双向链表
解法：inorder遍历，保证一个pointer pass by reference

逆序数
解法： divide and conquer(merge sort)

#2 实现Candy Crush
1.m行n列的矩阵；2.q种花色物品；3.矩阵里每个cell的花色都是random的；4.初始化之后至少一个available的move；5.no 3-run，即初始化的时候不能直接出现三个同种物品连一线的情况。
好像还有其他几个要求，我已经记不清了。
我就开始按照他的要求挨个进行分析。先是random函数，然后就可以用双层for循环来填充每一个cell。我说但是一个available的move这个太难了，因为有太多的情况。就问他要提示，而且我不断做尝试。他说“其实答案比你想想的简单多了。最后直接告诉我：“你可以直接在填充所有的cell之前先创造一个可以move的三个物品先放进去。我恍然大悟，对对对，在双层for循环之前先做这一步操作。
下一个是"no 3-run的条件”。我说就每当在填充一个之前先往上下左右四个方向的两个格子都跟将random生成的物品进行比对。他说：“其实另一种情况。”我说：“就是将要填充的物品正好在两个同色物品之间。”他说对。我说咱们就可以用一个while循环，如果random生成的颜色不符合要求（设置一个boolean函数来判断，这里不要求实现）就继续循环。; u# V. Y: \ p7 B$ {/ a/ [: n
他说：“OK。其实这样会stuck到一种情况，你来想想。”我就想到比如比如当前方格的上、下、左、右各有一种两个同色物品排列，那么这个cell填这四种颜色的任何一种都不对了。”他说对，怎么避免呢？经过他的提示我就写这样的情况下直接清除board中所有已填颜色从头来过。0 L% F- Z) k( F
难点解决了，下一步就是写代码了，然后照相。
感觉这种题目面试官已经在里面设置好了处理的难点来等待你遇到和解决，然后看你尝试解决问题的方法以及交流能力。就像寻宝一样不断地试探、前进、解决问题。
#3 Tries

#4
比如1729 = 1^3 + 12 ^ 3 = 9 ^ 3 + 10 ^ 3。像这种可以由两对或两对以上的立方和组成的数叫做R某某某数（单词记不清了）。让你构造一个函数，输入是N，输出小于N的所有这种数。/ u" f% G( Z( |9 Q0 f- _1 H5 K
其实方法很简单，就是将从1到N的立方根之间的数，从中任取两个来求立方和，然后看结果集当中有没有出现两次或两次以上的数。就是类似于暴力了。

解法: 暴力 + hash，从1开始算到N

----------------------------------------------------------
ref: http://www.meetqun.com/forum.php?mod=viewthread&tid=11067&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50

Google onsite
1. 类似这道题：
给如下的数据格式：<start_time, end_time, value>
For example,
1, 3, 100
2, 4, 200
5, 6, 300
。。。
这些数据时间点可能有重合。在时间段2~3之间，value的和是100+200 = 300. 找出这
组数据中最高的value和
[consider end points]

解法：类似meeting room，把开始、结束时间排序，设2个指针p1, p2。
如果是开始时间，cur + value[p1++], 结束时间cur - value[p2++]

2.find k most frequent words from a file
解法：priority queue + hash map

3.brainstorming: 一个上传文件的service，之前正常运转，突然有一天挂了，这期间
没改代码。问怎么排查问题。

查log，物理硬件

-------------------------------------------------------------------------------
ref： http://www.meetqun.com/forum.php?mod=viewthread&tid=301&extra=page%3D1%26filter%3Dtypeid%26typeid%3D50&page=6

check一个数是否是3的次幂

解法：http://stackoverflow.com/questions/1804311/how-to-check-if-an-integer-is-power-of-3

遍历

查表，32位内3的幂也就几十位

2分

---------------------------------------------------------------------------------
ref: http://www.geeksforgeeks.org/dynamic-programming-set-18-word-wrap/
word wrap

解法：
标准dp

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

int cube(int num) {  return  num * num * num; } int minCost(vector<int> &v,vector<int> &dp,int index, int width) {  if (index == v.size()) return 0;  if (dp[index] != INT_MAX) return dp[index];  int len = v[index];  int minC = INT_MAX;  for (int i = index; i < v.size(); i++) {   minC = min(minC, cube(width - len) + minCost(v,dp,i + 1,width));   len += v[i] + 1;   if (width < len) break;  }  dp[index] = minC;  return minC; } int spawn(vector<int> &v, int width) {  vector<int> dp(v.size(),INT_MAX);  return minCost(v,dp,0,width); }

---------------------------------------
round 1: 给定一个class
class Event {
int id; /nsor id
int timestamp;
boolean status;
}
意思是某个sensor会触发一个事件使其状态status改变，true->false or false->true. 设计数据结构，存储以下信息：每个事件的sensor id, timestamp和status，使其可以响应一种query， query包含id, timestamp,返回这个id在这个时刻的status
follow up: 如果来的event不是按照timestamp递增的，怎么修改数据结构

round 2:
一个二维矩阵，里面是bits (1 or 0)，可以用int 或byte表示，左右翻转这个矩阵，有什么优化

round 3:
一个猜词游戏，给定一个词典，里面的词的长度都一样，有一个secret word在这个词典里，每次从词典里选一个词猜，只会返回和secret word有几个字母是一样的（只知道数量，不知道位置）。问怎样猜能尽量减少猜测次数