Design a logger that returns top-K messages

Task

Design an in-memory logging system that tracks incoming messages with their arrival timestamps and supports querying the top-k most frequent messages within a specified time range [start_time, end_time] (inclusive).

Implement the TopKLogger class:

• TopKLogger(): Initializes the logger object.
• log_message(timestamp: int, message: str) -> None: Records that message occurred at timestamp. Calls arrive in non-decreasing order of timestamp.
• get_top_k(start_time: int, end_time: int, k: int) -> list[str]: Returns a list of the k most frequent messages logged with timestamps between start_time and end_time (inclusive). If two messages have the same frequency, the lexicographically smaller message should appear first. If there are fewer than k unique messages in the range, return all of them ordered by frequency then lexicographically.

Interface

class TopKLogger:
    def __init__(self):
        pass

    def log_message(self, timestamp: int, message: str) -> None:
        pass

    def get_top_k(self, start_time: int, end_time: int, k: int) -> list[str]:
        pass

Examples

Example 1

logger = TopKLogger()
logger.log_message(1, "error")
logger.log_message(2, "info")
logger.log_message(3, "error")
logger.log_message(5, "warn")
logger.log_message(6, "info")
logger.log_message(7, "error")

# Between t=1 and t=5: "error" appears 2 times, "info" 1 time, "warn" 1 time.
# Top 2: "error" (count 2), then "info" beats "warn" lexicographically (both count 1).
logger.get_top_k(1, 5, 2)  # Returns ["error", "info"]

# Between t=4 and t=7: "warn" (1), "info" (1), "error" (1)
logger.get_top_k(4, 7, 3)  # Returns ["error", "info", "warn"]

Constraints

• 1 <= timestamp <= 10^9
• timestamp values in log_message are non-decreasing.
• start_time <= end_time
• 1 <= k <= 100
• 1 <= len(message) <= 50
• At most 10^5 calls to log_message.
• At most 500 calls to get_top_k.

Edge Cases

• No messages exist within [start_time, end_time]: return an empty list [].
• Fewer than k unique messages exist: return all unique messages properly sorted.
• Multiple messages with the same count: break ties using lexicographical order.