# Deduplicate and Order Batch and Streaming Logs A log is `(timestamp, message)`, where `timestamp` is an integer and `message` is compared exactly. Input order may differ from timestamp order. Implement these related behaviors: 1. `dedupe_first(logs)`: keep the first input occurrence of each message, then return retained logs sorted by `(timestamp, original_input_index)`. 2. `dedupe_latest(logs)`: keep the occurrence with the greatest timestamp for each message. If timestamps tie, keep the later input occurrence. Return retained logs sorted by `(timestamp, retained_input_index)`. 3. `StreamingLogs(policy)`, where `policy` is `first` or `latest`, with `add(timestamp, message)` and `get_next()`. `get_next` removes and returns the retained entry with the smallest `(timestamp, sequence_number)`, or returns `None` when no entry is currently available. For streaming `latest`, adding a newer version supersedes an unconsumed older version. Stale heap entries must never be returned. Once an entry has been returned, later arrivals do not retract it. ## Constraints - Up to `200000` batch logs or streaming operations. - Messages are non-empty strings. - Batch output must be deterministic. - Explain batch complexity and amortized streaming complexity. ## Example For `[(5, "x"), (2, "y"), (1, "x")]`, `dedupe_first` returns `[(2, "y"), (5, "x")]`; `dedupe_latest` returns the same values because timestamp `5` is the latest `x`. ## Clarifications Arbitrarily late events mean a streaming result is only the smallest value known now, not a globally final ordering. State what watermark or maximum-lateness contract would be needed for final ordered output. ## Hints A map stores the authoritative version for each message; a min-heap can contain candidates that are checked lazily when popped. ## Extensions - Expire deduplication state after a fixed window. - Compact a heap whose stale entries grow too large. - Partition the stream while routing equal messages consistently.