Data Structures

Part I — Foundations · Interview reference

Data structure choice is a senior skill: asymptotic complexity plus cache behavior, mutability, concurrency, and operational constraints (memory, latency percentiles, serialization).

Mental model

Ask, in order:

1. Access pattern — sequential, random, keyed, ordered, graph-shaped?
2. Ops mix — read-heavy? append-only? frequent mid-insert? range queries?
3. Constraints — memory, latency SLA, concurrency, persistence, language stdlib?
4. Constants matter — O(1) hash map can lose to sorted array for tiny n or poor locality.

Interview signal: juniors recite Big-O; seniors pick structures and defend why not the others.

Core structures (reference)

Arrays / dynamic arrays (ArrayList, vector)

Use: default sequence; buffers; compact rows.
Pitfalls: geometric growth memory spikes; concurrent modification; confusing size vs capacity.

Java: ArrayList backs on a contiguous Object[] elementData. Default capacity is 10 on first insert. Growth is oldCapacity + (oldCapacity >> 1) (1.5×), then System.arraycopy to the new array. Mid insert/delete shifts elements with arraycopy. Vector is the synchronized legacy twin — prefer external sync or concurrent collections. CopyOnWriteArrayList copies the whole array on every write (read-heavy, rare writes).

Production case study (high volume)

Context: E-commerce checkout cart service (~tens of millions of carts/day, Black Friday peak) materializes line items into ArrayList then serializes to Redis/JSON. Why seniors care: Mid-list insert on large carts is O(n) copy; geometric growth causes allocation spikes and young-gen pressure exactly when QPS peaks; CopyOnWriteArrayList for frequently mutated carts multiplies GC cost. Failure / symptom: p99 latency and GC pause correlation during flash sales; flame graphs show System.arraycopy / grow hot; heap dumps show oversized capacity after bulk imports. Resolution: ensureCapacity for known sizes; prefer append-only builders; size hints from item-count headers; load-test with peak cart sizes, not averages. Seen at / similar to: Shopify/Amazon checkout paths; any JVM service buffering high-cardinality request batches.

Linked lists

Use: rare in application code; useful inside allocators, LRU link wiring, intrusive lists.
Interview angle: “When is linked list better than array?” — usually almost never for general app code; answer with locality and prefetch.

Java: LinkedList is a doubly-linked list of Node { E item; Node next; Node prev } and implements both List and Deque. Each element is a separate heap object → pointer chasing, poor cache locality. Index access walks from the nearer end. Almost never beats ArrayList for list-shaped workloads on the JVM; still fine as a deque when you need cheap mid-list splice given a node reference (rare in app code).

Stack / queue / deque

• Stack: DFS, undo, parsing, recursion elimination
• Queue: BFS, scheduling, buffering
• Deque: sliding window maxima, work stealing queues

Complexity: amortized O(1) end ops for array-backed deque; watch queue implemented as list in languages where that’s O(n) dequeue (classic Python list.pop(0) trap).

Java: Do not use java.util.Stack (extends synchronized Vector). Default stack/deque is ArrayDeque: circular Object[], head/tail indices, capacity power-of-2, doubles on grow; nulls forbidden. Concurrent queues: ArrayBlockingQueue (circular array + single lock), LinkedBlockingQueue (linked nodes, optional capacity, two locks put/take), ConcurrentLinkedQueue (Michael–Scott lock-free CAS), SynchronousQueue (handoff, no internal capacity — used by cached thread pools).

Production case study (high volume)

Context: Ride-hailing matching / logistics dispatch (~millions of location events/min) uses bounded queues between ingest, scoring, and assigner stages. Why seniors care: Unbounded LinkedBlockingQueue hides backpressure until OOM; SynchronousQueue + cached pools can explode threads under spike; queue choice is a capacity and p99 decision. Failure / symptom: Heap climb with “healthy” CPU; or thread count → tens of thousands and context-switch thrash; assigner lag vs SLA. Resolution: Bounded ArrayBlockingQueue + rejection/CallerRuns; metrics on queue depth/age; align capacity with downstream DB/Kafka limits. Seen at / similar to: Uber/Lyft dispatch pipelines; Netflix Zuul/gateway request queues; LMAX-style disruptor ring buffers for ultra-low-latency trading/matching.

Hash tables

Must explain: hashing, collision strategy (chaining vs open addressing), load factor, rehash cost, equals/hashCode contract.

Senior probes

• Hash flooding / DoS → randomized seeds, TreeBins (Java)
• Identity vs value equality
• Mutable keys (corrupt bucket location)
• Memory overhead vs tree map

Java: HashMap uses a power-of-2 Node[] table. Hash mix: h ^ (h >>> 16) then bucket (n - 1) & hash. Default load factor 0.75; resize doubles capacity and re-bins. Collisions chain; a bin of length ≥ 8 treeifies into a red-black TreeBin (only if table capacity ≥ 64, else resize first); untreeifies when short. Allows one null key. HashSet is a HashMap with a shared dummy value. Variants: LinkedHashMap (doubly-linked iteration order; access-order + removeEldestEntry → LRU), IdentityHashMap (== / System.identityHashCode), WeakHashMap (weak keys), EnumMap (array indexed by ordinal). Concurrent: see thread safety — ConcurrentHashMap.

Production case study (high volume)

