Design Data Structures

Clarify the API, fix each method's cost, write the invariant — then snap HashMaps, arrays, stacks, TreeMaps and tries together so every call hits its target.

advanced~80 min4 simulations5 problems

▶ guided lesson ⚡ 1-minute summary ↻ 13 recall cards

before this: Java OOP · Hashing · Linked Lists · Stacks · Binary Search · BST · Tries

Section

01 · why it exists

Why this exists, and the weight it carries

since1974

Design from the API (abstract data types)

Barbara Liskov (MIT) & Stephen Zilles (IBM)

In 1974 Barbara Liskov and Stephen Zilles published "Programming with Abstract Data Types" at an ACM SIGPLAN symposium. Their idea: describe a data type by the operations its users may call, and keep its representation hidden inside. Liskov's 2008 Turing Award citation honours her contributions to programming language and system design, "especially related to data abstraction, fault tolerance, and distributed computing". Every Java interface you use — List, Map, Deque — is this idea: one API, several representations behind it, each with its own costs.

the problem it solvedCode that reaches into a structure's fields everywhere can't change the structure without breaking. Fixing the operations first lets the inside change freely.

its jobs today

Java's Collections Framework: Map is the API; HashMap and TreeMap are two representations with different costs per method.
Every "Design X" interview question: the class and its methods are fixed, and you choose what's inside so each method meets its cost.
Service APIs: callers depend only on the methods, so the storage behind them can change — a list today, an index tomorrow.

the weight it carries

Illustrative: LeetCode allows 2·10⁵ calls on a RandomizedSet — say 10⁵ inserts, then 10⁵ removes. If each remove scans and shifts a list of up to 10⁵ values, that is up to 10⁵ × 10⁵ = 10¹⁰ steps — far too slow. With every method O(1) on average it is 2·10⁵ calls × a few operations ≈ 10⁶ steps.

without it

Without fixing the API and the per-method costs first, you polish one method and discover at the end that another one is O(n) — the most common way design rounds go wrong.

when · why · how

when: Any question that says "design" or "implement the class" with several methods.
why: The slowest method decides the total: n calls × the worst per-call cost. Choosing a structure per method keeps every call inside its budget.
how: Write the class skeleton with each method's target cost as a comment, then the fields, then the invariant — and only then the method bodies.

since1964 / 1993

Array + index map (swap-with-last delete)

Richard Durstenfeld; Preston Briggs & Linda Torczon (Rice University)

The move is old. Durstenfeld's 1964 random-permutation algorithm (CACM Algorithm 235) swaps a randomly chosen element with the last one of the not-yet-shuffled range, then shrinks the range — nothing shifts. In 1993 Briggs and Torczon published a set built from a dense array of members plus a second array giving each member's slot. Add, delete and clear take constant time, and iterating costs only the number of members — far cheaper than a bit vector over the whole range. GCC still ships an implementation; its comment says it replaces the deleted element with the last element of the dense array.

the problem it solvedCompilers needed many small sets drawn from a large range of numbers, with constant-time add, delete and clear, and iteration over the members only.

its jobs today

Compilers: GCC's sparse sets give O(1) add, delete and clear for sets of small integer ids; Briggs and Torczon developed the design for register allocation.
Picking a random item from a pool that keeps changing — a random online player for a match, a random healthy server — in O(1) per pick and per change (illustrative).
Game loops: removing a destroyed object from the array of live objects by moving the last one into its slot, so the array never has holes (illustrative).

the weight it carries

Illustrative: 10 lakh (1,000,000) online players in an ArrayList. Removing one from the front with remove(0) shifts 999,999 references; swap-with-last moves 1 element and makes 2 map updates (fix the moved value's index, delete the removed value). A random pick from a HashSet walks about 5 lakh entries on average; from the array it is 1 index.

without it

getRandom would cost O(n) (walk a set) or remove would cost O(n) (shift a list) — at LC 380's 2·10⁵ calls (say 10⁵ inserts, then 10⁵ picks or removes), up to 10⁵ × 10⁵ = 10¹⁰ steps.

when · why · how

when: You need O(1) insert, delete and random access (or index-based iteration), and the order of the elements doesn't matter.
why: The array gives O(1) access by index; the map gives O(1) "where is x?". Filling the hole with the last element means nothing ever shifts — the price is that the order changes.
how: List<Integer> values + Map<Integer, Integer> indexOf. Remove: i = indexOf.get(v); last = values.get(size − 1); values.set(i, last); indexOf.put(last, i); values.remove(size − 1); indexOf.remove(v);

since2010

Group by count (a bucket per frequency)

Ketan Shah, Anirban Mitra & Dhruv Matani

An LFU (least frequently used) cache evicts the key with the fewest uses. The paper notes that the best-known implementations, a min-heap plus a hash table, cost O(log n) per operation. Shah, Mitra and Matani's paper, dated August 2010 and posted to arXiv in 2021, gave an O(1) LFU: one bucket of keys per use count, the buckets linked in count order, and a hash table that finds each key's entry. Each use moves a key to the bucket for the next count — a count changes by exactly one, so the right bucket is always next door. Maximum Frequency Stack uses the same trick, with a stack per count so that ties go to the newest value.

the problem it solvedMaking "most (or least) frequently used" as cheap as "least recently used": O(1) per access instead of O(log n).

its jobs today

LFU caches: evict the key with the fewest uses in O(1), with keys kept in one bucket per use count.
"Most played right now" lists that must answer after every event, without re-sorting (illustrative).
Schedulers that serve the most-repeated kind of task first, newest first among ties — the frequency stack's pop (illustrative).

the weight it carries

Illustrative, at LC 895's limit of 2·10⁴ calls (say 10⁴ pushes, then 10⁴ pops): scanning up to 10⁴ values on every pop costs up to 10⁴ × 10⁴ = 10⁸ steps; a heap costs about 2·10⁴ × log₂(2·10⁴) ≈ 2·10⁴ × 14.3 ≈ 3·10⁵; one stack per count costs a few map operations per call — about 10⁵ in total.

without it

"Most frequent so far" would need a scan or a heap on every query: O(n) or O(log n) instead of O(1).

when · why · how

when: Counts change by ±1 per event, and you keep taking the most (or least) frequent item.
why: Because a count moves by exactly one, only the neighbouring group can become the new extreme — so one integer (maxFreq) tracks it, with no search.
how: Map<Integer, Integer> freq + Map<Integer, Deque<Integer>> group (computeIfAbsent(f, k -> new ArrayDeque<>()).push(v)) + int maxFreq.

since1978–1983

Versioned values (floor lookup by time)

David P. Reed (MIT); Philip Bernstein & Nathan Goodman

In his MIT doctoral thesis, issued in 1978 as report TR-205, David Reed treated a changing object as a sequence of immutable versions, each named by the object and a pseudo-time. A reader asks for the version that was current at its time, so old versions stay readable while new ones are written. In 1983 Bernstein and Goodman gave multiversion concurrency control (MVCC) a formal theory in ACM Transactions on Database Systems. Today PostgreSQL's manual describes MVCC as each SQL statement seeing a snapshot of the data as it was some time ago.

the problem it solvedLetting readers see a consistent past state while writers keep changing the data, without readers and writers blocking each other.

its jobs today

Databases: PostgreSQL's MVCC keeps row versions so a statement reads one snapshot while others write.
Config and feature-flag history: "what was this setting at 10:05, when the bug started?" (illustrative).
Price history in a shopping app: the price that was live when an order was placed (illustrative).

the weight it carries

Illustrative: a config key changed 10 lakh (10⁶) times. "Value at time t" by scanning back can touch all 10⁶ versions; a binary search touches ⌈log₂(10⁶)⌉ = 20.

without it

You would keep only the latest value and lose the history, or scan every version on each read.

when · why · how

when: Values change over time and you must answer "what was it at time t?" — snapshots, audit logs, LC 981, LC 1146.
why: History sorted by time turns "latest version ≤ t" into a floor search: O(log v). If writes come in time order, appending keeps it sorted at O(1) amortized.
how: Increasing times: two ArrayLists per key + a binary search for the last time ≤ t. Any order: TreeMap<Integer, String>.floorEntry(t).

since1965–1974

Tree of names (paths as a trie)

Robert Daley & Peter Neumann (Multics); Dennis Ritchie & Ken Thompson (Unix)

In 1965 Daley and Neumann described the Multics file system as a tree hierarchy of files, where a file's path name is the chain of entry names from the root. Unix made this the everyday model. Ritchie and Thompson's 1974 CACM paper says directories map the names of files to the files themselves, in the form of a rooted tree. A path name is a sequence of directory names separated by slashes, and a directory entry holds just a name and a pointer — an integer called the i-number. LC 588 builds the same walk in memory: split on '/', then one lookup per level.

the problem it solvedOrganising thousands of files so that any one is found by name through a short chain of small directories, instead of one huge flat list.

its jobs today

File systems: opening /home/priya/notes walks one directory per name.
Coordination stores: ZooKeeper names its nodes with slash-separated paths; its namespace is "much like that of a standard file system".
Web routers that match URLs like /api/users/42 one segment at a time (illustrative).

the weight it carries

Illustrative: 10 lakh (10⁶) files. Listing one folder with a flat map of full paths compares the prefix against all 10⁶ paths. With a tree of names it is one lookup per level (say 6 levels) plus the folder's own entries (say 50) — about 56 steps, not a million.

without it

Every ls or lookup would scan all stored paths, and every path would repeat its parents' names in full.

when · why · how

when: Names form a hierarchy: file paths, URLs, nested categories, config keys like a.b.c.
why: Each level narrows the search to one folder's children, so the cost depends on the path's depth and the folder's size — not on the total number of files.
how: class Node { TreeMap<String, Node> children = new TreeMap<>(); StringBuilder content; }, and walk with for (String name : path.split("/")) if (!name.isEmpty()) node = node.children.computeIfAbsent(name, k -> new Node());

since?

Counting map (store counts, not copies)

Counting identical items in a table is as old as tallying, and the HashMap-of-counts idiom has no single inventor, so we name none.

its jobs today

Analytics: count events per (user, page) or per map tile instead of storing every event.
Geometry on a grid: count points per cell, then answer "how many squares or pairs" by multiplying counts (LC 2013).
Multisets in Java: there is no built-in one, so HashMap<K, Integer> with merge(k, 1, Integer::sum) is the standard stand-in.

the weight it carries

Illustrative, at LC 2013's limit of 3,000 calls: with 2,000 points stored, scanning pairs costs up to 2,000² = 4·10⁶ steps per count. Counting copies and looping over the query's column costs at most 1,001 × 2 square checks — about 2,000.

without it

Duplicates would be stored and scanned one by one, and "how many ways" questions would need nested loops over every copy.

when · why · how

when: Identical items repeat and you only need how many of each — even when "copies count separately" in the answer.
why: k copies contribute a factor of k, so one count replaces k entries, and queries loop over distinct items only.
how: Map<Integer, Map<Integer, Integer>> byX with byX.computeIfAbsent(x, k -> new HashMap<>()).merge(y, 1, Integer::sum).

02 · plain english

The idea in 30 seconds

A design question hands you an API (a class and its methods) and a cost for each method. Your job: choose the fields so that every method meets its cost.

You rarely invent anything. You compose pieces you already know: a HashMap to find, an array to pick by index, a stack for newest first, a TreeMap for nearest ≤ x, a trie for paths.

The glue is an invariant: one sentence about the fields that is true after every call. A method may break it for a moment, but restores it before it returns.

picture this

A database table with indexes. The table holds the rows, and you add one index for each query that must be fast; every insert or delete updates the table and all its indexes together. A design answer is the same: one store, one helper structure per fast method, all kept in sync.

03 · remember

What you must know

The routine: state the API → write each method's target cost → pick one structure per method's question → write the invariant over the fields → code method by method → dry-run a script of calls.
One question, one structure: find by key → HashMap · pick by position or at random → ArrayList · newest first → stack · oldest first → queue · smallest or largest → heap · nearest ≤ x, sorted order → TreeMap or a sorted list + binary search · by path or prefix → trie.
Swap with the last: an array can drop any slot in O(1) when order doesn't matter. Copy the last element into the hole, update its index in the map, remove the end.
Group by a changing count: keep value → count plus count → stack of values. A count moves by exactly 1 per call, so the top group is tracked with one integer, never searched.
Append-only history is sorted for free: when timestamps only grow, appending keeps each key's list sorted, and "value at time t" is a binary search for the floor.
Paths are tries of names: split /a/b/c on / and walk a tree of nodes, each mapping a name to a child. TreeMap children hand ls its names already sorted.
Count, don't copy: store item → how many copies and loop over a small candidate set (one column of points) instead of every stored item.
Say each method's cost precisely: HashMap is O(1) average, ArrayList.add is O(1) amortized, TreeMap is O(log n) worst case.
LRU Cache, Min Stack, Design Twitter, Implement Trie, Design Circular Queue and Design HashSet live in their own chapters. Practise them here as design rounds (see Also practise this here).

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Insert Delete GetRandom O(1): swap with the last

Top: the ArrayList. Bottom: the HashMap from value to index. A remove copies the last value into the hole, fixes its index and drops the end — nothing shifts.

loading simulation…

javajava.util.* · java.util.function.*

1class RandomizedSet {2    private final List<Integer> values = new ArrayList<>();        // the elements, in any order3    private final Map<Integer, Integer> indexOf = new HashMap<>(); // value → its index in values4    private final Random random = new Random();5    // invariant: values.get(indexOf.get(v)) == v for every v in the set6 7    public boolean insert(int val) {8        if (indexOf.containsKey(val)) return false;9        indexOf.put(val, values.size()); // it will sit at the end10        values.add(val);11        return true;12    }13 14    public boolean remove(int val) {15        Integer i = indexOf.get(val);16        if (i == null) return false;17        int last = values.get(values.size() - 1);18        values.set(i, last);              // the last element fills the hole19        indexOf.put(last, i);             // and the map learns its new index20        values.remove(values.size() - 1); // removing the end shifts nothing21        indexOf.remove(val);              // last, so it also works when val was the last element22        return true;23    }24 25    public int getRandom() {26        return values.get(random.nextInt(values.size())); // every index equally likely27    }28}

sim

Maximum Frequency Stack: one stack per count

A value pushed f times sits once in each of groups 1…f. pop takes the top of the highest group: the most frequent value, and among ties the newest.

loading simulation…

javajava.util.* · java.util.function.*

1class FreqStack {2    private final Map<Integer, Integer> freq = new HashMap<>();          // value → copies in the stack3    private final Map<Integer, Deque<Integer>> group = new HashMap<>(); // count f → values that reached f, newest on top4    private int maxFreq = 0;5    // invariant: a value with count f sits once in each of group 1, 2, …, f6 7    public void push(int val) {8        int f = freq.merge(val, 1, Integer::sum);9        maxFreq = Math.max(maxFreq, f);10        group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(val);11    }12 13    public int pop() {14        Deque<Integer> top = group.get(maxFreq); // the most frequent values15        int val = top.pop(); // the newest of them wins the tie16        freq.merge(val, -1, Integer::sum);17        if (top.isEmpty()) maxFreq--; // group maxFreq − 1 still holds val, so it is never empty18        return val;19    }20}

sim

Time Based Key-Value Store: binary search for the floor

Each key's times grow, so its list is sorted for free. get(key, t) narrows lo..hi to the last time ≤ t.

loading simulation…

javajava.util.*

1class TimeMap {2    private static class History {3        final List<Integer> times = new ArrayList<>(); // increasing, because set() timestamps only grow4        final List<String> values = new ArrayList<>(); // values.get(i) was set at times.get(i)5    }6 7    private final Map<String, History> store = new HashMap<>();8 9    public void set(String key, String value, int timestamp) {10        History h = store.computeIfAbsent(key, k -> new History());11        h.times.add(timestamp); // appending keeps the list sorted12        h.values.add(value);13    }14 15    public String get(String key, int timestamp) {16        History h = store.get(key);17        if (h == null) return "";18        int lo = 0, hi = h.times.size() - 1, found = -1;19        while (lo <= hi) {20            int mid = (lo + hi) >>> 1;21            if (h.times.get(mid) <= timestamp) {22                found = mid; // a candidate; a later one may fit too23                lo = mid + 1;24            } else {25                hi = mid - 1; // too new26            }27        }28        return found == -1 ? "" : h.values.get(found);29    }30}

sim

In-memory file system: walk a tree of names

Folders are boxes, files are spheres. Every call splits its path on "/" and takes one TreeMap step per name; missing folders are created on the way.

loading simulation…

javajava.util.*

1class FileSystem {2    private static class Node {3        final TreeMap<String, Node> children = new TreeMap<>(); // name → child, kept sorted for ls4        StringBuilder content;                                  // null for a folder, text for a file5    }6 7    private final Node root = new Node();8 9    /** Walks from the root, one name at a time, creating missing folders on the way. */10    private Node walk(String path) {11        Node node = root;12        for (String name : path.split("/")) { // "/a/b" → ["", "a", "b"]; "/" → []13            if (name.isEmpty()) continue;14            node = node.children.computeIfAbsent(name, k -> new Node());15        }16        return node;17    }18 19    public List<String> ls(String path) {20        Node node = walk(path);21        if (node.content != null) { // a file lists only its own name22            return List.of(path.substring(path.lastIndexOf('/') + 1));23        }24        return new ArrayList<>(node.children.keySet()); // TreeMap keys are already sorted25    }26 27    public void mkdir(String path) {28        walk(path); // creates every missing folder on the path29    }30 31    public void addContentToFile(String filePath, String content) {32        Node file = walk(filePath);33        if (file.content == null) file.content = new StringBuilder(); // a new file34        file.content.append(content); // append, never overwrite35    }36 37    public String readContentFromFile(String filePath) {38        return walk(filePath).content.toString();39    }40}

05 · cost

Time & space, explained

Which piece answers which question fast (n stored items)
	find by key	add / remove	pick at random	nearest ≤ x	why
HashMap / HashSet	O(1) avg	O(1) avg	O(n)	O(n)	Hashing jumps straight to one bucket, but a hash table keeps no order and no index — random picks and floor lookups must walk it.
ArrayList (any order)	O(n)	add O(1) amortized · remove O(n), or O(1) by swapping with the last	O(1)	O(n)	Index access is one address calculation; finding a value is a scan. remove(i) shifts the tail unless you fill the hole with the last element.
Sorted ArrayList + binary search	O(log n)	O(n) to keep it sorted · O(1) amortized if keys only grow	O(1)	O(log n)	Binary search halves the range each step; inserting in the middle shifts the tail — unless every new key is the largest, as with timestamps.
TreeMap	O(log n)	O(log n)	O(n)	O(log n)	A red-black tree stays balanced, so every lookup, insert and floor/ceiling query walks one root-to-leaf path.
ArrayDeque as a stack	O(n)	O(1) at the top	—	O(n)	Only the top is reachable in O(1); anything else is a walk.

This chapter's designs: the slow method vs the designed one
	First idea	Designed	why
RandomizedSet.remove	O(n) — find, then shift (ArrayList only)	O(1) average	The map gives the index; the last element fills the hole, so nothing shifts.
RandomizedSet.getRandom	O(n) — walk a HashSet	O(1)	`values.get(random.nextInt(size))` is one index access.
FreqStack.pop	O(n) scan · O(log n) heap	O(1) average	The answer is always the top of group maxFreq, and maxFreq moves by one.
TimeMap.get (v versions of the key)	O(v) — scan back	O(log v)	The history is sorted by time, so the floor is a binary search.
FileSystem.ls (P stored paths, d names in the path, k listed)	O(P · L) — scan every path string	O(d · log c + k)	The tree walks d levels, each one TreeMap lookup among c siblings, then copies k sorted names.
DetectSquares.count (n points added)	O(n²) — scan pairs	O(c), c ≤ 1,001	Only points in the query's column can be a corner, and y ≤ 1000 limits that column to 1,001 different values.

06 · java

Raw vs Collections Framework

Delete from the middle in O(1): fill the hole with the last element

javaint[] + size: copy the last live element into the holejava.util.*

1/** Removes data[i] from the live part data[0..size-1] in O(1). Order is not kept. Returns the new size. */2static int removeAt(int[] data, int size, int i) {3    data[i] = data[size - 1]; // the last live element fills the hole4    return size - 1;          // and the old last slot is simply outside the live part now5}

javaArrayList + HashMap<String, Integer> (value → index)java.util.*

1/** O(1) removal from an ArrayList whose order doesn't matter, keeping the value → index map in sync. */2static boolean removeValue(List<String> items, Map<String, Integer> indexOf, String value) {3    Integer i = indexOf.get(value);4    if (i == null) return false;5    String last = items.get(items.size() - 1);6    items.set(i, last);              // the last element fills the hole7    indexOf.put(last, i);            // ...and the map learns where it went8    items.remove(items.size() - 1);  // removing the end shifts nothing9    indexOf.remove(value);           // done last, so value == last also works10    return true;11}

list.remove(i) shifts every element after i: O(n). list.remove(list.size() - 1) shifts nothing: O(1).
The price is the order: the last element jumps into the middle. Use it for sets and pools, not for playlists or queues.
The moved element's index changed, so update the map. Remove the deleted value from the map last — then deleting the last element works too.

Value at time t: the floor of t in a sorted history

javabinary search: last index with times[i] ≤ tjava.util.*

1/** Index of the last time ≤ t in a sorted array, or -1 if every time is later. O(log n). */2static int floorIndex(int[] times, int t) {3    int lo = 0, hi = times.length - 1, found = -1;4    while (lo <= hi) {5        int mid = (lo + hi) >>> 1;6        if (times[mid] <= t) {7            found = mid;  // fits; look right for a later one8            lo = mid + 1;9        } else {10            hi = mid - 1; // too late; look left11        }12    }13    return found;14}

javaTreeMap<Integer, String>.floorEntry(t)java.util.*

1/** The value that was current at time t, or "" if nothing was set yet. O(log n). */2static String valueAt(TreeMap<Integer, String> history, int t) {3    Map.Entry<Integer, String> e = history.floorEntry(t); // largest key ≤ t, or null4    return e == null ? "" : e.getValue();5}

Keep a found variable: record mid when it fits, then keep going right. You never have to reason about where lo stops.
floorEntry(t) returns the entry with the largest key ≤ t, or null. floorKey(t) returns just the key.
Prefer the list when writes arrive in time order (append is O(1) amortized and memory is compact); use TreeMap when they don't.
(lo + hi) >>> 1 never overflows; (lo + hi) / 2 can for indices near 2³¹.

Group values by a count that changes

javaList<Deque<Integer>> indexed by the countjava.util.*

1/** levels.get(f) = values that reached count f, newest last. Counts are 1, 2, 3…, so a list index works. */2static void addToLevel(List<Deque<Integer>> levels, int f, int value) {3    while (levels.size() <= f) levels.add(new ArrayDeque<>()); // grow up to level f4    levels.get(f).push(value);5}

javaMap<Integer, Deque<Integer>> + computeIfAbsentjava.util.*

1/** group.get(f) = values that reached count f, newest on top. computeIfAbsent creates a missing stack. */2static void addToGroup(Map<Integer, Deque<Integer>> group, int f, int value) {3    group.computeIfAbsent(f, k -> new ArrayDeque<>()).push(value);4}

Counts are 1, 2, 3… with no gaps, so a list indexed by the count works as well as a map.
computeIfAbsent(f, k -> new ArrayDeque<>()) returns the existing stack or creates it — no null checks.
Use ArrayDeque for the stacks: push, pop and peek work at the front in O(1). The legacy Stack class is synchronized and slower.

Splitting a path into names

javaby hand: scan for '/'java.util.*

1/** "/home/priya/code" → [home, priya, code], reading the characters by hand. */2static List<String> namesByHand(String path) {3    List<String> names = new ArrayList<>();4    int start = 1; // skip the leading '/'5    for (int i = 1; i <= path.length(); i++) {6        if (i == path.length() || path.charAt(i) == '/') {7            if (i > start) names.add(path.substring(start, i));8            start = i + 1;9        }10    }11    return names;12}

javapath.split("/") and skip empty partsjava.util.*

1/** Same result with split: "/a/b".split("/") is ["", "a", "b"] and "/".split("/") is [], so skip empty parts. */2static List<String> namesBySplit(String path) {3    List<String> names = new ArrayList<>();4    for (String name : path.split("/")) {5        if (!name.isEmpty()) names.add(name);6    }7    return names;8}

"/a/b".split("/") is ["", "a", "b"] and "/".split("/") is an empty array. Always skip empty names.
split takes a regular expression. "/" is safe, but a dot is special: split on "\\.", not ".".
Scanning by hand avoids building an array; in an interview, split is clearer.

Java API you will actually use
call	does	cost
`map.get(k) / map.containsKey(k)`	Find a key's value (null if absent) / test presence	O(1) average
`map.merge(k, 1, Integer::sum)`	Add 1 to k's count (creating it at 1) and return the new count	O(1) average
`map.computeIfAbsent(k, x -> new ArrayList<>())`	Return k's collection, creating it on first use	O(1) average
`list.set(i, x) / list.get(i)`	Overwrite / read slot i	O(1)
`list.remove(list.size() - 1)`	Remove the last slot; nothing shifts	O(1)
`list.remove(i) / list.remove(Integer.valueOf(x))`	Remove by index / by value; shifts everything after it	O(n)
`random.nextInt(n)`	A uniformly random int in [0, n)	O(1)
`treeMap.floorEntry(t) / floorKey(t)`	Entry / key with the largest key ≤ t, or null	O(log n)
`treeMap.keySet()`	The keys in sorted order (a view; copy it before returning)	O(k) to iterate k keys
`Collections.binarySearch(list, key)`	Index of key, or −(insertion point) − 1 if absent; needs a sorted RandomAccess list	O(log n)
`deque.push(x) / deque.pop() / deque.peek()`	Stack operations on an ArrayDeque (front = top)	O(1)
`path.split("/")`	The parts between slashes; a leading "/" gives an empty first part	O(length)
`sb.append(s)`	Grow a StringBuilder (a file's content) without copying it every time	O(\|s\|) amortized

Insert, delete and pick at random, all O(1)

→ ArrayList + HashMap value → index (swap-with-last delete)

The list gives random access by index; the map finds the slot to delete without a scan.

Pop the most frequent value, ties to the newest

→ HashMap value → count + HashMap count → ArrayDeque + int maxFreq

Counts move by ±1, so the top group is always maxFreq; no heap needed.

Value at time t, writes in time order

→ HashMap key → two ArrayLists (times, values) + binary search

Appending keeps the list sorted: set O(1) amortized, get O(log v), compact memory.

Value at time t, writes in any order (or deletes)

→ HashMap key → TreeMap<Integer, String> with floorEntry

The tree keeps order on every insert in O(log v).

Paths, folders, nested names

→ Trie node with TreeMap<String, Node> children

One lookup per level; TreeMap returns ls already sorted. (HashMap + sort if ls is rare.)

Many identical items, count-based answers

→ HashMap<K, Integer> with merge (a multiset)

k copies become one entry and a factor of k; loops run over distinct items only.

O(1) get and put with least-recently-used eviction

→ HashMap + doubly linked list (or LinkedHashMap in access order)

The map finds the node; the list reorders and evicts in O(1). See LRU Cache.

A stack that reports its minimum in O(1)

→ ArrayDeque of {value, min so far}

Each entry remembers the minimum below it, so pop needs no recomputation. See Min Stack.

07 · recognise

Spot the pattern

"insert, delete and getRandom, all in O(1)"

HashMap value → index + ArrayList; delete by swapping with the last element

"pop the most frequent; on a tie, the most recent"

count map + map from count to a stack, plus maxFreq

"value at timestamp t", "latest version ≤ t", "snapshot"

Per-key history sorted by time + floor search (binary search or TreeMap.floorEntry)

"mkdir", "ls", paths like /a/b/c, nested names

Trie of names: each node maps a name to a child; TreeMap children for sorted output

"count the squares/rectangles formed with stored points", "duplicates count separately"

Count identical points; loop over the few points that can be a partner (same column or row)

"O(1) get and put with eviction of the least recently used"

HashMap + doubly linked list (LRU Cache, linked-lists chapter)

"Design X" / "implement the class" with several methods and per-call targets

The routine: API → cost per method → one structure per question → invariant → script test

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Swap-with-last: forgetting indexOf.put(last, i) — the moved element keeps a stale index, and a later remove deletes the wrong slot.
Swap-with-last: calling indexOf.remove(val) before indexOf.put(last, i). When val is the last element, the put brings it back.
list.remove(val) on a List<Integer> with an int removes by index. Use the index from your map, or list.remove(Integer.valueOf(val)) when you really mean a value.
Comparing two Integers from a map with ==: equal values above 127 are usually different objects, so == says false. Unbox first (int x = map.get(k)) or use .equals.
Frequency stack: forgetting to decrease the popped value's count, or scanning for a new maximum when maxFreq - 1 is always right.
Time map: searching for the first time ≥ t (ceiling) instead of the last time ≤ t (floor), or returning null instead of "".
File system: not skipping the empty strings from split("/"), and overwriting a file's content instead of appending.
Returning an internal list or keySet() from a method lets the caller change your state. Return a copy: new ArrayList<>(…).

tricks

Open by writing the API: class name, each method's signature and its target cost. Then ask: value ranges? duplicates? how many calls? do timestamps only grow? thread safety?
Write the invariant as a comment above your fields before any method body, and check every method against it.
Name the brute force first ("one list makes remove O(n)"), then say which piece fixes which method. That shows the interviewer your reasoning, not just the answer.
After coding, dry-run a short script that hits the edges: an empty structure, removing the last element, duplicates, a tie.
Say average for HashMap and amortized for ArrayList.add — precise words build trust.
Prefer two simple structures kept in sync over one clever structure. Clear code is part of the grade — bas itna yaad rakho: one question, one structure, one invariant.
LeetCode gives design tests as two arrays — method names and arguments. Read them as a script and replay it by hand.

09 · why & how

Questions you might be too shy to ask

How do I know which structures to combine?

List the methods and the question each one must answer fast: find by key, pick by index, newest, smallest, nearest ≤ x, by path. Each question has a standard piece (see the table). Take those pieces, then write down what must stay in sync between them — that is your invariant, and it tells you what every update must touch.

Is HashMap really O(1)?

On average, with a decent hash, yes: each call looks at one bucket. In the worst case many keys share a bucket. Since Java 8 a bucket that grows large is turned into a balanced tree (JEP 180), so even that case is O(log n) for keys that are Comparable. In an interview, say "O(1) average".

What does "O(1) amortized" mean for ArrayList.add?

Most adds just write into a free slot: O(1). Once in a while the backing array is full, so Java copies everything into a bigger one: that one add is O(n). (OpenJDK grows it to about 1.5× — an implementation detail; the spec only promises amortized O(1).) The array grows by a fixed factor, so copies are rare, and spread over many adds the cost per add is still O(1). Amortized = "cheap on average over a long run of calls", with a guarantee, not luck.

LeetCode gives me a class with no main. Where do my fields go, and who calls the methods?

Declare the fields inside the class, outside every method, and set them up where they're declared or in the constructor. For each test case, the judge does new RandomizedSet() once, then calls your methods in the order of the test script. Every call sees the same fields, so whatever one call stores, the next call can read. That shared state is the whole design.

The fields are private final, but I keep changing the map. How?

final only locks the reference: the field always points to the same HashMap object. The contents of that map can still change freely with put and remove. So final stops one bug (accidentally writing freq = new HashMap<>() somewhere) and costs nothing.

Why does getRandom need an array? Can't a HashSet do it?

A set has no index. To return its k-th element you must walk k entries: O(n). An array answers "element at index r" directly, so values.get(random.nextInt(values.size())) is a fair pick in O(1).

Swap-with-last changes the order. Is that allowed?

Only when order doesn't matter, as in a set or a pool of servers. If order matters (a playlist, a queue), you need a linked list or a balanced tree instead, and you pay for it elsewhere.

TreeMap or binary search on a list for the time map?

If timestamps only grow (LC 981 promises it), appending keeps a list sorted: set is O(1) amortized and get is O(log n), with less memory. If timestamps can arrive out of order, or old versions get deleted, use a TreeMap: O(log n) for both.

In Maximum Frequency Stack one value sits in many groups at once. Isn't that wasting memory?

No. Each push adds exactly one entry (to group f) and each pop removes exactly one. So the groups together hold exactly as many entries as the stack has elements: O(n) memory, same as a plain stack. A value pushed 3 times sits once in groups 1, 2 and 3: three entries for three copies.

For LRU Cache, why a doubly linked list? Why not a singly linked one?

On get, the map hands you the node, and you must unlink it from the middle of the list. Unlinking needs the node before it. A doubly linked node has prev, so that's O(1). A singly linked list would have to walk from the head to find the previous node: O(n), and the O(1) promise is gone.

Can I just use LinkedHashMap for LRU Cache in an interview?

Mention it, it shows you know Java: new LinkedHashMap<>(capacity, 0.75f, true) keeps entries in access order, and overriding removeEldestEntry to return size() > capacity evicts the oldest. But ask first. Most interviewers then say "now build it yourself", because the HashMap + doubly linked list is what they are testing.

What if the interviewer asks for thread safety?

Say how you would do it: the simplest is synchronized on every public method, because your methods change two structures that must stay consistent together. A ConcurrentHashMap alone doesn't keep a map and a list in sync. Don't add locks unless asked.

Where does LFU Cache (LC 460) fit?

It combines this chapter's ideas: a count per key, a group per count (each group in least-recently-used order) and the minimum count. Build it after Maximum Frequency Stack here and LRU Cache in the linked-lists chapter.

My design works but the code is long. Is that bad?

Not if each method is short and does one thing. Pull a repeated walk or lookup into one private helper (like walk(path) in the file system), name fields by their meaning (indexOf, maxFreq), and the length stops mattering.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#380
Insert Delete GetRandom O(1)must-do
MediumBloombergUberLinkedInByteDance / TikTokApple+1
#981
Time Based Key-Value Storemust-do
MediumNetflixAppleUberAmazonMicrosoft+1
#2013
Detect Squares
MediumGoogleAmazon
#895
Maximum Frequency Stackmust-do
HardAmazonMicrosoftGoogle
#588
Design In-Memory File SystemLeetCode Premium
HardUberAmazonMicrosoftGoogle

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#146
LRU Cache
Mediumin Linked Lists
The most-asked design round. get and put must be O(1), so a HashMap finds the node and a doubly linked list keeps recency order — two structures, one invariant.
#155
Min Stack
Mediumin Stacks
Augment instead of search: each entry stores the minimum below it, so getMin never scans — the same move as keeping maxFreq here.
#355
Design Twitter
Mediumin Heaps
Compose per-user pieces (a follow set, a tweet list) and merge them on read with a heap: a design that moves the expensive work to the query.
#208
Implement Trie (Prefix Tree)
Mediumin Tries
The node behind this chapter's file system: a children map plus an end flag. Here the edges are whole names instead of letters.
#622
Design Circular Queue
Mediumin Queues
Fixed memory, O(1) per call: an array with head + size, where every other index is derived. The invariant does the work.
#705
Design HashSet
Easyin Java OOP
Build the hash table itself (buckets + chaining). Knowing why it is O(1) on average is what lets you promise O(1) in every design here.
#528
Random Pick with Weight
Mediumin Math & Numbers
getRandom's weighted cousin: prefix sums and a binary search turn a random ticket into an index.
#729
My Calendar I
Mediumin BST
TreeMap floor and ceiling inside a design class — the time map's lookup, used to reject overlapping bookings.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A design question = an API + a cost per method. Pick one structure per method's question, glue them with an invariant, keep them in sync on every call.
use it when
"Design X" or "implement the class" with methods like insert, get, pop, ls — and targets like O(1) or O(log n) per call.
template
Routine: API → cost per method → structures → invariant as a comment → code each method → dry-run a script of calls.
template
O(1) delete: values.set(i, last); indexOf.put(last, i); values.remove(size - 1); indexOf.remove(val);
cost
RandomizedSet O(1) avg · FreqStack O(1) avg · TimeMap set O(1) amortized, get O(log v) · file system O(depth · log c) · DetectSquares O(one column).
trap
Swap-with-last: update the moved element's index, and remove val from the map last — or deleting the last element breaks.
trap
list.remove(5) on a List<Integer> removes index 5, not the value 5. And "/a".split("/") starts with an empty string.
pro tip
Most frequent, newest wins → count → stack groups + a maxFreq that moves by ±1. Value at time t → floor search in a time-sorted history.
pro tip
Paths → a trie of names (TreeMap children give sorted ls). Shapes from stored points → count copies, loop over one column.
pro tip
Say average for HashMap and amortized for ArrayList.add. Then dry-run: empty, delete the last element, duplicates, a tie.

12 · recall

Flip, remember, repeat

card 1 / 13

recall

What are the steps of the design-round routine?

tap or Space to flip ↻

Question 1: What are the steps of the design-round routine?

13 · check yourself

Quick quiz

values = [10, 40, 30, 20] and indexOf maps each value to its index. You remove 40 by swapping with the last. What is values now, and what is indexOf.get(20)?
In remove(val), why call indexOf.remove(val) after indexOf.put(last, i)?
Why can't a HashSet alone give getRandom in O(1)?
FreqStack after push(4), push(6), push(6), push(4). What does pop() return?
In FreqStack.pop, group[maxFreq] becomes empty. What should happen to maxFreq?
TimeMap: set(k, "a", 2), set(k, "b", 5), set(k, "c", 9). What does get(k, 8) return?
Why can LC 981 keep each key's history in a plain ArrayList and still binary-search it?
What does `"/".split("/")` return in Java?
DetectSquares holds (3,10), (11,2), (3,2) and a second (11,2). What is count([11,10])?
In a design round, what should you write before any method body?

0/0 correct · 10 left

14 · learn more