Design LRU Cache

An LRU (Least Recently Used) cache is a data structure that maintains a fixed-size collection of key-value pairs that were recently accessed. When the cache reaches its capacity limit, it automatically evicts the least recently accessed item to make room for new entries.

Data Structure Requirements

Both get and put operations should be O(1) time complexity.

Implement an LRU (Least Recently Used) cache with O(1) time complexity for both get and put operations. The cache should have a fixed capacity and evict the least recently used item when the cache is full. Use a combination of hash map and doubly linked list for optimal performance.

#include <unordered_map>
#include <iostream>

// TODO: Implement an LRU (Least Recently Used) cache with O(1) time complexity
// for both get and put operations
//
// Key Methods to Implement:
// - get(key): Return value if key exists, -1 otherwise. Update access order.
// - put(key, value): Add/update key-value pair. Evict LRU if at capacity.

class LRUCache {
private:
    // TODO: Implement the data structure

public:
    // TODO: Constructor - initialize cache with given capacity
    LRUCache(int capacity) : capacity_(capacity) {
        // TODO: Initialize head and tail dummy nodes
        // TODO: Link head and tail together
    }

    // TODO: Destructor - clean up all allocated memory
    ~LRUCache() {
        // TODO: Delete all nodes in the list
        // TODO: Delete head and tail dummy nodes
    }

    // TODO: Get value for key, return -1 if not found
    // Also move the accessed item to front (most recently used)
    int get(int key) {
        // TODO: Check if key exists in cache
        // TODO: If found, move to front and return value
        // TODO: If not found, return -1
        return -1;
    }

    // TODO: Put key-value pair into cache
    // If key exists, update value and move to front
    // If cache is full, evict least recently used item
    void put(int key, int value) {
        // TODO: Check if key already exists
        // TODO: If exists, update value and move to front
        // TODO: If new key and cache is full, evict LRU item
        // TODO: Add new item to front of list
    }

};