一道很难的面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道很难的面试题

一道很难的面试题# JobHunting - 待字闺中

y*u2012-10-09 07:10

1 楼

公司名就不说了，面试官要求实现一个queue,要求：
enqueue, dequeue, min, max, median 全部在o(1)。。。彻底败了。。。板上的各位
有没有什么想法啊？

n*n2012-10-09 07:10

2 楼

如果interviewer有答案的话，可以发篇paper出来，下届的图灵奖就是他的

l*a2012-10-09 07:10

3 楼

enqueue, dequeue, min, max都可以实现。
median要求O（1）有点强人所难了。

y*u2012-10-09 07:10

4 楼

是啊，我也是说了前四个O(1)的方法，他好像很不满意的样子。。。

【在 l*****a 的大作中提到】

: enqueue, dequeue, min, max都可以实现。
: median要求O（1）有点强人所难了。

J*u2012-10-09 07:10

5 楼

这是面a家aws secret project team的题?

h*92012-10-09 07:10

6 楼

stack的min,max容易，但queue的min,max怎样做？

【在 l*****a 的大作中提到】

: enqueue, dequeue, min, max都可以实现。
: median要求O（1）有点强人所难了。

a*l2012-10-09 07:10

7 楼

说简单也很简单，做一个异步的进程，随时更新，就可以了。当然，这种做法基本上等
于是作弊。

【在 y**u 的大作中提到】

: 公司名就不说了，面试官要求实现一个queue,要求：
: enqueue, dequeue, min, max, median 全部在o(1)。。。彻底败了。。。板上的各位
: 有没有什么想法啊？

l*a2012-10-09 07:10

8 楼

错了。想成stack了。
看看careercup第四版的20.9就知道O（1）的median是不可能的。

【在 h**********9 的大作中提到】

:
: stack的min,max容易，但queue的min,max怎样做？

f*72012-10-09 07:10

9 楼

using a min-heap, a max-heap, and a median variable to implement a data
structure to fetch median of a integer stream in O(1) time. of course, it
requires additional storage.

c*t2012-10-09 07:10

10 楼

if you need maintain heaps, how can dequeue and enqueue be O(1) time?

【在 f*****7 的大作中提到】

: using a min-heap, a max-heap, and a median variable to implement a data
: structure to fetch median of a integer stream in O(1) time. of course, it
: requires additional storage.

f*72012-10-09 07:10

11 楼

heap是单独维护的，元素还是往queue里放。
这题显然是把常见题综合起来的啊
对外是个conceptual queue
内部多用了很多存储实现那些O(1)操作
为了出题而出题吧。

【在 c********t 的大作中提到】

: if you need maintain heaps, how can dequeue and enqueue be O(1) time?