Linked List - One trick problems

1. LRU - Least Recently Used

All the 3 solutions of this problem should be discussed especially the hashmap solution.

https://neetcode.io/problems/lru-cache
The Map object maintains insertion order, which allows us to implement LRU eviction in O(1) time complexity for both get and put operations.

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) return -1; // Key not found

        // Move the accessed key to the end (most recently used)
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);

        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // Remove the old entry to update it
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // Remove the least recently used (LRU) item (first key in the Map)
            const lruKey = this.cache.keys().next().value;
            this.cache.delete(lruKey);
        }

        // Insert the new key-value pair at the end
        this.cache.set(key, value);
    }
}

// Example usage:
const lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
console.log(lru.get(1)); // Returns 1
lru.put(3, 3); // Evicts key 2
console.log(lru.get(2)); // Returns -1 (not found)
lru.put(4, 4); // Evicts key 1
console.log(lru.get(1)); // Returns -1 (not found)
console.log(lru.get(3)); // Returns 3
console.log(lru.get(4)); // Returns 4