Live top-k best-selling books leaderboard

A bookstore wants a live leaderboard of its best-selling books. Sales arrive one at a time, and the leaderboard can be read at any moment.

Implement a BookSalesTracker class:

• BookSalesTracker(): creates an empty tracker.
• record_sale(book_id: str, quantity: int = 1) -> int: adds quantity copies to the book's running total and returns the new total. quantity is a positive integer.
• get_sales(book_id: str) -> int: returns the book's total, or 0 if it has never sold.
• top_k(k: int) -> List[str]: returns up to k book ids with the highest totals, best first. Break ties by the smaller book id. If fewer than k books have sales, return all of them. Return [] when k <= 0.

Constraints

• Up to 10^5 distinct books and 10^6 calls in total.
• top_k may be called as often as record_sale, so avoid sorting every book on each read.

Example

t = BookSalesTracker()
t.record_sale("dune", 5)      # 5
t.record_sale("emma", 3)      # 3
t.record_sale("beloved", 3)   # 3
t.top_k(2)                    # ["dune", "beloved"]  (tie at 3 goes to the smaller id)
t.record_sale("emma", 4)      # 7
t.top_k(3)                    # ["emma", "dune", "beloved"]
t.top_k(10)                   # ["emma", "dune", "beloved"]
t.get_sales("missing")        # 0

Interviewers often add parts: returns that lower a total, a leaderboard over only the last hour, per-category leaderboards, or a tracker spread across many machines.

Reconstructed from the reported question; details may differ from what interviewers ask.