Design a logger that returns top-K messages

Problem

Design an in-memory logging component that supports recording log events and querying the top K most frequent messages.

Each log event has:

• timestamp (integer seconds)
• message (string)

Implement the following operations:

1. log(timestamp, message) : record a new log event.
2. topK(startTime, endTime, k) -> List[str] : return up to k messages with the highest frequency among events with startTime <= timestamp <= endTime .
   • If there is a tie in frequency, break ties by lexicographically smaller message first (or state and apply a consistent tie-break rule).
   • If there are fewer than k distinct messages in the interval, return all of them.

Requirements

• You may assume timestamps are non-decreasing across calls to log .
• Use a heap in your approach for extracting the top K.

Constraints (reasonable interview assumptions)

• Up to 2 * 10^5 total log() calls
• Up to 2 * 10^5 total queries
• k can be up to the number of distinct messages in the queried interval

Example

Logs:

• log(1, "A") , log(2, "B") , log(3, "A") , log(10, "C")

Query:

• topK(1, 3, 2) → ["A", "B"] (A appears 2 times, B appears 1 time)