1.

Which data structures are used for implementing LRU cache?

Answer»

LRU cache or Least Recently Used cache allows quick identification of an element that hasn’t been put to use for the longest time by organizing items in order of use. In order to achieve this, two data structures are used:



  • Queue – This is implemented using a doubly-linked list. The maximum size of the queue is determined by the cache size, i.e by the total number of available frames. The least recently used pages will be near the front end of the queue whereas the most recently used pages will be towards the rear end of the queue.


  • Hashmap – Hashmap stores the page number as the key along with the address of the corresponding queue node as the value.


Discussion

No Comment Found

Related InterviewSolutions