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

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