一亩三分地论坛

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

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

Google Intern面试 12.5

[复制链接] |试试Instant~ |关注本帖
lzhao403 发表于 2016-1-6 08:15:52 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
1号从国内飞到学校,时差还没完全倒回来,在国内也没好好刷题,哎,估计跪。第一轮安排的面试,面试官约不到房间,我也不知道。等了15分钟给RECRUITER打电话,说让我先面第二个。又巴巴等了40多分钟。-google 1point3acres
第一轮:
南亚口音,口音极重,听到第一句就心里咯噔了。上来介绍了名字就开始做题,题目很简单,number frequency count。 但做follow up的时候,我一直不能 get 他的意思(口音真的很重,而且不知道用了speaker还是啥,回音好重。。。),get到得时候,时间不够了,简单说了几句。

第二轮:
也是南亚口音,但口音没有那么重。人比较和蔼,上来在doc里写了自己的名字,介绍自己的组,是search组的。
题目是 max-density problem,只做了1d,没时间做2d。 自己先写了粗暴解法,后来小哥举了个非常易懂的例子,提示下优化了nlogn。面完和工作的师兄聊,原来就是著名的meeting room。。。(我是真真没有好好刷题在国内

. 1point 3acres 璁哄潧

基本上感觉非常差,不过也算是警醒自己,以后要好好刷题努力了。

评分

2

查看全部评分

xiaozhuxiaozhu 发表于 2016-1-6 08:39:06 | 显示全部楼层
什么是max density problem?
回复 支持 反对

使用道具 举报

 楼主| lzhao403 发表于 2016-1-6 08:49:03 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-6 08:39
什么是max density problem?

input本质上和meeting room一样,求的返回结果不一样。

如果用meeting room那个问题来表述就是最多同时有几个meeting在开。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-6 08:49:31 | 显示全部楼层
lz第一题的follow up是啥啊
回复 支持 反对

使用道具 举报

 楼主| lzhao403 发表于 2016-1-6 09:03:22 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-6 08:49
lz第一题的follow up是啥啊

如果我真的听懂他的意思的话是说让用更efficiency的算法或者数据结构来sort算好的frenquency。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-6 09:04:27 | 显示全部楼层
lzhao403 发表于 2016-1-6 09:03. Waral 鍗氬鏈夋洿澶氭枃绔,
如果我真的听懂他的意思的话是说让用更efficiency的算法或者数据结构来sort算好的frenquency。。。

你max density的暴力解法是怎么做的
回复 支持 反对

使用道具 举报

 楼主| lzhao403 发表于 2016-1-6 09:15:05 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-6 09:04
你max density的暴力解法是怎么做的

两层循环。

对每一个pair:
    看所有pair中的starts有多少个在这个pair range里面

返回最多的那个值

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xiaozhuxiaozhu 发表于 2016-1-6 09:16:51 | 显示全部楼层
lzhao403 发表于 2016-1-6 09:15
两层循环。

对每一个pair:

和我想的一样,可是这不是最优解吧?
你对最优有啥想法么?
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-6 09:21:59 | 显示全部楼层
LZ再能说说第一题吗
回复 支持 反对

使用道具 举报

 楼主| lzhao403 发表于 2016-1-6 09:36:07 | 显示全部楼层
xiaozhuxiaozhu 发表于 2016-1-6 09:16. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
和我想的一样,可是这不是最优解吧?
你对最优有啥想法么?

面试官给了提示,写了nlogn。
可以先把所有的time points排个序。然后直接遍历,遇到start就+1,遇到end就-1,然后keep住最大的density。.1point3acres缃
写完了面试官指出一个bug就是遇到end和start值相同的时候,算法会有错误。想了一会需要在sort的时候把值相同的start放在end前面来避免(但没实现,就标记了下)。. 1point 3acres 璁哄潧
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
复杂度就集中在sort的时候。

后来完了搜网上有没有线性解,结果都是一些paper讨论这个的:
Maximum-Density Segment
回复 支持 反对

使用道具 举报

 楼主| lzhao403 发表于 2016-1-6 09:38:09 | 显示全部楼层
jmnjmnjmn 发表于 2016-1-6 09:21
LZ再能说说第一题吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
就是一组number,统计每个unique number出现的频率。然后根据频率,对uniqe number排序
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-9 14:56:15 | 显示全部楼层
lzhao403 发表于 2016-1-6 09:38
就是一组number,统计每个unique number出现的频率。然后根据频率,对uniqe number排序

用TreeMap吧?
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-12 13:08:49 | 显示全部楼层
lzhao403 发表于 2016-1-6 09:36
面试官给了提示,写了nlogn。. more info on 1point3acres.com
可以先把所有的time points排个序。然后直接遍历,遇到start就+1,遇到end ...

还是不懂什么是max-density problem,请问lz可以再具体一点,活着提供相关题目内容的网页吗?谢谢!
回复 支持 反对

使用道具 举报

jmnjmnjmn 发表于 2016-1-12 16:33:22 | 显示全部楼层
哗啦啦 发表于 2016-1-12 13:08
还是不懂什么是max-density problem,请问lz可以再具体一点,活着提供相关题目内容的网页吗?谢谢!

1D的应该就是 max overlap interval , meeting room 那道。  2D的话应该怎么做啊  
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-1-12 21:00:54 | 显示全部楼层
楼主收到feedback了吗
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-11 11:49:42 | 显示全部楼层
请问楼主1d和2d是指什么?1d是meeting room吗?那2d是什么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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