LRU cache (int keys, fixed capacity)

Challenge

Build a least-recently-used (LRU) cache with int keys and a fixed capacity.

Task

Implement the following API. lru_get returns the cached value or -1 if the key is absent; lru_put inserts or updates a key, evicting the least-recently-used entry when the cache is over capacity. Both get (on a hit) and put count as "using" a key.

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);

Input

• capacity: maximum number of entries (capacity > 0).
• Keys and values are ints. Up to 10000 operations.

Output

• lru_get returns the stored value, or -1 if the key is not present.
• lru_put returns nothing; it may evict the least-recently-used key.

Example

lru_create(2)
lru_put(1,10); lru_put(2,20)
lru_get(1)        ->   10        (1 is now most-recently used)
lru_put(3,30)                    (evicts key 2, the least-recently used)
lru_get(2)        ->   -1        (evicted)
lru_put(1,100)                   (update existing key)
lru_get(1)        ->   100

Edge cases

• Capacity 1.
• Repeated put of an existing key updates the value without evicting.
• get of a missing key returns -1.

Rules

• O(1) amortized per operation; O(capacity) memory. Avoid allocating in the get/put hot path after creation (allocate node slots up front if needed).

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; int keys and values; up to 10000 operations.

Output format

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

Constraints

c points to initialized lru_cache_t. Keys and values are 32-bit integers.

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

Failing to update doubly-linked pointers on node detachment leading to corrupted list.

Edge cases to handle

Lookup on empty cache, inserting duplicate keys, eviction when reaching capacity.

Complexity

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

Background lessons

• Hashing — turning keys into table indices