G家电面

路过的小伙伴分享一下思路吧。我没太懂hash解法 可否简单说一下？

我只有最弱的方法： 遍历时间戳 当出现大于“当前时间戳+自定义的短时间” 的时间戳出现 就输出 当然细节还要处理NAN的情况 不过时间复杂度都一样 就是o(n)了。。也可能我理解不对 求帮忙打开思路

无法想象O（1）啊 输出都是 n / sample interval 了吧 也就相当于0（n）了  顺便问一下时间戳不是排好序的么？（抱歉不是太懂时间戳）

没看懂
无论是否排序，读一遍数据不是也需要O(N)了吗？
难道是map reduce神马的?

cztianshi 发表于 2014-8-15 13:40
下周也要电面了，感觉各种不靠谱。。。。

google啊。那是大牛才能过的面试。

littlecoolblaxk 发表于 2014-8-22 05:23
无法想象O（1）啊 输出都是 n / sample interval 了吧 也就相当于0（n）了  顺便问一下时间戳不是排好序的 ...

sorry，我说的是空间复杂度O(1), 时间复杂度是O(n)

面试官说可以in place的算法。。

O(1) place 应该不能hash了吧
输入可以自己定义吗？ 线性表的话，因为要插入NaN 应该不能用array
那为什么我觉得用一个linkedlist就OK？
求大牛来指正~

如果时间戳按照顺序给，可以记录前一个时间戳和前一个时间戳有没有输出，如果前一个和当前的在一个时间点的附近，并且输出了，当前就不输出了，不然就输出下呗
这里按照顺序指在一个时间点周围的都是连续给出的
不知道这样行不