</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Structures Under Constraints

What is this?

Each of these hands you an interface and a complexity requirement, and the requirement is the design brief. O(1) random access rules out a linked list. O(1) minimum and maximum rules out a heap. O(1) eviction by frequency rules out sorting. What survives every time is a hash map for lookup paired with something that maintains order, and the work is keeping the two exactly in step.

Decision tree: the time bound rules out a structure so pick what is left

Fun fact: LFU Cache is usually attempted with a heap keyed by frequency, which gives O(log n) per operation, not the required O(1). The structure that does work is two levels deep: a map from frequency to an ordered collection of keys at that frequency, plus a single integer min_freq. Eviction is then "take the oldest key in the min_freq bucket", which is constant time. And min_freq only ever needs one specific repair: after promoting a key out of its bucket, if that bucket is now empty and it was the minimum, min_freq increases by exactly one. It can never jump further, because the promoted key is now sitting at min_freq + 1.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Summary: a hash map gives you O(1) lookup and no order; a list, bucket chain or array gives you order and no lookup. Every problem here is the two of them, wired together and updated together.


1. Swap with the last, then pop

def remove(self, val):
    if not self.idx[val]: return False
    i = self.idx[val].pop()                       # discard the victim first
    last_i = len(self.arr) - 1
    if i != last_i:                               # a tail move only if there is one
        last = self.arr[last_i]
        self.arr[i] = last                        # overwrite the hole
        self.idx[last].discard(last_i); self.idx[last].add(i)
    self.arr.pop()
    return True

Each line of bookkeeping is load-bearing. The victim's index leaves its set before anything else. If the victim is the last element (i == last_i) there is nothing to move, and skipping the move is what keeps the set correct: with [7, 7], moving the tail anyway would delete both indices of the 7s from the set.

Duplicates are why idx maps to a set of positions rather than to one. getRandom is then random.choice(self.arr), and each value appears in proportion to its multiplicity, which is precisely what the problem asks for.

2. Buckets, when a heap will not do

*All Oone* needs inc, dec, getMaxKeyandgetMinKeyall inO(1). A heap pays O(log n)` per update, and one heap knows only its minimum or its maximum, never both. The structure is a doubly linked list of buckets in increasing count order, plus a map from key to its bucket:

Count buckets in a doubly linked list from head to tail

inc moves a key to the next bucket, creating it if the neighbour's count is not exactly one more; dec moves it back. Max and min are the buckets adjacent to tail and head. Every operation touches a constant number of nodes, and the empty bucket must be unlinked or the ends stop being meaningful.

3. Maximise the distance to the nearest

Exam Room keeps the occupied seats sorted and, on each seat(), evaluates three kinds of candidate (an empty room returns seat 0):

best, pos = seats[0], 0                            # sit at 0: distance to the first
for a, b in zip(seats, seats[1:]):
    if (b - a) // 2 > best: best, pos = (b - a) // 2, a + (b - a) // 2
if (n - 1) - seats[-1] > best: pos = n - 1         # sit at the far end

The two ends are special cases and the source of most wrong answers: sitting at seat 0 or seat n - 1 has only one neighbour, so its distance is the full gap rather than half of it. Ties go to the smaller seat number, which falls out of using a strict > while scanning left to right.

With a sorted list the scan costs O(k) per call for k seated students, and leave() is O(k) too, because deleting from the middle of an array shifts the tail. A max-heap of gaps with lazy deletion brings both calls to O(log q) amortized over q calls: a gap whose neighbours changed is left in the heap and discarded when it surfaces.


4. A 30-second worked example (swap and pop)

arr = [1, 2, 2, 3], idx = {1: {0}, 2: {1, 2}, 3: {3}}. Remove one 2, and suppose the set hands back index 2.

Worked example trace: swap and pop to delete value 2

The tail 3 moves into the hole at index 2. Had the set handed back index 1, the result would be [1, 3, 2], so order is not preserved in general, and that is fine, because nothing in the interface promised order. The only invariant that matters is that idx[v] holds exactly the positions where v lives, and after those few lines it does.


5. Where you'll actually meet this

  • Cache layers. LFU is a real eviction policy: Redis offers allkeys-lfu, and Caffeine admits entries with a TinyLFU frequency sketch. Both use approximate counters rather than the exact buckets here, which are the textbook O(1) design.
  • Per-client counters. Counting requests per client with O(1) busiest and quietest lookup is the All-O`one interface.
  • Weighted sampling. A pool where a server with weight 3 holds three slots, picked uniformly, is a multiset with O(1) draw.
  • Farthest-point placement. Greedily placing the next item as far as possible from those already on a line is the Exam Room query.

