LRU Cache


LRU Cache [Very Hard]

  • Implement an LRUCache class for a Least Recently Used (LRU) cache. The class should support:
    • Inserting key-value pairs with the insertKeyValuePair method.
    • Retrieving a key’s value with the getValueFromKey method.
    • Retrieving the most recently used (the most recently inserted or retrieved) key with the getMostRecentKey method.
  • Each of these methods should run in constant time.
  • Additionally, the LRUCache class should store a maxSize property set to the size of the cache, which is passed in as an argument during instantiation. This size represents the maximum number of key-value pairs that the cache can store at once. If a key-value pair is inserted in the cache when it has reached maximum capacity, the least recently used key-value pair should be evicted from the cache and no longer retrievable; the newly added key-value pair should effectively replace it.
  • Note that inserting a key-value pair with an already existing key should simply replace the key’s value in the cache with the new value and shouldn’t evict a key-value pair if the cache is full. Lastly, attempting to retrieve a value from a key that isn’t in the cache should return None / null.

**Sample Usage **

// All operations below are performed sequentially.
LRUCache(3): - // instantiate an LRUCache of size 3
insertKeyValuePair("b", 2): -
insertKeyValuePair("a", 1): -
insertKeyValuePair("c", 3): -
getMostRecentKey(): "c" // "c" was the most recently inserted key
getValueFromKey("a"): 1
getMostRecentKey(): "a" // "a" was the most recently retrieved key
insertKeyValuePair("d", 4): - // the cache had 3 entries; the least recently used one is evicted
getValueFromKey("b"): None // "b" was evicted in the previous operation
insertKeyValuePair("a", 5): - // "a" already exists in the cache so its value just gets replaced
getValueFromKey("a"): 5


Hints

Hint 1
What data structure could allow you to insert, retrieve, and evict resources as fast as possible, all the while keeping track of the least recently accessed resource - essentially keeping track of the order of the resources? A hash table would allow you to insert and retrieve resources fast, but it wouldn't allow you to keep track of their order. An array would let you keep track of their order, but it wouldn't let you access elements fast; it also wouldn't allow you to move an element from one position to another in constant time, which you would need to do to make a newly-accessed key / value pair the most recent one upon retrieval of a key's value. A linked list would allow you to keep track of elements' order and to move them seamlessly (if you knew their position), but it wouldn't allow you to access them easily without knowing their position beforehand. Could a heap help? What about a BST or a trie? Would any other data structures work?


Hint 2
Could you use multiple data structures to make your LRU Cache's functionality fast and efficient? Could you store keys in one data structure, for instance, and values in an auxiliary data structure? What should these data structures be in order for all of the LRU Cache's methods to run in constant time?


Hint 3
Try storing keys in a hash table and mapping them to nodes in a doubly linked list containing the keys' corresponding values (perhaps the nodes would also have to store the keys themselves). With these two data structures, you could access any key / value pair very easily via the hash table, and you could also effortlessly move nodes in the linked list so as to keep track of the most recent and least recent key / value pairs. The linked list would also allow you to keep track of the entire order of the key / value pairs, thus allowing you to perpetually update the least recent key / value pairs after evictions.


Method 1

【O(1)time∣O(1)space】
package LinkedLists;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhengstars
 * @date 2023/06/25
 */
public class LRUCache {
    class ListNode {
        String key;
        int value;
        ListNode prev;
        ListNode next;

        ListNode(String key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }
    }

    private Map<String, ListNode> cache;
    private int maxSize;
    private ListNode head;
    private ListNode tail;

    public LRUCache(int maxSize) {
        this.maxSize = maxSize;
        cache = new HashMap<>();
        head = new ListNode("", 0);
        tail = new ListNode("", 0);
        head.next = tail;
        tail.prev = head;
    }

    public void insertKeyValuePair(String key, int value) {
        if (cache.containsKey(key)) {
            ListNode node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (cache.size() == maxSize) {
                ListNode removedNode = removeTail();
                cache.remove(removedNode.key);
            }
            ListNode newNode = new ListNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
        }
    }

    public int getValueFromKey(String key) {
        if (cache.containsKey(key)) {
            ListNode node = cache.get(key);
            moveToHead(node);
            return node.value;
        }
        return -1; // or throw an exception to indicate key not found
    }

    public String getMostRecentKey() {
        if (head.next != tail) {
            return head.next.key;
        }
        return ""; // or throw an exception to indicate cache is empty
    }

    private void addToHead(ListNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(ListNode node) {
        removeNode(node);
        addToHead(node);
    }

    private ListNode removeTail() {
        ListNode removedNode = tail.prev;
        removeNode(removedNode);
        return removedNode;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);

        cache.insertKeyValuePair("b", 2);
        cache.insertKeyValuePair("a", 1);
        cache.insertKeyValuePair("c", 3);

        cache.getMostRecentKey(); // Output: "c"

        cache.getValueFromKey("a"); // Output: 1

        cache.getMostRecentKey(); // Output: "a"

        cache.insertKeyValuePair("d", 4);

        cache.getValueFromKey("b"); // Output: -1

        cache.insertKeyValuePair("a", 5);

        cache.getValueFromKey("a"); // Output: 5

    }
}




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 2379. Minimum Recolors to Get K Consecutive Black Blocks
  • 2471. Minimum Number of Operations to Sort a Binary Tree by Level
  • 1387. Sort Integers by The Power Value
  • 2090. K Radius Subarray Averages
  • 2545. Sort the Students by Their Kth Score