谷歌 上门

上周面的谷歌 上门，之前也在地里看了很多谷歌的面经，但是由于他家题库太大，以致于每道题貌似见过，又貌似没有见过。

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的地方，小哥说，那就对了嘛，然后就走了。。。。

2. 傻白甜小姐姐。问我对context free grammar

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

和左子树比，右子树和右子树比。赶紧改完code，照完相，走了。

5. ABC 小哥和大黑哥， 问了一个拿纸牌游戏， 纸牌上面有值，比如说 100， 1， -1， 2， 200， 1. 然后两个人轮流拿，直到拿完。 但是每次只能拿从左边数起的前三个，但是如果你要拿第三个，就必须前两个都拿了，你要拿第二个，就必须第一个也拿了，大家都最优策略，问最后第一个人能拿多少分。dfs 加 cache做了。 又问了一个bst相关的题，不难

总体来说，感觉狗家面试还是有点难，问题就在于如果看不穿问题的本质，或者说get不到面试官提示，就非常伤。所以估计多半挂了， 就当学习学习，下次继续面。

第三轮可能是这个 https://leetcode.com/problems/rectangle-area-ii/description/ ？

leonlica 发表于 2018-6-21 04:12
多谢楼主分享。
1. 请问数据量大是要如何处理？followup 线性增长那问有些没看明白，能否再解释下，谢谢。 ...

1.数据量大，我基本上就是胡喷，大致就是按照某个规矩（比如说按照user id），hash到 多个机子上算，算完了汇总一下。 follow up是这样的，比如说，你有一个log， start time 是1：00， end time 是1：30， usage 是30。 那么刚开始的时候，1点就是0， 一点十分就是10， 一点二十就是20， 一点三十就是30， 然后瞬间掉为0.

2. 第二个不太清楚，我给忘了stable的定义是什么，是说string 最后不变，还是说string最后的长度不变就算stable。

nibuxing 发表于 2018-6-21 10:25
楼主能说一下第五题dfs+cache的具体做法吗

因为你dfs下去求解，那么会有很多状态是重复的。所以用一个map存一下算过的状态。比如说在i这个位置开始拿牌，a[i]表示在i这个位置第一个人能拿到的最多分数，b[i]表示另一个人能拿到的最多分数。那么a[i] 就应该在 sum[ i - i + k] + b[ i + k], k 小于3 ，之间挑一个值，相应的能够算出b[i]来，不知道我说清楚了没有。

想问一下关于第五题，每次拿的时候，是只知道前三张是多少值，还是后面所有牌的值和顺序都是知道的

楼主，第二题是一个图问题吧。比如a->ab代表a指向ab，那么，需保证每个节点的入度小于等于出度？因为入度大于出度的话每次迭代此节点个数一定增长，最后不能stable.

多谢楼主分享。
1. 请问数据量大是要如何处理？followup 线性增长那问有些没看明白，能否再解释下，谢谢。
2. 最后stable是图有环吧？

wtcupup 发表于 2018-6-20 12:48
第三轮可能是这个 https://leetcode.com/problems/rectangle-area-ii/description/ ？

感觉好像不太像

ws775901 发表于 2018-6-21 04:05
楼主，第二题是一个图问题吧。比如a->ab代表a指向ab，那么，需保证每个节点的入度小于等于出度？因为入度大 ...

这我就不知道了。 比如说，上面那个例子，a变ab，b变c，c变没，我感觉里面没有环啊，但是它怎么变，都还是abc。

感谢分享！祝好运！

chenjunren0406 发表于 2018-6-21 04:31
1.数据量大，我基本上就是胡喷，大致就是按照某个规矩（比如说按照user id），hash到 多个机子上算，算完 ...

好的，十分感谢！