algoadvance

Leetcode 146. LRU Cache

Problem Statement

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

Implement the LRUCache class:

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

Example:

Input:
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

Output:
[null,null,null,1,null,-1,null,-1,3,4]

Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
                    // cache is {2=2, 1=1}
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {3=3, 4=4}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Clarifying Questions

  1. What should the behavior be if we put a key that exists already?
    • It should update the value and move this key to the most recently used position.
  2. What should the behavior be if we get a key that does not exist?
    • It should return -1.
  3. Is the capacity always a positive integer?
    • Yes, the capacity is always a positive integer.

Strategy

To achieve O(1) time complexity for both get and put operations, we can use a combination of:

  1. A HashMap to store key-value pairs for O(1) access.
  2. A doubly linked list to keep track of the order of usage (most recently used to least recently used).

Key Operations:

  1. get(key):
    • Check if the key is in the HashMap.
    • If found, move this node to the front of the doubly linked list and return the value.
    • If not found, return -1.
  2. put(key, value):
    • If the key already exists, update the value and move the node to the front of the list.
    • If the key does not exist:
      • Check if the cache size exceeds the capacity.
      • If it does, remove the node at the back of the doubly linked list and delete its entry from the HashMap.
      • Insert the new key-value pair into the front of the doubly linked list and add it to the HashMap.

Code

import java.util.HashMap;

class LRUCache {
    private class Node {
        int key;
        int value;
        Node prev;
        Node next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        remove(node);
        insertToFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            remove(node);
            insertToFront(node);
        } else {
            if (map.size() == capacity) {
                map.remove(tail.prev.key);
                remove(tail.prev);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            insertToFront(newNode);
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void insertToFront(Node node) {
        Node temp = head.next;
        head.next = node;
        node.prev = head;
        node.next = temp;
        temp.prev = node;
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI