推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 2308|回复: 10
收起左侧

Google Intern 电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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才行,他让我描述了下做法
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赶紧纠正。. 1point 3acres 璁哄潧
然后最后弥补了迟到的五分钟让我问了问问题结束。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
希望能尽早拿到好的feedback :)
也祝大家顺利 :)




评分

1

查看全部评分

本帖被以下淘专辑推荐:

jiongjiongyoush 发表于 2016-11-12 09:45:47 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
第一题要用binary index tree?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

jiongjiongyoush 发表于 2016-11-12 10:38:18 | 显示全部楼层
wey066 发表于 2016-11-12 10:35. visit 1point3acres.com for more.
我想到的第一个解法就是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
是的.....所以从这点看我运气不错 = =.....我跟他说BIT然后问他能不能get到我idea,他说可以,我就开开心 ...

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

使用道具 举报

crosslife 发表于 2016-12-16 13:02:10 | 显示全部楼层
第二题如果确保是vaild的字符串的话,直接把asscil码加起来就行了,两个相减就行了
回复 支持 反对

使用道具 举报

garycheck 发表于 2016-12-18 15:01:03 | 显示全部楼层
我也感觉他是让你XOR
回复 支持 反对

使用道具 举报

wangyishuo123 发表于 2017-1-4 15:21:41 | 显示全部楼层
follow 5可以用map吧 建立两个map<Character, Integer>. 遍历第一个map 通过key看是否和第二个map的value一样
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-28 16:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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