Designing a data structure

Implement a hash map with get, put and remove, without using the language's built-in map.

Trigger

This is the one the recruiter named explicitly: implement one using only arrays.

Approach

1. Say the three pieces: hash function, compression modulo capacity, collision resolution.
2. Pick a strategy out loud and justify it — chaining is simpler, open addressing is cache-friendly.
3. Handle the key-already-exists case in put (overwrite, do not append).
4. Add the resize at a load factor threshold, doubling capacity and rehashing everything.
5. If open addressing: deletion needs a tombstone, and the resize trigger must count tombstones.

Target complexity

O(1) average, O(n) worst case; O(n + m) space.

Pitfall

Omitting the resize entirely. Without it every operation degrades to O(n) and the implementation is not finished.

Say it out loud

“I'll use separate chaining because deletion is trivial and it tolerates a load factor above one. When the load factor crosses 0.75 I double the capacity and rehash — I can't copy the buckets, because the index depends on the modulus and that just changed. That resize is O(n) but it's amortised constant across insertions.”

Solve on LeetCode

Design a set supporting insert, delete and uniform random retrieval, all in O(1).

Trigger

'Design a…' with an O(1) target on every operation.

Approach

1. O(1) random needs an array. O(1) delete needs a hash map. So use both.
2. A list holds the values; a dict maps value to its index in the list.
3. Delete: swap the target with the last element, update the moved element's index, pop.

Target complexity

O(1) average for all three; O(n) space.

Pitfall

Forgetting to update the moved element's index after the swap. The structure silently corrupts.

Say it out loud

“The two requirements pull in different directions: random access wants an array, deletion wants a map. I'll combine them — a list for the values and a dict from value to index — and delete by swapping with the last element so removal stays constant.”

Solve on LeetCode

Design a fixed-capacity cache that evicts the least recently used entry, with O(1) operations.

Trigger

'Design a cache' plus 'O(1) for get and put'.

Approach

1. O(1) lookup wants a hash map; O(1) reordering wants a doubly linked list. Use both.
2. The map points at nodes; the list keeps recency order with the most recent at the head.
3. get: find via the map, unlink, move to head. put: insert at head, evict the tail if over capacity.
4. Use sentinel head and tail nodes so there are no null edge cases.

Target complexity

O(1) for both operations; O(capacity) space.

Pitfall

A singly linked list. You cannot unlink a node in O(1) without the previous pointer.

Say it out loud

“This is the combine-two-structures pattern. The hash map gives constant lookup but no order; the doubly linked list gives constant reordering but no lookup. Together they give both. I'll use sentinel nodes at each end so I never special-case the empty or single-element list.”

Solve on LeetCode

Design a stack that also reports its minimum in O(1).

Trigger

'Design a stack with an extra O(1) query'.

Approach

1. A second stack holding the minimum at each level.
2. On push, push min(new, current_min). On pop, pop both.
3. Optimisation worth mentioning: only push to the min stack when the value ties or beats the current minimum.

Target complexity

O(1) for every operation, O(n) space.

Pitfall

Recomputing the minimum on pop. That is O(n) and defeats the whole point.

Say it out loud

“The trick is storing the minimum *at each level* rather than one running value, because popping has to restore the previous minimum. A parallel stack does that in constant time for every operation.”

Solve on LeetCode

Sort an array without using the language's built-in sort.

Trigger

The email is explicit: know quicksort and merge sort in detail.

Approach

1. Say which you'll write and why. Merge sort for the worst-case guarantee, quicksort for space.
2. If quicksort: random pivot — without it, sorted input is O(n²).
3. If quicksort: recurse into the smaller partition and loop on the larger, bounding the stack at O(log n).
4. If merge sort: allocate the buffer once, not per call.

Target complexity

O(n log n) time. Merge sort O(n) space; quicksort O(log n) stack.

Pitfall

A fixed pivot at the last element. Sorted input — the most common real input — degrades to quadratic.

Say it out loud

“I'll write merge sort because it guarantees n log n in the worst case and it's stable. If you'd rather see quicksort, the two details I'd be careful with are a random pivot, so sorted input doesn't degrade it, and recursing into the smaller side so the stack stays logarithmic.”

Solve on LeetCode