1/6 谷歌 电面

wanyisjtu 发表于 2016-3-5 00:40
那非要优化到O(n)只能纯哈希了，但是space就不知道有多大了。

如何纯Hash呢？说下大概思路？

没明白这道题意，给的测试用例也没看懂，能不能解释一下呢？
不过如果start和end都是整数的话，那么排序这个环节可以在O(n)的时间内用bucket sort搞定，后面的扫描也是O(n)的，所以整个是O(n)的。

这个题应该就是merge interval，然后检测每个interval的长度吧。如果改进的话，就是开一个24*60*60的array, 然后被占用了就记为true？

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

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

liuqi627 发表于 2016-3-8 00:31
没明白这道题意，给的测试用例也没看懂，能不能解释一下呢？
不过如果start和end都是整数的话，那么排序这 ...

bucket sort＋merge interval go through list 就是o（n）了

建一个有线队列如何

cx00001 发表于 2016-4-2 02:25
bucket sort＋merge interval go through list 就是o（n）了

请问如何bucket sort?

关注一下有没有O(n)算法