Katkat
Back

Escalation Stack That Resolves the Most-Reported Issue First

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Design a support-escalation structure where resolving an issue always clears whichever one currently has the most open reports, breaking ties by the most recently reported occurrence. Tests combining frequency and recency so both operations run in O(1).

A support team logs incoming issue reports by category (e.g. "login-timeout"). When an on-call engineer is free to resolve one issue, they always pick this way:

  • Resolve whichever category currently has the most open reports.
  • If several categories tie, resolve the one whose most recent report happened more recently than the others' most recent reports.
  • Resolving a category closes exactly one of its open reports — the most recent one. The rest stay open.

Implement the class:

class EscalationStack:
    def report(self, issue: str) -> None: ...
    def resolve(self) -> str: ...   # never called when there are no open reports

Also write a driver, process(log: list[str]) -> list[str]. Each entry in log is either an issue category (a report) or the literal string "RESOLVE". Return the categories resolved, in order.

Examples

log = ["login-timeout", "payment-decline", "login-timeout", "sync-lag", "payment-decline",
       "RESOLVE", "RESOLVE", "RESOLVE", "RESOLVE"]
out = ["payment-decline", "login-timeout", "sync-lag", "payment-decline"]
  • Open reports: login-timeout x2, payment-decline x2, sync-lag x1. login-timeout and payment-decline tie at 2; payment-decline's latest report (5th) is newer than login-timeout's (3rd). Resolve payment-decline.
  • Now login-timeout is the only one with 2. Resolve login-timeout.
  • All three remaining categories have 1 open report each; sync-lag's is the newest still-open one (4th). Resolve sync-lag, then payment-decline (2nd), ending at one open report overall after four resolves.
log = ["a", "b", "b", "RESOLVE", "a", "RESOLVE", "RESOLVE", "c", "RESOLVE"]
out = ["b", "a", "b", "c"]

Constraints

  • Up to 2 * 10^5 operations total.
  • report and resolve should each run in O(1) time (amortized is fine).
  • Issue names are arbitrary non-empty strings, never equal to "RESOLVE".

Hints

Hint 1

A heap keyed on (count, last-report time) gives O(log n) but needs lazy deletion to handle stale entries cleanly. Is there a way to avoid ordering entirely?

Hint 2

A category's open-report count only ever changes by +1 or -1. What if you grouped categories by their current count instead of sorting them?

Hint 3

Keep one stack per count level. When a category's count reaches k, push it onto level k's stack. The answer to resolve() is always the top of the highest non-empty level.

Hint 4

When the top level empties out, why is the new maximum always exactly one lower, never lower than that?

Follow-up questions

  • Add `withdraw(issue)`, which removes a customer's most recent still-open report for that issue (it was a duplicate). Can you keep it O(1)?
  • Change the tie-break to the *oldest* still-open report instead of the newest. What has to change in the data structure?
  • Reports should expire automatically after 24 hours. How would you support that without scanning every open report?
  • How would you shard this across many support queues handled by independent on-call engineers?