google 一题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

google 一题

google 一题# JobHunting - 待字闺中

h*g2011-04-19 07:04

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*p2011-04-19 07:04

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*a2011-04-19 07:04

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*p2011-04-19 07:04

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*y2011-04-19 07:04

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*p2011-04-19 07:04

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*e2011-04-19 07:04

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*p2011-04-19 07:04

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*e2011-04-19 07:04

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