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) and 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" — 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.

The one-line idea: 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()                       # any index holding val
    last = self.arr[-1]
    self.arr[i] = last                            # overwrite the hole
    self.idx[last].add(i); self.idx[last].discard(len(self.arr) - 1)
    self.arr.pop()
    return True

Three lines of bookkeeping and every one is load-bearing. The moved element's index set must gain i and lose the old last position — and when val is the last element, add before discard is what keeps the set correct rather than emptying it.

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 getMaxKeyandgetMinKeyinO(1)`, which no heap provides — a min-heap knows its minimum and a max-heap 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:

head ↔ [count 1: {"a", "d"}] ↔ [count 3: {"b"}] ↔ [count 7: {"c"}] ↔ 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 candidate positions:

best = 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.

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.

i = 2 popped from idx[2]        idx[2] = {1}
last = arr[-1] = 3
arr[2] = 3                      arr = [1, 2, 3, 3]
idx[3].add(2)                   idx[3] = {2, 3}
idx[3].discard(3)               idx[3] = {2}
arr.pop()                       arr = [1, 2, 3]

final: arr = [1, 2, 3]   idx = {1:{0}, 2:{1}, 3:{2}}     ✓ consistent

Order is destroyed — the surviving 2 is now before the 3 that used to be at the end — 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 five lines it does.

5. Where you'll actually meet this

• Cache layers. LFU is a real eviction policy, and this is how it is really implemented.
• Rate limiters. Counting per client with O(1) hottest and coldest lookup is the All-O`one interface.
• Sampling systems. Uniform selection from a mutable multiset backs A/B assignment and load shedding.
• Seat and slot allocation. Maximising distance to the nearest occupant is used in venues, parking and cell placement.
• Session and connection pools. Any "evict the least used" policy is this structure with the names changed.

6. Problems in this chapter

▶ All O`one 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(n) per call, or O(log n) with a gap heap.

▶ 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.
• discard before add in the swap-and-pop when the removed value is the last element, which empties the set.
• 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 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` return nothing.

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.