一亩三分地论坛

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

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

Google Intern 电面

[复制链接] |试试Instant~ |关注本帖
wey066 发表于 2016-11-12 09:09:00 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Other其他

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

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

x
11/09面的,还没feedback好心焦,因为手头暂时没其他interview了,recruiter姐姐说要一两个礼拜。一天要查好几次邮件,还有些distraction,发个面经求土地公公保佑!
两轮背靠背,感觉题目跟地里比起来简单的不像话,不知道是福是祸。

1. 听起来是国人姐姐,声音很温柔,一上来还很礼貌地为迟到两分钟解释了下
Problem:一个矩阵,支持两个操作,update一个格子,range query一个子矩阵
答:我经验比较少,直接写了二维树状数组,后来在网上查发现其他有人碰到过这个题,挂在面试官完全不知道树状数组这个结构,有些庆幸我的面试官姐姐很了解
然后让我过了个简单例子,分析了下复杂度O(logM * logN)
Follow up: query多,update少,返回去写了个sum的方法,O(MN) update, O(1) query
写完两题剩了10分钟,聊了聊天就结束了,临走时还祝我good luck on my second interview好暖

3. 听起来是个native的姐姐,也迟到了5分钟左右
Problem:有两个string,一个比另外一个多一个char,其他都一样,如"hello"和"hepllo",要找出这个char
答:简单的一次扫描,一开始忘了考虑这个char在字符串末尾,面试官让我自己出了个数据发现了这个bug,改了
Follow up: 我在写第一个的时候念叨了句好像可以binary search,面试官让我详细思考下,我想了下发现要no consecutive same character才行,他让我描述了下做法. from: 1point3acres.com/bbs
Follow up2: 如果要检查两个字符串是否满足Problem描述的关系要怎么做,我说了找出第一个不同后继续扫描,他让我写了代码
Follow up3: 如果可以打乱顺序怎么解,如"hello"和"lelloh",我说用bucket记录下出现次数,他让我写了
Follow up4: 如果字典太大,用bucket开销太大怎么办,我说用sort再用follow up2里的方法,他没让我写代码
Follow up5: 如果不能改变字符串怎么办?我想了30秒想不出很好的方法,他说想不到的话ok,我说我唯一的思路就是brute force一一匹配,开销是O(N^2)time,O(N)space,他没表态(不知道这里有没有更好的方法)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴最后他范围follow up4问我sort方法,包括快排worst case,以及稳定的NlogN方法(我说heapsort),然后我嘴贱地说merge sort,他问我空间复杂度,我一想发现需要额外的NlogN space赶紧纠正。
然后最后弥补了迟到的五分钟让我问了问问题结束。

希望能尽早拿到好的feedback :)
也祝大家顺利 :)
-google 1point3acres



评分

1

查看全部评分

本帖被以下淘专辑推荐:

jiongjiongyoush 发表于 2016-11-12 09:45:47 | 显示全部楼层
第一题要用binary index tree?
回复 支持 反对

使用道具 举报

iammajian 发表于 2016-11-12 10:17:15 | 显示全部楼层
最后一题是想让用xor吧?
回复 支持 反对

使用道具 举报

 楼主| wey066 发表于 2016-11-12 10:35:49 | 显示全部楼层
jiongjiongyoush 发表于 2016-11-12 09:45
第一题要用binary index tree?
. from: 1point3acres.com/bbs
我想到的第一个解法就是BIT。。。。
回复 支持 反对

使用道具 举报

jiongjiongyoush 发表于 2016-11-12 10:38:18 | 显示全部楼层
wey066 发表于 2016-11-12 10:35
我想到的第一个解法就是BIT。。。。

BIT好难解释==
回复 支持 反对

使用道具 举报

 楼主| wey066 发表于 2016-11-12 10:39:06 | 显示全部楼层
iammajian 发表于 2016-11-12 10:17
最后一题是想让用xor吧?

精妙!不过xor没办法验证invalidation吧
回复 支持 反对

使用道具 举报

 楼主| wey066 发表于 2016-11-12 10:48:30 | 显示全部楼层

是的.....所以从这点看我运气不错 = =.....我跟他说BIT然后问他能不能get到我idea,他说可以,我就开开心心写代码了...
回复 支持 反对

使用道具 举报

jiongjiongyoush 发表于 2016-11-12 10:52:34 | 显示全部楼层
wey066 发表于 2016-11-12 10:48. from: 1point3acres.com/bbs
是的.....所以从这点看我运气不错 = =.....我跟他说BIT然后问他能不能get到我idea,他说可以,我就开开心 ...

国人姐姐一定刷过lc 哈哈哈
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 19:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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