I believe my friend got this question in a bbg phone interview.
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Could you do both operations in O(1) time complexity?
Hash table to support lookup. The “value” is a pointer to a link node. Link node also has key/value — 2-way linkage.
slist is a FIFO and grows at tail for every new key/value pair, so head is the earliest pair. Every time a key/value is accessed via hash table, we move the node to the tail.
When capacity is reached, we would remove the tail node. Using the key in that node, we also remove from hash table.