Leetcode - LRU Cache

Question

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

This is a tesla question

• A weirdly difficult question because of the constraint that both get and put need to operate in O(1) time

• DS: cache: {key (int): Node(key, value)} and a deque to maintain our history

• We know we want to use a linked list because we want to be able to maintain a history (think browsing history), while being able to add and remove things in O(1) time

• Use head and tail pointers which are dummy pointers for tracking the least recently used and most recently used values

• Remember how to remove a node from a Linked List

• When we get new things, we need to remove our key form the linked list and then add it to the end

• When we add things, we need to remove our head value and add our new node to the end to maintain history

• O(1) insert and query time

• You can also solve it in O(logn) time using a min heap

Solution

Min heap solution