4

Possible Duplicate:
LRU cache design

I got this question in a programming interview. Feel free to think about how you might answer it.

How would you implement an LRU (least-recently-updated) cache in C++? Basically, the cache can hold up to N items. If a new item is inserted and the number of items in the cache is less than N, it's just inserted. But if a new item is inserted and the number of items in the cache is already N, the item that's least recently used should be removed from the cache.

Think about what running time it would take for each of your operation.

Community
  • 1
  • 1
JJ Beck
  • 5,193
  • 7
  • 32
  • 36

1 Answers1

1

I would have member of cache element that stores last access time. When element is accessed (member function is called) then access time member is updated. When cache gets full then element with smallest access time would be erased.

Other option is to have cache elements in intrusive list. When something is accessed and is not in top of list it comes to top of list. When cache is full the bottom element of list is erased. More work on each access, but the victim is quicker to find.

The basic idea is not to have typical maps and lists for such tasks, these will fragment your memory. My algorithms keep the cache constantly at one place.

Öö Tiib
  • 10,809
  • 25
  • 44
  • Sure, that should work, but you would have to go through all the elements to find the one with smallest access time. – JJ Beck Oct 27 '12 at 23:12
  • Ok i added other algorithm that might make sense on case of very lot of cache elements. – Öö Tiib Oct 27 '12 at 23:22