</> 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%

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

Flow: the dict is the source of truth, the heap only orders, stale entries discarded

Fun fact: lazy deletion is not only an interview trick, it is a common way to write Dijkstra's algorithm. The textbook version calls for a decrease-key operation that Python's heapq does not have. So many implementations push the improved distance as a new entry and skip any popped entry whose distance is worse than the best known. Same structure, same validity check, same reason. Recognising that Dijkstra and these two 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.


Core 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 heap size and the cleanup work are bounded by the number of operations m, not by the number of live items n.

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. In Food Rating, peek before popping: a query only reads the top, so the valid top must stay in the heap for the next call. (Task Manager is different: execTop executes the task, so it pops the valid entry and deletes the task from the dict.) 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.

The priority comparison has one gap. If an id could be removed and then added again with the same priority as an old stale entry, that stale entry would be accepted. The Task Manager statement guarantees add gets an id that does not exist at that moment, so the lesson's check compares only the priority. If reuse were allowed, store a version counter in each entry as well.

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).

Worked example: stale heap entries overruled by the dict

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

  • Priority schedulers and job queues. Anything that dispatches the highest-priority job has to cope with a job being re-prioritised or cancelled before it runs.
  • Shortest paths. Dijkstra and A* are often written with lazy deletion instead of decrease-key.
  • The Python standard library. The heapq documentation describes this pattern for priority queues: mark an entry as removed and skip it when it surfaces.
  • Per-category rankings. Top-rated item per category while ratings keep changing, which is the Food Rating problem.

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 + c)) per changeRating and amortised O(log(n + c)) per highestRated, where c is the number of rating changes so far.

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. The lesson also covers an indexed heap that updates entries in place and keeps the heap at O(n).
Pattern: heap + lazy deletion with removal. Target: add and edit O(log m), remove O(1), execTop amortised O(log m), where m is the total number of operations, since the heap can hold one entry per add and edit.


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 in a read-only query like highestRated, which loses the valid top 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. The heap can hold up to n + c entries (or m in Task Manager), so the bound is O(log m) or O(log(n + c)), and the read is amortised: one call can discard many stale entries, but each was pushed once.
  • Reusing an id while an old entry with the same priority is still in the heap, which the priority check would accept.

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 when the heap has no cheap update, which is why Dijkstra is often written this way.
  3. Validate at read time, against the authority, every time.
  4. In a read-only query, peek, then pop only if stale. A valid top must survive the call. (Task Manager's execTop pops the valid entry because it executes the task.)
  5. Tie-breaks belong in the heap key, negated as needed for a min-heap.
  6. Say "amortised" and "log of m". The bound is real but it is not per-operation worst case, and the heap holds stale entries. An indexed heap gives worst-case O(log n) and O(n) space at the cost of more code.
  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.

Design a Food Rating System

Core idea: Keep one max-heap per cuisine keyed by (-rating, food) so the smallest tuple at the top is the highest rating, ties broken by the lexicographically smallest name. On a rating change, push a fresh entry and leave the old one alone. On a query, pop from the top while the entry's rating no longer matches the source-of-truth dictionary, and return the first entry that does match.

Problem, rephrased

You're building the ratings backend for a food-delivery app. Every dish belongs to a cuisine, diners revise ratings all day, and each cuisine tab must show its current top dish. The catalog arrives as three parallel arrays of length n: foods[i] is a dish name, cuisines[i] is its cuisine, ratings[i] is its starting rating.

Build a FoodRatings class with three operations:

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.