Build It: LRU Cache

Before touching a data structure, pin down the contract. An LRU (Least Recently Used) cache holds at most capacity entries. Every access counts as a use, and when a put would overflow the cache, you evict the entry that was used longest ago. Both operations must run in O(1) — that constraint is the whole problem, and it is the first thing an interviewer wants you to say out loud.

Nail down the observable behavior before the internals:

• get(key) returns the value if present and marks the key as most-recently-used; on a miss it returns some sentinel (here we use null).
• put(key, value) inserts or updates the key, marks it most-recently-used, and evicts the least-recently-used entry if the size now exceeds capacity.
• Updating an existing key is a use: it refreshes recency, it does not grow the size.
• capacity is fixed at construction and must be positive.

Lock the public surface down first so the implementation has a target to hit:

public class LRUCache<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        this.capacity = capacity;
    }

    // Returns the value, or null on a miss. Counts as a use.
    public V get(K key) { /* fill in later */ return null; }

    // Inserts or updates, then evicts the LRU entry if over capacity.
    public void put(K key, V value) { /* fill in later */ }
}

Notice what the API does not promise: no iteration order, no thread-safety yet, no persistence. Interviewers reward a candidate who states the boundaries of the contract before writing a line of logic, because it shows you know which invariants you must protect.