LRU Cache: Hash Table + Doubly Linked List

LRU Cache (LeetCode 146)

Requirements: Both get and put must operate in O(1) time.
Solution: Hash Table + Doubly Linked List.

• Hash Table: key -> Node mapping for O(1) attribute lookup.
• Doubly Linked List: Maintains access order (Head is Most Recently Used, Tail is Least Recently Used) for O(1) node repositioning.

class LRUCache {
    private class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }
    
    private Map<Integer, Node> nodeMap = new HashMap<>();
    private Node head, tail; // Sentinel (dummy) nodes
    private int capacity;

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

    public int get(int key) {
        if (!nodeMap.containsKey(key)) return -1;
        Node node = nodeMap.get(key);
        // Move recently accessed node to the head
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (nodeMap.containsKey(key)) {
            Node node = nodeMap.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            if (nodeMap.size() == capacity) {
                // Evict the least recently used element (tail.prev)
                Node lruNode = tail.prev;
                removeNode(lruNode); 
                nodeMap.remove(lruNode.key);
            }
            Node newNode = new Node(key, value);
            addToHead(newNode); 
            nodeMap.put(key, newNode);
        }
    }

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

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

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

Note: While Java's LinkedHashMap provides a built-in LRU implementation, implementing it manually demonstrates a deeper architectural understanding of pointer manipulation and data structure hybridity.

Insert Delete GetRandom O(1) (LeetCode 380)

Combining a Hash Map and a Dynamic Array:

class RandomizedSet {
    private Map<Integer, Integer> valToIndex = new HashMap<>(); // Value -> Array Index
    private List<Integer> valList = new ArrayList<>();

    public boolean insert(int val) {
        if (valToIndex.containsKey(val)) return false;
        valList.add(val);
        valToIndex.put(val, valList.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!valToIndex.containsKey(val)) return false;
        
        // Logical Removal: Swap target with the end of the array, then pop
        int idx = valToIndex.get(val);
        int lastVal = valList.get(valList.size() - 1);
        
        valList.set(idx, lastVal);
        valToIndex.put(lastVal, idx);
        
        valList.remove(valList.size() - 1);
        valToIndex.remove(val);
        return true;
    }

    public int getRandom() {
        return valList.get(new Random().nextInt(valList.size()));
    }
}

Randomized Collection with Duplicates (LeetCode 381)

Concept: The Hash Map stores a Set of indices for each value. During deletion, pick an arbitrary index from the set and replace it with the array's tail element.

class RandomizedCollection {
    private Map<Integer, Set<Integer>> valToIndices = new HashMap<>();
    private List<Integer> valList = new ArrayList<>();
    
    // insert and remove logic is similar to the above, 
    // but requires managing index sets and updating the map for the moved tail element.
}

Summary