1/6 谷歌 电面

印度大哥，不太友善，上来聊了两句就开始做题。
不贴题目，然后带着印度口音口述了题目，我没怎么听懂，然后问他有没有example给我一个，如下：

大意是有一个办公室，in代表进入办公室的时间，o

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

优化，我实在想不出怎么优化复杂度了，印度大哥一点提示也没有然后也不说话，我无奈之下随便扯了一点数据比较大什么的。

简直是纯坑呀。个人认为这个题不太可能有O(n)的算法，试想如果新读入一个区间，怎么也得至少用类似binary search的方法和之前的区间排出一个 “大小关系” 来。否则根本就没有order可言，何来 “最长最短” 呢。

douch 发表于 2016-1-8 09:22
丫估计要类似于bucket的做法？ lz也被老印坑过，lz在思考的时候，丫挺的把我坑里带，还好面完立马投诉，拿 ...

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

bobzhang2004 发表于 2016-3-9 09:02
这个题应该就是merge interval，然后检测每个interval的长度吧。如果改进的话，就是开一个24*60*60的array, ...

请问你这个算法的意思是如果有个event是[5, 10]那就把5到10都标记成true吗？如果是的话，假如给你n个event都是[1, 1440]咋办呢。。

印度人真的纯坑。。。感觉楼主的解法算标准了

丫估计要类似于bucket的做法？ lz也被老印坑过，lz在思考的时候，丫挺的把我坑里带，还好面完立马投诉，拿了个二面。

aiwojiujiu 发表于 2016-1-8 09:25
印度人真的纯坑 看见中国人就不给好脸  我面过无数次  基本都是跪印度人那了  明明算法是对的 自己不明白 ...

哎，我现在碰见印度人真是一头包。。。。他脸黑的不行。。我还要扮笑脸这才是最悲剧的。。。

merge interval?

douch 发表于 2016-1-8 09:22
丫估计要类似于bucket的做法？ lz也被老印坑过，lz在思考的时候，丫挺的把我坑里带，还好面完立马投诉，拿 ...

用bucket能满足线性复杂度吗？我还是想不太出来。。。

ChrisGates23 发表于 2016-1-8 09:42
merge interval?

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

觉得楼主做的很好啊，要不要给HR发邮件反馈下？我觉得答出来就肯定不会挂 放心吧