Context: Social feed / session service holds per-user in-memory maps (tens of millions of entries across a fleet) and a global ConcurrentHashMap for feature flags / experiment assignments. Why seniors care: Resize storms under traffic spikes burn CPU and allocate huge arrays; bad hashCode → TreeBin CPU; CHM single-ops ≠ safe multi-step “ensure entry then update”; memory overhead × replicas is a cost line item. Failure / symptom: Periodic p99 cliffs correlating with map growth; GC old-gen promotion from retained maps; correctness bugs from containsKey+put races on inventory-like counters. Resolution: Size maps at construction; compute/merge APIs; Caffeine/Guava bounded caches with eviction metrics; load-test resize behavior; estimate 10M-entry footprint before “just put it in a HashMap.” Seen at / similar to: Twitter/X early Redis+JVM caches; LinkedIn mid-tier caches; Cloudflare edge maps (language varies) — same hash-table operational story.

Trees (BST, AVL, Red-Black, B-Tree)

Use ordered maps/sets when you need predecessor, range, rank.
DB angle: indexes are B+Trees (or LSM) — link to query optimisation chapter.

Java: TreeMap / TreeSet are red-black trees (Entry with left/right/parent/color); natural order or Comparator; null keys forbidden with natural ordering. NavigableMap APIs give floor/ceiling/subMap. ConcurrentSkipListMap is a skip list, not a tree — lock-free concurrent ordered map. No JDK B-tree or trie; DB indexes and libraries fill that gap.

Heaps / priority queues

• Array-backed binary heap: insert O(log n), get-min O(1), extract O(log n)
• Not for arbitrary delete/decrease-key unless augmented (Indexed heap, Fibonacci — rarely needed in interviews beyond name-drop)

Use: Dijkstra, scheduling, top-K, merge K lists.
Pitfall: “sorted” expectation — heap is partial order only.

Java: PriorityQueue is a binary heap on Object[] (min-heap by default / Comparator); sift-up / sift-down; no efficient arbitrary decrease-key or delete-by-identity. Not thread-safe. PriorityBlockingQueue wraps heap growth with a lock (unbounded). For bounded priority blocking, use PriorityBlockingQueue carefully or a custom design.

Production case study (high volume)

Context: Streaming video / ads auction ranker computes top-K creatives per request at hundreds of K QPS fleet-wide. Why seniors care: Full sort of large candidate sets blows p99; unbounded PriorityBlockingQueue for async scoring hides overload; wrong comparator → silent ranking bugs = revenue. Failure / symptom: CPU-bound handlers; latency proportional to candidate N; OOM on unbounded priority queues during provider outages. Resolution: Heap of size K (or Quickselect); bound queues; histogram candidate counts; compare against Redis sorted-set / search index approaches when N grows. Seen at / similar to: YouTube/Netflix ranking; Google Ads auction-style top-K; Kafka Streams windowed aggregations.

Graphs

Representations:

Know directed vs undirected, weighted, cyclic, connected components.

Java: No first-class graph type in the JDK. Usual stand-in: Map<V, List<E>> or Map<V, List<V>> adjacency lists (HashMap + ArrayList). Matrix as boolean[][] / weight array. Prefer ArrayDeque for BFS; recursion or explicit stack for DFS (watch stack depth).

Specialized (name-drop with one-line why)

Java: BitSet = packed long[] bit vector. EnumSet = bit vector over enum ordinals (very fast). Bloom filters: Guava BloomFilter, not JDK. LRU: LinkedHashMap access-order + removeEldestEntry, or Caffeine in production. Skip list: ConcurrentSkipListMap. Ring buffers: disruptor-style or ArrayBlockingQueue / custom circular arrays.

Production case study (high volume)

Context: Multi-AZ API gateway / edge cache for a SaaS (~100M+ req/day) uses Caffeine LRU locally + Redis for shared hot keys; Bloom filter in front of “user exists?” DB lookups. Why seniors care: Unbounded caches = memory incidents; cache stampede after expiry at top-of-hour; Bloom FPR becomes DB QPS; false sharing / lock strips on naive concurrent LRU. Failure / symptom: Thundering herd to Postgres after deploy flush; Redis hot key on celebrity accounts; elevated DB CPU with “cache hit rate looks fine” (Bloom false positives). Resolution: Soft/hard TTL + singleflight; bound max weight; per-key metrics; size Bloom from growth forecasts; hot-key shielding (local + request coalescing). Seen at / similar to: Netflix EVCache/Hermes-style caching; Discord/Slack presence; Cloudflare edge caches; Redis at Twitter historically for timelines.

Complexity cheat sheet (average)

ADT → Java class (cheat)

Decision criteria

Concurrency & memory (senior layer)

• Structure choice interacts with locking granularity and immutability
• ConcurrentHashMap ≠ “always safe for compound actions” (check-then-act still races)
• Cache line / false sharing matters for striped counters and ring buffers → CPU chapter
• Persistent / functional structures trade write allocation for structural sharing

What interviewers probe

1. Compare ArrayList vs LinkedList with locality and real JVM behavior.
2. HashMap internals — buckets, treeify, resize, null keys (Java specifics if claimed).
3. Design an LRU cache — O(1) get/put structure combo.
4. When hash map loses to sort + scan or to tree.
5. Graph representation choice for a concrete problem (social graph vs road network).
6. Memory overhead estimate for a map of 10M entries.
7. Cache stampede / hot key under millions of RPS — structure + operational fix.

Senior-level expectation: Defend a choice with workload numbers (“p99 latency”, “working set fits L3”, “write amplification”), not only Big-O.

Pitfalls

• Using list where set/map semantics were required (O(n) contains)
• Relying on hash map iteration order
• Storing huge objects in trees by value copies (language-dependent)
• Ignoring load factor and GC pressure from short-lived maps
• Implementing exotic structures when stdlib suffices
• Unbounded queues/caches in high-QPS services (OOM disguised as “slow GC”)
• Choosing LinkedList for hot paths because Big-O insert looked better

Cross-references

• Algorithms
• CPU architecture
• Thread safety
• Database joins & query optimisations