Advanced Data Structures

Data Structure Design

Combine structures to meet per-operation complexity targets (LRU cache, min stack).

Hard, about 120 minutes to practise.

1Understand

The idea

Start from the complexity each operation must have, then combine structures so that each covers what the others cannot. An LRU cache pairs a hash map (find in O(1)) with a doubly linked list (reorder in O(1)); a min stack keeps the running minimum next to each value. Write down the invariant that ties them together.

Intuition

Start from the complexity each operation must meet, then combine structures so each covers what the others cannot. An LRU cache pairs a hash map (O(1) find) with a doubly linked list (O(1) move-to-front). A min stack stores the running minimum beside each value.

Write down the invariant that ties the pieces together, e.g. "map key → node address; list order is recency." Without the invariant, the design drifts.

Interview design problems are less about clever algorithms and more about honest complexity bookkeeping.

What you will be able to do

  • Pick structures from the complexity targets
  • Keep all internal structures in sync

When to use it

  • Design a class with operations in O(1)
  • Cache with eviction
  • Stack or queue with extra queries

2See it

Walkthrough

O(1) set with delete

list + idx map, swap-remove the value.

1 / 6

i
1
2
3
012

idx

  • 1→ 0
  • 2→ 1
  • 3→ 2

Array stores values; map stores indices for O(1) lookup.

idx[val] = len(arr); arr.append(val)

Live template

Line 1 active

1class LRU:
2 def __init__(self, cap): self.cap = cap; self.data = OrderedDict()
3 def get(self, k):
4 if k not in self.data: return -1
5 self.data.move_to_end(k); return self.data[k]

Complexity: time O(1) per op (target), space O(n)

Target O(1) or O(log n) per operation as stated. Using list.remove (O(n)) behind a dict quietly breaks LRU. Tree maps give O(log n) ordered ops when O(1) is impossible.

Read the walkthrough as text

LRU cache. Capacity 2; operations put(1,1), put(2,2), get(1), put(3,3), get(2).

  1. After two puts: list order 1,2 (2 most recent), map holds both.
  2. get(1) moves 1 to front → order 2,1.
  3. put(3,3) evicts least recent 2; map deletes 2; list 1,3.
  4. get(2) misses → -1.

Hash map alone cannot reorder in O(1); a list alone cannot find in O(1). Together they can.

3Recognise it

Kinds of problems (11)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Min stack

    Example. Stack with getMin in O(1).

    How. Secondary stack tracks running minimum on each push.

  • Queue from two stacks

    Example. FIFO using two stacks.

    How. Pour in-stack to out-stack when out empty on pop.

  • LRU cache

    Example. Capacity-limited cache evicts least recently used.

    How. OrderedDict or hash + doubly linked list: move to end on access.

  • Insert / delete / get-random in O(1)

    Example. RandomizedSet with uniform random.

    How. List plus index map; swap delete with last for O(1) remove.

  • Time-based key-value store

    Example. Get key at timestamp.

    How. Map key → sorted list of (timestamp, value); binary search floor timestamp.

  • Iterator design

    Example. Peeking iterator or flatten nested list iterator.

    How. Stack of pending elements; advance to next valid on hasNext.

  • Hash map from scratch (buckets and resizing)

    Example. Design hash map with chaining.

    How. Buckets of (key, value); resize when load factor exceeds threshold.

  • Frequency buckets (LFU cache, max-frequency stack)

    Example. LFU cache eviction.

    How. Map key→node; buckets by freq; evict from min freq bucket LRU.

  • Circular buffer (circular queue)

    Example. Fixed-size queue with head/tail modulo capacity.

    How. Array with front/rear indices; full when (rear+1)%cap == front.

  • History navigation (browser history, undo)

    Example. Visit, back, forward stack design.

    How. Stack back; move current to forward stack on visit; clear forward on new visit.

  • Several maps working together (check-in systems, feeds)

    Example. All-one data structure or tweet counts per user.

    How. Split roles: global count map + per-key freq map stay in sync on changes.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Structures out of sync

    Why it happens. One structure is the source of truth.

    How it fails. LRU: delete key from dict but node stays in linked list, ghost entries.

    Fix. Every mutating op updates all paired structures in one transaction.

  • Linear-time operation

    Why it happens. n is small in examples so scanning is fine.

    How it fails. getRandom scans list O(n), violates O(1) spec at scale.

    Fix. Meet each op target: hash+list swap-delete, OrderedDict move_to_end, etc.

  • Capacity edge case

    Why it happens. Evict then insert is the same as insert then evict at capacity.

    How it fails. LRU at cap: put existing key evicts LRU before updating, wrong key removed.

    Fix. Update existing key without eviction; evict only on new key when full.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons