上周面的谷歌 上门，之前也在地里看了很多谷歌的面经，但是由于他家题库太大，以致于每道题貌似见过，又貌似没有见过。
1.大黑哥。稍微有点口吃，聊天比较费劲。。。。给你一堆log，里面每个人 的cpu usage，起始时间和结束时间， 每个人的peak usage。 会议室2的做法。 做完了以后写test case。然后简单问了一下问数据量很大怎么破。 然后说题目改了，之前说的是在这个时间段里面是cpu usage是恒定不变的， 现在变成线型增长的了，start time的时候是0， end time 的时候是log里面的那个值，然后问同样的问题。。。我第一反应还是往会议室2上面套，说那就看要多精确，比如说要精确到分钟，那就把之前的时间段拆成分钟级别的。小哥将信将疑的看着我，让我码出来来看看。写完了，小哥拍完照，看看时间，给我说，其实你这个做法不太对，你想想，如果两个时间段t1, t2 overlap的话，最大值只可能出现在什么地方。 我一想，说只可能出现在t1.endtime 或者t2.endtime的地方，小哥说，那就对了嘛，然后就走了。。。。
-
傻白甜小姐姐。问我对context free grammar 熟不熟悉。 我说并不知道，小姐姐表示非常好，就喜欢考不知道的。大概意思就是，给一串字符，比如说“abc”，grammar 会有一个 mapping，比如说a -> “ab”, b -> “c”, c -> “”;然后问给一个string n 个iteration后，string 会变成什么结果。 基本上就是brute force一下。然后小姐姐问，你这个东西的空间复杂度是多少，我说这个很难讲，得看你这个mapping是什么情况。她说，那好，如果我说不太关心最后string会变成什么样，我只关心最后有多长。 然后我就犯傻逼了，抠了半天脚，没有想出来，耽误好多时间。估计小姐姐都崩溃了，其实方法就是只记录string中的每个character的个数，就能generate下一个string各个character 的个数，最后加一下就完了。码完了以后，基本上没有多少时间了，又问了一个问题，说给我的一个string，判断通过一定iteration后，能不能变得stable。比如说上面那个abc，因为a会变成ab，b会变成c, c会变没有，所以这个是stable的。然而想了一会儿，并没有想出来，时间就到了。
-
三哥面，国人大哥shadow。出去上厕所的时候，国人大哥问我上午如何，我说一般般。大哥安慰我说，没有关系，面挂一轮也无所谓。在此谢过大哥了。问题是，你有一系列窗口，有些窗口会有重叠，让计算出每个窗口最后会有百分之多少展现出来，自己设计数据结构。我大概的意思就是，先假设这些窗口，只有两两重叠的，写了一个method。然后在三哥的提示下处理两个以上重叠的，大致的想法就是，比如说你已经算了0 到i个窗口，现在来了i + 1 一个窗口，你只要保证前面0到i个窗口中，没有两两重叠的，那算i + 1的时候，就不会有两个以上重叠的。所以做法就是每次在处理i + 1 的时候，先处理0到i，发现有重叠的，就split成多个窗口。最后code写得一团糟，估计挂了。
-
东欧大姐，问题很简单 https://www.geeksforgeeks.org/tree-isomorphism-problem/。 我照这个上面的方法码完以后，大姐表示可以，让我开始优化。很显然我没有get到大姐的点，我觉得这个算法基本上已经很优化了，不知道该如何改进。感觉大姐也应该是暗示到极限了，才明白大姐的意思是，程序的最后一行递归的时候，因为要分别 node1.left 和 node2.left， node1.right 和 node2.right比， 或者node1.right 和node2.left， node1.left和node2.right 比。所以这里还可以优化，就是在对于每一个node，只要做一些约束，比如说，左边的val比右边小，就能够只用左子树和左子树比，右子树和右子树比。赶紧改完code，照完相，走了。
-
ABC 小哥和大黑哥， 问了一个拿纸牌游戏， 纸牌上面有值，比如说 100， 1， -1， 2， 200， 1. 然后两个人轮流拿，直到拿完。 但是每次只能拿从左边数起的前三个，但是如果你要拿第三个，就必须前两个都拿了，你要拿第二个，就必须第一个也拿了，大家都最优策略，问最后第一个人能拿多少分。dfs 加 cache做了。 又问了一个bst相关的题，不难
总体来说，感觉狗家面试还是有点难，问题就在于如果看不穿问题的本质，或者说get不到面试官提示，就非常伤。所以估计多半挂了， 就当学习学习，下次继续面。