B*******1
发帖数: 2454 | 1 Ask longtime ago on this board. But did not get a good answer.
http://www.careercup.com/question?id=9786128
Implement a stack that pops out the most frequently added item. Stack
supports 3 functions - push, pop,and top. Give complexity of each functions
in your implementation. |
a*******6
发帖数: 520 | 2 push and pop can be implemented as the insert and delete in a hash table
(or a BST) in O(1) (or O(logn)) time, with the frequency associated
Also maintain a two-level linked list of all the elements (grouping
elements with the same frequency together)... when the frequency of an
element +1 or -1 (push or pop), move this element to the next or the
previous group or create a new group, in O(1) time...
functions
【在 B*******1 的大作中提到】
: Ask longtime ago on this board. But did not get a good answer.
: http://www.careercup.com/question?id=9786128
: Implement a stack that pops out the most frequently added item. Stack
: supports 3 functions - push, pop,and top. Give complexity of each functions
: in your implementation.
|
z****u
发帖数: 104 | 3 感觉和 LRU 很像，不过 LRU 是记录每个元素出现的先后，这个是元素出现的次数
用 hash + heap
hash 用来 O(1) access 对应的地址；按照出现次数来维护 heap。
每次 push 和 pop 的时候需要对他在 heap 中的 node 做up-heapify 或 down-
heapify，心元素的话就是 heap 的 insert，最坏情况都是 O(lgn)
top 是 O(1)
functions
【在 B*******1 的大作中提到】
: Ask longtime ago on this board. But did not get a good answer.
: http://www.careercup.com/question?id=9786128
: Implement a stack that pops out the most frequently added item. Stack
: supports 3 functions - push, pop,and top. Give complexity of each functions
: in your implementation.
|
s******n
发帖数: 3946 | 4 heapify的时候不光是这个node，其他node的index也变了，还得改hashtable，平均插
入一个node要log(n)次查询hashtable。
【在 z****u 的大作中提到】
: 感觉和 LRU 很像，不过 LRU 是记录每个元素出现的先后，这个是元素出现的次数
: 用 hash + heap
: hash 用来 O(1) access 对应的地址；按照出现次数来维护 heap。
: 每次 push 和 pop 的时候需要对他在 heap 中的 node 做up-heapify 或 down-
: heapify，心元素的话就是 heap 的 insert，最坏情况都是 O(lgn)
: top 是 O(1)
:
: functions
|
z****u
发帖数: 104 | 5 不用 array 做 heap，用 double linked list 可行么？
heap 的结构更复杂了，不过不存在其它node更改index 和更改 hashtable 的问题
【在 s******n 的大作中提到】
: heapify的时候不光是这个node，其他node的index也变了，还得改hashtable，平均插
: 入一个node要log(n)次查询hashtable。
|
H***e
发帖数: 476 | 6 call this a stack is very misleading
should only call it data structure
functions
【在 B*******1 的大作中提到】
: Ask longtime ago on this board. But did not get a good answer.
: http://www.careercup.com/question?id=9786128
: Implement a stack that pops out the most frequently added item. Stack
: supports 3 functions - push, pop,and top. Give complexity of each functions
: in your implementation.
|
