LRU cache (int keys, fixed capacity)

Challenge

Implement an LRU cache with operations lru_get(int key) (returns the cached int or -1 if absent) and lru_put(int key, int value) (inserts or updates; evicts least-recently-used on overflow). Use this header:

typedef struct lru lru_t;
lru_t *lru_create(int capacity);
int    lru_get(lru_t *c, int key);
void   lru_put(lru_t *c, int key, int value);
void   lru_destroy(lru_t *c);

Both operations must be O(1) amortized.

Why this matters

LRU caches power web browsers, database buffer pools, OS page replacement, and CDNs. Implementing one teaches the rare-but-essential 'hash map of doubly-linked-list nodes' pattern.

Input format

capacity > 0. Keys and values are ints. Up to 10000 operations.

Output format

lru_get returns the value, or -1 if key absent.

Constraints

O(1) per operation; O(capacity) memory. No malloc in the hot path inside get/put after creation (you may allocate node slots up front).

Starter code

#include <stdlib.h>
typedef struct lru lru_t;
lru_t *lru_create(int capacity);
int    lru_get(lru_t *c, int key);
void   lru_put(lru_t *c, int key, int value);
void   lru_destroy(lru_t *c);

Common mistakes

Forgetting to move a node to the front on lru_get (not just lru_put); using a singly-linked list (eviction becomes O(n)); leaking nodes on overwrite.

Edge cases to handle

Capacity 1. Repeated put of the same key (update, no evict). Get for missing key.

Complexity

O(1) amortized per operation. O(capacity) memory.

Background lessons

• Hashing — turning keys into table indices