一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1868|回复: 18
收起左侧

Google 电面两轮

[复制链接] |试试Instant~ |关注本帖
mnmunknown 发表于 2016-8-31 04:16:08 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Passfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近三周面的,前两天刚接到电话安排了 onsite,后面的因为 NDA 估计就没法直接贴面经了,争取换个其他形式吧。几个月来窝在地里潜水看了不少面经,也贡献下自己的一份吧,也当攒攒人品~
. 鍥磋鎴戜滑@1point 3 acres
第一轮电面:

       美国小哥,口音和名字来看应该是个白人 native speaker. 简单问了简历之后就扔出来一道题,LC308. 这题之前我准备过,本来觉得比较合适的是从 1D 的情况然后慢慢过渡到 2D ,从 immutable 过渡到 mutable ,期间你来我往谈笑风生一番。。然而我想多了,小哥直接拍了个 2D mutable 的原题上来,我的内心对这种生硬的开局其实是比较拒绝的。。。。说了 brute foce 之后很快讲了 fenwickTree,小哥 “哦” 了一声想开始听我讲 fenwick tree 的原理,lz 平常做题的时候喜欢画图,然而隔着一个 google docs 非常抓瞎,询问了下能不能我去 google 一下找个 fenwick tree 的图贴过来咱俩比划,小哥不同意,说没事,你就这么给我讲就行(。。。。) 于是想了一想先从 binary heap 的结构入手,讲一下 1D array 的线性数组可以通过 bit manipulation 表示一个树状的结构,想由此引出 “树状数组” 和 “位运算” 进入 fenwick tree 的描述,然而悲剧的发现在这两个概念的实现上双方无法达成共识。。小哥一直觉得用数组 + 位运算表示 heap 很奇怪而且问我为什么要提 heap .... 反复讨论了十几分钟小哥稍微有点不耐烦了,让我写 code,几分钟撸完,中间穿插了讲解。之后小哥陷入了短暂的沉默,可能他在想为什么这个人 fenwick tree 描述的云里雾里但是 code 又能写出来。。。比较庆幸的是 code 写完之后小哥的态度缓和了很多,也同意我对时间复杂度的分析描述。最后挺不好意思给小哥道歉说我学过这个结构但是隔着 google docs 有点画不明白,要不你给我留个联系方式我挂了电话画好图再发给你?小哥哈哈笑了下说:别担心,我也承认 google docs 画画挺烂的。。

-google 1point3acres
       两天后接到 hr 电话说反馈不太明朗,面试官不太确定我的 coding 能力如何,建议加面。算是有惊无险。

. 1point3acres.com/bbs
第二轮电面:.鏈枃鍘熷垱鑷1point3acres璁哄潧

       国人大哥,念完自己英文名字之后还字正腔圆用普通话念了一遍,作为回应我也用普通话念了一遍自己的名字,短暂的两句话中包含了大量的信息,效果大概等同于 “天王盖地虎” “宝塔镇河妖” “脸红什么” “精神焕发” “怎么又黄了” “防冷涂的蜡”。 你感受下~

       题不难,都是 two pointer 的 sliding window, 第一问是找数组中最长的连续子序列,第二问就是 LC340,过渡的比较自然,follow up 是如果输入是 steam of string,内存存不下整个 window 的时候,怎么样还能高效维护当前算法的 window 信息。写完 code 问了下时间复杂度。个人感觉这轮的面试官对题目的设计和准备就合理许多,很顺利就写完了,感谢国人大哥不刁难人~

评分

1

查看全部评分

chestnut9919 发表于 2016-8-31 06:00:23 | 显示全部楼层
电话里到底怎么讲BIT才能讲明白啊 太难了
回复 支持 1 反对 0

使用道具 举报

zq13667243992 发表于 2016-8-31 06:22:45 | 显示全部楼层
请问一下,内存存不下整个 window 的时候 该怎么做??谢谢
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2016-8-31 06:25:27 | 显示全部楼层
zq13667243992 发表于 2016-8-31 06:22
请问一下,内存存不下整个 window 的时候 该怎么做??谢谢

向右扩张窗口是不受影响的,左面缩减窗口会有影响因为不能像 LC 那样直接找到最左面的 char 然后减去出现次数。所以需要存的信息是相对于 window 里面的每个出现的字母,与位置相关~ 这个 follow up 没有原题难,建议稍微想一下就能想出来了
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2016-8-31 06:59:15 | 显示全部楼层
chestnut9919 发表于 2016-8-31 06:00
电话里到底怎么讲BIT才能讲明白啊 太难了

我也不知道。。我确实尽力了。。
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-8-31 07:08:11 | 显示全部楼层
电话第一题直接抛这个,太难了
回复 支持 反对

使用道具 举报

