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.
Fun fact: LFU Cache is usually attempted with a heap keyed by frequency, which gives
O(log n)per operation, not the requiredO(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 integermin_freq. Eviction is then "take the oldest key in themin_freqbucket", which is constant time. Andmin_freqonly 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_freqincreases by exactly one. It can never jump further, because the promoted key is now sitting atmin_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:
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.
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 textbookO(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 wheni != 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 forO(1). - Failing to repair
min_freqafter 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-O
one, which makesgetMaxKeyandgetMinKey` read an empty bucket. - Claiming
O(log n)for Exam Roomleave. Deleting from the middle of a sorted array is linear.
8. Key takeaways
- The stated bound is the design brief. Write it beside each method before choosing anything.
- Hash map for lookup, something ordered for order. Every solution here is that pair.
- Swap-and-pop turns
O(n)deletion intoO(1)whenever order is not required. - Buckets replace the heap when you need both extremes, or constant-time eviction.
- A minimum pointer only ever moves by one after a promotion, which is why it stays
O(1). - Boundaries are where these break: the ends of a row, the last element of an array, the empty bucket.
- 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.
Insert Delete GetRandom O(1) - Duplicates Allowed
Core idea: Keep every occurrence (duplicates included) in a flat array, so a random index is O(1) and
get_random's probability scales with multiplicity for free. Beside it keep a mapvalue -> set of indices where that value lives. To remove one copy, take any index from that set, move the last array element into that slot, fix the moved element's entry in its own set, then pop the tail. The delete is O(1), leaves no hole, and survives duplicates.
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