h*****g
发帖数: 312 | 1 Design a efficient cache, supporting retrieval of maximum element in cache
along with other normal cache operations.
Suggest data structures to be used,also tell the complexities for each of
the operations.
用 heap+linkedHashmap? |
k*p
发帖数: 1526 | 2 我觉得用另一个double linked list来维护
LRU的node多一个域存放指向DLL node的指针
DLL的head始终是当前LRU maximum元素
当向LRU里面put时，如果大于DLL的head，则DLL添加一个node到head，同时把LRU新增的
node的那个域指向这个DLL的node
当LRU的tail被挤出的时候，看那个node有没有指向DLL的指针，有的话同时删除DLL里的
那个node
【在 h*****g 的大作中提到】
: Design a efficient cache, supporting retrieval of maximum element in cache
: along with other normal cache operations.
: Suggest data structures to be used,also tell the complexities for each of
: the operations.
: 用 heap+linkedHashmap?
|
p*****a
发帖数: 147 | 3 It seems you miss the case when inserting something smaller than head.
Not sure if there is an better than O(n) solution for that.
It seems to me that if we want to maintain the double linked list to be
sorted, the insertion would have to be O(n) either inserting from the tail
or from the head.
增的
里的
【在 k*p 的大作中提到】
: 我觉得用另一个double linked list来维护
: LRU的node多一个域存放指向DLL node的指针
: DLL的head始终是当前LRU maximum元素
: 当向LRU里面put时，如果大于DLL的head，则DLL添加一个node到head，同时把LRU新增的
: node的那个域指向这个DLL的node
: 当LRU的tail被挤出的时候，看那个node有没有指向DLL的指针，有的话同时删除DLL里的
: 那个node
|
k*p
发帖数: 1526 | 4 Yes, you are right. I am wrong. In such case, all elements must be kept some
where ordered, since any element could fall out. How about using BST?
【在 p*****a 的大作中提到】
: It seems you miss the case when inserting something smaller than head.
: Not sure if there is an better than O(n) solution for that.
: It seems to me that if we want to maintain the double linked list to be
: sorted, the insertion would have to be O(n) either inserting from the tail
: or from the head.
:
: 增的
: 里的
|
s*****y
发帖数: 897 | 5 So i can you determine the least recently used items?
Or this cache does not care?
some
【在 k*p 的大作中提到】
: Yes, you are right. I am wrong. In such case, all elements must be kept some
: where ordered, since any element could fall out. How about using BST?
|
k*p
发帖数: 1526 | 6 LRU still has to use double linked list + hash to implement. BST is used to
find max element. Any new element to LRU or removal of tail element needs in
sertion/deletion to BST in O(h) time.
【在 s*****y 的大作中提到】
: So i can you determine the least recently used items?
: Or this cache does not care?
:
: some
|
g**e
发帖数: 6127 | 7 linkedhashmap + max heap
put O(lgn) in worst case
get is O(1)
getMax is O(1)
to remvoe least recent use item, update heap may take O(lgn) worst case as
well.
【在 s*****y 的大作中提到】
: So i can you determine the least recently used items?
: Or this cache does not care?
:
: some
|
k*p
发帖数: 1526 | 8 removing arbitrary element from heap could be painful to write the code
【在 g**e 的大作中提到】
: linkedhashmap + max heap
: put O(lgn) in worst case
: get is O(1)
: getMax is O(1)
: to remvoe least recent use item, update heap may take O(lgn) worst case as
: well.
|
|
g**e
发帖数: 6127 | 9 if we keep the item reference and its heap index in hashmap, deleting it is
almost the same as deleting root from heap.
as
【在 k*p 的大作中提到】
: removing arbitrary element from heap could be painful to write the code
|
s****n
发帖数: 48 | 10 是不是跟那个sliding window求最大值很象？
http://www.ihas1337code.com/2011/01/sliding-window-maximum.html
【在 h*****g 的大作中提到】
: Design a efficient cache, supporting retrieval of maximum element in cache
: along with other normal cache operations.
: Suggest data structures to be used,also tell the complexities for each of
: the operations.
: 用 heap+linkedHashmap?
|
a********m
发帖数: 15480 | 11 arbitrary element 可以当作一个子树的root吧。调整在这个子树里面应该够吧？
【在 k*p 的大作中提到】
: removing arbitrary element from heap could be painful to write the code
|