6. Problems in this chapter

[All O`one Data Structure](/curriculum/coding-interview/301/chapters/design-and-code/structures-under-constraints/all-oone-data-structure)

Increment, decrement, and report the max and min keys, all in O(1). Doubly linked list of count buckets with a key → node map.
Pattern: bucket list + hash map. Target: O(1) every operation.

Exam Room

Seat a student as far as possible from the nearest occupant, smallest index on a tie. Keep the seats sorted and evaluate both ends plus every gap.
Pattern: sorted structure with explicit boundary cases. Target: O(k) per call with a sorted list, or O(log q) amortized with a gap heap and lazy deletion.

LFU Cache

Get and put in O(1), evicting the least frequently used and breaking ties by age. Frequency buckets of ordered keys, plus min_freq.
Pattern: two-level map with a minimum pointer. Target: O(1) get and put.

Insert Delete GetRandom O(1) - Duplicates Allowed

A multiset with O(1) insert, remove and uniform random draw. Array of values plus a value → set of indices map.
Pattern: array + index sets, swap-and-pop. Target: O(1) average.


7. Common pitfalls

  • Updating one structure and not the other. This is the bug in this chapter, every time.
  • Moving the tail when the victim is the tail in the swap-and-pop. With [7, 7] it deletes both indices from the set. Discard the victim first and move only when i != last_i.
  • Preserving order in getRandom, which is not required and costs you the bound.
  • Reaching for a heap in LFU. It gives O(log n) and lets stale entries pile up, and the problem asks for O(1).
  • Failing to repair min_freq after a promotion empties its bucket.
  • Forgetting the two ends in Exam Room, where the distance is the whole gap, not half.
  • Leaving empty buckets linked in All-Oone, which makes getMaxKeyandgetMinKey` read an empty bucket.
  • Claiming O(log n) for Exam Room leave. Deleting from the middle of a sorted array is linear.

8. Key takeaways

  1. The stated bound is the design brief. Write it beside each method before choosing anything.
  2. Hash map for lookup, something ordered for order. Every solution here is that pair.
  3. Swap-and-pop turns O(n) deletion into O(1) whenever order is not required.
  4. Buckets replace the heap when you need both extremes, or constant-time eviction.
  5. A minimum pointer only ever moves by one after a promotion, which is why it stays O(1).
  6. Boundaries are where these break: the ends of a row, the last element of an array, the empty bucket.
  7. Why interviewers like it: the design is half the answer and the synchronisation is the other half, and both are visible in the code you write.

Order: All O`one Data Structure → Exam Room → LFU Cache → Insert Delete GetRandom O(1) - Duplicates Allowed.

Core idea: Keep keys grouped into buckets by their exact count, and chain those buckets in a doubly-linked list ordered by count. Incrementing or decrementing a key just hops it to the neighbouring bucket, and the min and max keys sit at the two ends of the list, so every operation is O(1).

Problem, rephrased

A live dashboard for a streaming service tracks how many times each track has been played today, and a producer wants the current most-played and least-played titles flashed on screen at every refresh. You're given a stream of counter operations keyed by track name: inc(key) records one more play of key, inserting it with count 1 if it isn't tracked yet; dec(key) retracts a play (a skip inside the grace window), removing key entirely once its count hits 0, dec on a missing key is a no-op.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.