一亩三分地论坛

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

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

1/6 谷歌 电面

[复制链接] |试试Instant~ |关注本帖
xiaoluo2002 发表于 2016-1-8 06:13:42 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
印度大哥,不太友善,上来聊了两句就开始做题。.1point3acres缃
不贴题目,然后带着印度口音口述了题目,我没怎么听懂,然后问他有没有example给我一个,如下:
. From 1point 3acres bbs
大意是有一个办公室,in代表进入办公室的时间,out表示出办公室的时间, 每一个event都有in和out两个参数. 1point3acres.com/bbs

A in:5 out:10
C in:12 out: 15. visit 1point3acres.com for more.
D in: 25 out:30
B in:7 out:13
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
求最长的办公室被连续占用的区间. visit 1point3acres.com for more.
上面连续占用为 [5, 15], [25, 30]。因为要求最长的,所以返回[5,15]。

我的方法是按照 in 的时间进行排序,然后就维护最长区间的两个变量就行了。复杂度 nlogn,
但是印度大哥一定要我优化,我实在想不出怎么优化复杂度了,印度大哥一点提示也没有然后也不说话,我无奈之下随便扯了一点数据比较大什么的。
163 发表于 2016-1-8 09:56:56 | 显示全部楼层
简直是纯坑呀。个人认为这个题不太可能有O(n)的算法,试想如果新读入一个区间,怎么也得至少用类似binary search的方法和之前的区间排出一个 “大小关系” 来。否则根本就没有order可言,何来 “最长最短” 呢。
回复 支持 1 反对 0

使用道具 举报

aiwojiujiu 发表于 2016-1-8 09:16:47 | 显示全部楼层
印度人真的纯坑。。。感觉楼主的解法算标准了
回复 支持 反对

使用道具 举报

douch 发表于 2016-1-8 09:22:08 | 显示全部楼层
丫估计要类似于bucket的做法? lz也被老印坑过,lz在思考的时候,丫挺的把我坑里带,还好面完立马投诉,拿了个二面。
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-8 09:25:55 | 显示全部楼层
douch 发表于 2016-1-8 09:22
丫估计要类似于bucket的做法? lz也被老印坑过,lz在思考的时候,丫挺的把我坑里带,还好面完立马投诉,拿 ...

印度人真的纯坑 看见中国人就不给好脸  我面过无数次  基本都是跪印度人那了  明明算法是对的 自己不明白还给我个差评 艹
回复 支持 反对

使用道具 举报

 楼主| xiaoluo2002 发表于 2016-1-8 09:40:49 | 显示全部楼层
aiwojiujiu 发表于 2016-1-8 09:25. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
印度人真的纯坑 看见中国人就不给好脸  我面过无数次  基本都是跪印度人那了  明明算法是对的 自己不明白 ...

哎,我现在碰见印度人真是一头包。。。。他脸黑的不行。。我还要扮笑脸这才是最悲剧的。。。
回复 支持 反对

使用道具 举报

ChrisGates23 发表于 2016-1-8 09:42:19 | 显示全部楼层
merge interval?
回复 支持 反对

使用道具 举报

 楼主| xiaoluo2002 发表于 2016-1-8 09:42:55 | 显示全部楼层
douch 发表于 2016-1-8 09:22
丫估计要类似于bucket的做法? lz也被老印坑过,lz在思考的时候,丫挺的把我坑里带,还好面完立马投诉,拿 ...
. from: 1point3acres.com/bbs
用bucket能满足线性复杂度吗?我还是想不太出来。。。
回复 支持 反对

使用道具 举报

 楼主| xiaoluo2002 发表于 2016-1-8 09:45:30 | 显示全部楼层

merge interval的前提是interval的第一个参数是有序的。。。如果排序了就nlogn了。。。。这个题明确说了是无序的
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-1-8 09:56:35 | 显示全部楼层
觉得楼主做的很好啊,要不要给HR发邮件反馈下?我觉得答出来就肯定不会挂 放心吧
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-5 12:42:35 | 显示全部楼层
这个应该不能优化了吧,时间空间都很难优化啊
回复 支持 反对

使用道具 举报

seashell199005 发表于 2016-2-5 13:17:48 | 显示全部楼层
楼主这个是pass了呀,这么做对了呀
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-2-5 13:38:53 | 显示全部楼层
应该是可以用union find吧,都union起来以后再扫一遍。
回复 支持 反对

使用道具 举报

tianchijushi 发表于 2016-2-5 14:15:52 | 显示全部楼层
segment tree 似乎可以
回复 支持 反对

使用道具 举报

木木 发表于 2016-2-5 14:37:03 | 显示全部楼层
douch 发表于 2016-1-8 09:22
丫估计要类似于bucket的做法? lz也被老印坑过,lz在思考的时候,丫挺的把我坑里带,还好面完立马投诉,拿 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
求问面完怎么投诉?给安排面试的HR说嘛?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-5 15:27:43 | 显示全部楼层
comicrudy 发表于 2016-2-5 13:38.鐣欏璁哄潧-涓浜-涓夊垎鍦
应该是可以用union find吧,都union起来以后再扫一遍。

能否详细说说UF怎么做呢?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-5 15:28:00 | 显示全部楼层
tianchijushi 发表于 2016-2-5 14:15
segment tree 似乎可以

能否详细说说ST怎么做呢?Tree的每个Node存什么内容?
回复 支持 反对

使用道具 举报

royal_916 发表于 2016-2-11 23:59:09 | 显示全部楼层
感觉这题貌似常看到啊,mark一下等大神解答做法,另外赞lz  踩烙印
回复 支持 反对

使用道具 举报

ecclesiastic 发表于 2016-3-4 13:53:32 | 显示全部楼层
这是leetcode 几乎是原题 meeting rooms II,就把原来的做法里算房间改成加时间就行,最优的是 O(n)
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-3-4 14:07:11 | 显示全部楼层
ecclesiastic 发表于 2016-3-4 13:54
这是leetcode 几乎是原题 meeting rooms II,就把原来的做法里算房间改成加时间就行,最优的是 O(n)

那个题我暂时只看到有O(n lg n)的解法https://leetcode.com/discuss/que ... g-rooms-ii?sort=hot,O(n)解法的思路是?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 11:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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