Best score from three books in different categories

A student's reading log is a list of (category, points) pairs, one per book read. Score the log: count at most three books, at most one book from any category, and return the highest total you can reach.

Interface

Unless you agree on a different interface with the interviewer, assume:

• get_max_score(books: list[tuple[str, int]]) -> int — returns the best total. With fewer than three categories, count one book from each. An empty log scores 0.

Example

get_max_score([("Adventure", 5), ("Adventure", 2), ("History", 3)])                    ->  8   # 5 + 3
get_max_score([("Adventure", 4), ("History", 3), ("Reference", 1), ("Fiction", 2)])    ->  9   # 4 + 3 + 2
get_max_score([("Biography", 2), ("Biography", 4), ("Science", 3), ("Science", 1)])    ->  7   # 4 + 3
get_max_score([])                                                                       ->  0

Constraints

• The log can be long, so trying every combination of three books is too slow.
• Points are integers. Category names are case-sensitive strings.

Clarifying questions

• Can points be zero or negative? If so, is it better to count fewer than three books?
• Are "History" and "history" the same category?
• Do you want only the score, or also which books were picked?
• Is the limit always three, or should it be a parameter k?

What a strong answer covers

• One pass that keeps the best score per category in a dictionary, then the three largest of those values.
• Picking the top three in O(c) with a size-3 min-heap or three running variables, instead of sorting all c categories (O(c log c)).
• Total cost O(n) time and O(c) space.
• Tests: an empty log, one category with many books, fewer than three categories, ties.

Follow-ups

• Do it without heapq or sorting: keep the top three in plain variables and shift them as new values arrive.
• Generalize to the best k categories. What does that cost?
• Return the chosen books along with the score, with a fixed tie rule.