Graph representation changes the cost
A graph describes vertices and edges. An adjacency list stores actual neighbors and suits sparse graphs; a matrix allocates space for every possible vertex pair. Lists support full traversal in O(V + E), while scanning every matrix row takes O(V²). Directed and undirected storage differ: an undirected list usually stores each edge twice. Add visited state because cycles break tree-only recursion assumptions.
Connectivity without paths
Disjoint-set union stores a parent forest for components. find returns a representative; union merges representatives. Union by size/rank and path compression make long sequences nearly constant amortized time, expressed using the inverse Ackermann function. This structure answers whether two vertices are connected as edges are added. It does not provide the actual route or efficiently handle arbitrary deletions without a different approach.
An LRU cache has two linked invariants
Use a hash map to locate a key node and a doubly linked list to track recency. Every cached key must have exactly one list node; every list node must have a corresponding map entry. A hit moves its node to the front, and eviction removes the tail from both structures. Under concurrency these changes need one consistency boundary. Capacity, null behavior, expiration and failure semantics are part of the contract.
Worked Java example
Illustrative snippet: imports, surrounding types or collaborators may be omitted. Read the assumptions before adapting it.
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.computeIfAbsent(1, key -> new ArrayList<>()).add(2);
graph.computeIfAbsent(2, key -> new ArrayList<>()).add(1);
// Undirected edge {1, 2}: store both directions.Walkthrough
The two map entries represent the same undirected edge from opposite endpoints. A traversal from 1 discovers 2, then must recognize that returning from 2 to 1 does not discover a new vertex. Without visited tracking, a recursive walk can continue indefinitely. Isolated vertices need explicit representation if the algorithm must include them.
Practice it yourself
Design tests for an LRU cache of capacity two, including repeated access, update of an existing key, and eviction.
Check your reasoning
Insert A then B, access A, insert C and verify B is gone. Updating A should not create another list node or grow the entry count. Specify capacity zero behavior and verify that every map entry appears exactly once in the recency list.
Recall checklist
- Explain the main invariant or contract without looking.
- Trace the example and test an edge case.
- State time, space, input variables and assumptions where relevant.
- Explain one alternative and when you would choose it.