Google | 迟来的实习面经 + 冬转夏时间线

时间线：
- 2018-7-16 投全职和实习的简历
- 2018-7-16 当天收到全职的 OA
- 2018-7-24 收到实习 OA
- 2018-7-26 OA
- 2018-7-27 预约面试
- 2018-8-30 13:00 - 15:00 PDT 背靠背
- 2018-8-30 15:33 PDT 送 Hiring Committee
- 2018-9-18 进 match
- 呜呜呜呜呜呜一个面试也没拿到
- 2018-11-26 申请换 summer pool
- 2018-12-3 换 summer pool
- 2018-12-5 拿到两个 host 面试
- 2018-12-12 背靠背 host 面试，同时得知 HR 不在谷歌了
- 2018-12-14 新的 HR 联系并且通知两个组都可以发 offer


~~~~

本来拿了全职 OA，因为我十二月份毕业想，第二年秋季读研，所以不能申请全职，然后要我 confirm 我会去读研，就说我只申请实习就好了。说完马上有了实习 OA。

OA：

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

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

后来预约面试，只能约一周多以后的。我说我实习完马上要回国浪了，申请到美国再面。

背靠背一面：

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

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

背靠背二面：

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

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

运气好，题目都不难


补充内容 (2019-1-7 09:19):
楼下一位朋友提醒 一面思路有点像

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

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

betterztt 发表于 2018-12-22 15:03
想请问一下楼主 第一题connect four 什么思路呀～

一开始我暴力解，时间空间复杂度 O(n)。后来他要求判断游戏是否结束需要 O(1)。

我最后的做法大概是用一个哈希表存每个端点所在的 `X` 数组的起始和终点，key 是 index，value 是起点终点。_ _ X X _ X X _ 就是 {2: [2, 3], 3: [2, 3], 5: [5, 6], 6: [5, 6]}。
关键要看的就是插入的 col 两侧原本有没有标记，如果有的话判断长度，然后更新哈希表。更新 `col` 所在的 `X` 数组两端就可以了。比如插入 1 之后看到 0 不在哈希表里就不管，2: [2, 3] 在哈希表里，并且发现长度不会超，就更新 3 对应的值，以及插入 1 对应的值，变成 {1: [1, 3], 2: [2, 3], 3: [1, 3], 5: [5, 6], 6: [5, 6]}。其实现在 2 对应的值已经没有用了，扔在那里不管就好。
插入 4 之后发现 3 和 5 都在哈希表里，算了一下长度会超，就返回 True。
edge case 不需要考虑，比如出界或者该位置已有标记，考虑一般情况就好。

看着面完试的笔记回答的，不知道有没有解释清楚

想请问一下楼主 第一题connect four 什么思路呀～

第二题

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

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

SuY 发表于 2018-12-24 16:05
一开始我暴力解，时间空间复杂度 O(n)。后来他要求判断游戏是否结束需要 O(1)。

我最后的做法大概是用 ...

有一个问题 比如第一次插入2 {2:[2,2]} 第二次 插入3 {2:[2,2],3:[2,3]} 第三次 插入1 {1:[1,2],2:[2,2],3:[2,3]}
插入3 的时候是不更新2 的， 那第三次插入1怎么检测到3 是upper bound？
如果插入3 的时候更新2， 那怎么确认什么时候要更新呢？

littlegrasscao 发表于 2019-1-3 21:23
有一个问题 比如第一次插入2 {2:[2,2]} 第二次 插入3 {2:[2,2],3:[2,3]} 第三次 插入1 {1:[1,2],2:[2,2], ...

可能之前解释得不清楚，是要更新两端的值。比如：
{1:[1,2], 2:[1,2]}，插入3，3边上的本来就存在的区间有[1,2]，不用管2但要更新1，这样就变成{1:[1,3], 2:[1,2], 3:[1,3]}
2不用更新因为面试官假设输入值都是valid的，不会重复输入1和3，所以以后永远也不会碰到2

一面是不是类似 蠡口 要而巴

lzyprint 发表于 2019-1-6 14:14
一面是不是类似 蠡口 要而巴

刚看了一下 确实很像！