swly 发表于 2016-8-31 09:01:04 | 显示全部楼层
电话里让你讲BIT,太发指了
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-8-31 22:04:00 | 显示全部楼层
mnmunknown 发表于 2016-8-30 15:25
向右扩张窗口是不受影响的,左面缩减窗口会有影响因为不能像 LC 那样直接找到最左面的 char 然后减去出现 ...

楼主,你这个解释我没看明白就是说内存里面存不下整个window,不能直接get到window最左边的pointer然后移动是吧,那你是怎么解决的呢? “相对于 window 里面的每个出现的字母”是啥意思呢。。
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2016-8-31 22:10:14 | 显示全部楼层
xpli521 发表于 2016-8-31 22:04. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主,你这个解释我没看明白就是说内存里面存不下整个window,不能直接get到window最左边的point ...

假如你当前 window 最左边出现了很多个 'A' ,如 AAAABCD,相对于 A 而言你的窗口向左缩小的过程中,直到删除最后一个 A 之前,其实 window 里面的 number of distinct character 的数量没变化,也不需要存到内存里,所以你只需要记录每个字母在 window 里最靠右的出现位置就行了,你需要维护的信息数量就和字符串的字母表成正比,而不再是 window size,这么解释的话会不会清楚一点 =。=
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-8-31 22:29:54 | 显示全部楼层
God bless you, god bless me, and god bless others.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hxtang 发表于 2016-8-31 22:45:00 | 显示全部楼层
我想了一下要大概能说明问题的Fenwick tree至少要有7个node。我刚刚测了一下画这个图大概花20-30秒(照图抄,如果边想边画可能1分钟吧)。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        0
                 /      |       \
             1         2         4
                        |         / \
                        3       5   6           
然后分三步讲:
1.先讲父子关系,可以举个例子,比如6的parent是4。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
2.然后讲每个node存什么,以及prefix sum怎么算的。可以拿6举个例。-google 1point3acres
3.然后讲更新叶子结点需要更新哪些非叶结点。定义后继关系,需要拿3,5分别举例子。
到这里Fenwick tree算大致讲完,我刚试了一下,大概5-7分钟吧。但前提是面试官自己是懂的或者不纠缠细节(比如后继为什么是那个bit op),只是来验证你是不是真懂...碰到不懂还非要问细节的感觉没辙.... 1point3acres.com/bbs

当然,直接上来就拍一个2D Fenwick tree的,太不友好了.... more info on 1point3acres.com
. visit 1point3acres.com for more.

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

tigercode 发表于 2016-8-31 22:48:36 | 显示全部楼层
第一题BIT应该不是面试官想要的答案,不知道他想要的答案是什么?
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-8-31 23:23:45 | 显示全部楼层
mnmunknown 发表于 2016-8-31 07:10
假如你当前 window 最左边出现了很多个 'A' ,如 AAAABCD,相对于 A 而言你的窗口向左缩小的过程中,直到 ...
. From 1point 3acres bbs
哦哦,相当清楚了!谢谢楼主!
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-1 03:53:32 | 显示全部楼层
两个LC 加密的hard题,要不要怎么凶残。。
回复 支持 反对

使用道具 举报

whisperty 发表于 2016-9-2 05:53:55 | 显示全部楼层
mnmunknown 发表于 2016-8-31 22:10
假如你当前 window 最左边出现了很多个 'A' ,如 AAAABCD,相对于 A 而言你的窗口向左缩小的过程中,直到 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
那不能用left pointer的话,我是不是得用个堆来得到窗口中最靠左的字符,删除这个字符得到最新的窗口大小呢?
回复 支持 反对

使用道具 举报

zhucaiyi1234 发表于 2016-9-2 08:57:49 | 显示全部楼层
问下楼主 ACBE 中的ACB 算连续子序列么 (就是想问连续子序列的顺序能不能乱)?
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2016-9-2 22:07:17 | 显示全部楼层
whisperty 发表于 2016-9-2 05:53
那不能用left pointer的话,我是不是得用个堆来得到窗口中最靠左的字符,删除这个字符得到最新的窗口大小 ...

恩,我当时就是这么答的
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2016-9-2 22:07:55 | 显示全部楼层
zhucaiyi1234 发表于 2016-9-2 08:57
问下楼主 ACBE 中的ACB 算连续子序列么 (就是想问连续子序列的顺序能不能乱)?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题输入是 array of integers,5,7,9,10,11,12,13,20 这种. from: 1point3acres.com/bbs
. from: 1point3acres.com/bbs
补充内容 (2016-9-3 02:28):
顺序不能乱,连续的 subarray
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-9-4 11:48:09 | 显示全部楼层
请问楼主subarray一定要连续的吗?像 9,100,101,10,11,12这样,是返回9,10,11,12还是100,101?

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 17:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表