An interview question that is becoming popular (apparently British Petroleum folks have been asking in their interview) is design LRU cache. The catch is - each item has a TTL & a certain priority specified while the key, value is put into the cache. The eviction policy when cache is full is in the order
- evict all (or just the oldest expired value) based on TTL, if this makes space, good enough
- if nothing to evict as nothing has expired, remove the one with the lowest priority
- if there are multiple items with the lowest priority, remove the one that was accessed the first
The problem is pretty hard to even come up with a solution in an hour. You also need to write code of whatever solution you could find. The tradition LRU cache is designed as hashmap & a doubly linked linkedlist. Doubly linked linkedlist helps because the access time of keys are linear & you need to move the accessed key to the top of the linked list & remove the oldest item.
In this cas