Top K Selling Books After Each Sale
Design TopSellers(k). Each call sale(book, quantity) adds to the book's total and returns the current top k books: highest total first, ties broken alphabetically.
top = TopSellers(2)
top.sale("A", 5) -> ["A"]
top.sale("B", 7) -> ["B", "A"]
top.sale("A", 3) -> ["A", "B"]
top.sale("C", 8) -> ["A", "C"]Hints
Hint 1
Keep a map from book to total. The straightforward version sorts the map's entries after each sale and slices k.
Hint 2
When the catalogue is large and k small, keep the current top k as a sorted list: a sale can move its book up within the list or into it, and nothing else changes.