y**u
发帖数: 28 | 1 公司名就不说了，面试官要求实现一个queue,要求：
enqueue, dequeue, min, max, median 全部在o(1)。。。彻底败了。。。板上的各位
有没有什么想法啊？ |
n******n
发帖数: 567 | 2 如果interviewer有答案的话，可以发篇paper出来，下届的图灵奖就是他的 |
l*****a
发帖数: 559 | 3 enqueue, dequeue, min, max都可以实现。
median要求O（1）有点强人所难了。 |
y**u
发帖数: 28 | 4 是啊，我也是说了前四个O(1)的方法，他好像很不满意的样子。。。
【在 l*****a 的大作中提到】
: enqueue, dequeue, min, max都可以实现。
: median要求O（1）有点强人所难了。
|
J***u
发帖数: 18 | 5 这是面a家aws secret project team的题? |
h**********9
发帖数: 3252 | 6
stack的min,max容易，但queue的min,max怎样做？
【在 l*****a 的大作中提到】
: enqueue, dequeue, min, max都可以实现。
: median要求O（1）有点强人所难了。
|
a****l
发帖数: 8211 | 7 说简单也很简单，做一个异步的进程，随时更新，就可以了。当然，这种做法基本上等
于是作弊。
【在 y**u 的大作中提到】
: 公司名就不说了，面试官要求实现一个queue,要求：
: enqueue, dequeue, min, max, median 全部在o(1)。。。彻底败了。。。板上的各位
: 有没有什么想法啊？
|
l*****a
发帖数: 559 | 8 错了。想成stack了。
看看careercup第四版的20.9就知道O（1）的median是不可能的。
【在 h**********9 的大作中提到】
:
: stack的min,max容易，但queue的min,max怎样做？
|
f*****7
发帖数: 92 | 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********t
发帖数: 5706 | 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*****7
发帖数: 92 | 11 heap是单独维护的，元素还是往queue里放。
这题显然是把常见题综合起来的啊
对外是个conceptual queue
内部多用了很多存储实现那些O(1)操作
为了出题而出题吧。
【在 c********t 的大作中提到】
: if you need maintain heaps, how can dequeue and enqueue be O(1) time?
|
C***y
发帖数: 2546 | 12 dequeue的时候你怎么从heap里做到O（1）删除？
【在 f*****7 的大作中提到】
: heap是单独维护的，元素还是往queue里放。
: 这题显然是把常见题综合起来的啊
: 对外是个conceptual queue
: 内部多用了很多存储实现那些O(1)操作
: 为了出题而出题吧。
|
f*****7
发帖数: 92 | 13 哦，也是。。heap也得维护，也得对应着删除元素
一下没招了
anyway，那个O(1)的median算法很重要。
【在 C***y 的大作中提到】
: dequeue的时候你怎么从heap里做到O（1）删除？
|
