Ranking Systems

What is this?

Both problems ask for "the current best" while the scores keep changing underneath. A heap answers "the best" perfectly and cannot update a key at all — so the resolution is counter-intuitive and the same in both: do not fix the heap. Push a new entry, leave the old one rotting, and discard stale entries when they surface at the top.

That works only because there is a second structure — a plain dictionary — that is always right, and every pop is checked against it.

💡 Fun fact: lazy deletion is not an interview shortcut — it is how Dijkstra's algorithm is written in practice. The textbook version calls for a decrease-key operation that Python's heapq does not have and that most real heaps make awkward. So every production implementation pushes the improved distance as a new entry and skips any popped entry whose distance no longer matches the current best. Same structure, same validity check, same reason. Recognising that these three problems are one pattern is worth more than any of them individually.

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

The one-line idea: keep one structure that is always correct and one that is merely ordered. Never repair the ordered one — validate against the correct one at the moment you read.

1. The two structures

self.info = {}                              # food/task id → the CURRENT value. authoritative.
self.heap = defaultdict(list)               # cuisine → [(-rating, name), …]. ordering only.

def change(self, key, new_value):
    self.info[key] = (new_value, group)     # O(1) — the truth is updated here
    heappush(self.heap[group], (-new_value, key))     # O(log n) — a second, newer entry

change never searches the heap and never removes anything from it. The heap may end up holding several entries per key, all but one obsolete, and that is by design — the cost is bounded by the number of operations, not by the number of live items.

2. The validity check

def best(self, group):
    h = self.heap[group]
    while h:
        neg_rating, key = h[0]
        if self.info[key][0] == -neg_rating:          # the dict agrees → genuine
            return key
        heappop(h)                                     # stale → discard and look again

Two details decide whether this is correct. Peek before popping: the valid top must stay in the heap for the next call. And the comparison must be against the authority, not against a remembered value — a key whose rating changed and changed back is still valid, and a check based on "has this been edited" would wrongly reject it.

For Task Manager, remove deletes the key from the dict, so the validity check must also handle a key that is absent entirely — self.info.get(key) returning None is a stale entry, not a crash.

3. Tie-breaks ride in the key

Neither problem breaks ties by insertion order:

• Food ratings want the lexicographically smallest name, which (-rating, name) gives directly, since Python compares tuples left to right.
• Task Manager wants the largest task id, which needs (-priority, -taskId) — negating both components so a min-heap yields the maximum of each.

Getting the tie-break into the tuple is what keeps best free of comparison logic. A tie-break handled after the pop is a tie-break that is wrong on the boundary.

4. A 30-second worked example (stale entries)

Tasks [[1,101,10], [2,102,20], [3,103,15]], then edit(102, 8).

dict:  101→(10,u1)   102→(8,u2)   103→(15,u3)          ← authoritative
heap:  (-20,-102)  (-15,-103)  (-10,-101)  (-8,-102)   ← two entries for 102

execTop():
  peek (-20,-102)   dict says 102 has priority 8, not 20   → stale, pop
  peek (-15,-103)   dict says 103 has priority 15          → match, return user 3

The stale (-20, -102) sits at the very top of the heap and is exactly the wrong answer — it is the entry an implementation without the validity check would return. Notice too that it is only discarded when it surfaces: had execTop never been called, the cleanup would never have happened, and nothing would have been wrong.

5. Where you'll actually meet this

• Schedulers. Cluster and OS schedulers pop the highest-priority job while priorities are renice'd and jobs cancelled underneath.
• Job queues. Celery, Sidekiq and every delayed-job system allow reprioritising and cancelling before execution.
• Shortest paths. Dijkstra and A* with lazy deletion instead of decrease-key is the standard implementation.
• Event simulation. Timer wheels validate a popped event against the live timer table before firing it.
• Leaderboards. Live rankings where scores stream in continuously and only the top is ever read.

6. Problems in this chapter

▶ Design a Food Rating System

Highest-rated food per cuisine, ties by lexicographically smallest name, with ratings changing over time. Per-cuisine heap plus an authoritative dictionary.
Pattern: heap + lazy deletion. Target: O(log n) per operation.

▶ Design Task Manager

Add, edit, remove and execute the highest-priority task, ties by largest task id. A dictionary is the truth; the heap only orders, and stale entries are skipped on pop.
Pattern: heap + lazy deletion with removal. Target: O(log n) amortised per operation.

7. Common pitfalls 🚫

• Trying to update inside the heap. There is no such operation; that is the whole reason for this design.
• Popping instead of peeking when the top is valid, which loses it for the next call.
• Validating against a remembered value rather than the dictionary — a value that changed and changed back is still valid.
• Not handling a deleted key in the validity check; an absent entry is stale, not an error.
• Breaking ties after the pop instead of encoding them in the heap key.
• Forgetting to negate both components for a max-heap on two fields.
• Claiming O(log n) without qualification. It is amortised — one call can discard many stale entries, but each was pushed once.

8. Key takeaways

1. One structure is the truth; the other is only an order. Never confuse their roles.
2. Lazy deletion beats repairing the heap — and it is what real schedulers do.
3. Validate at read time, against the authority, every time.
4. Peek, then pop only if stale. A valid top must survive the call.
5. Tie-breaks belong in the heap key, negated as needed for a min-heap.
6. Say "amortised". The bound is real but it is not per-operation worst case.
7. Why interviewers like it: the naive design is obvious and impossible, so the conversation goes straight to the trade-off that makes it work.

Order: Design a Food Rating System → Design Task Manager.