Deduplicating and Sorting Batch and Streaming Logs

Each log record is represented by (timestamp, message), where: timestamp is an integer; message is a string; logs may arrive in an order different from timestamp order; two logs are duplicates if their message values are exactly equal. For logs with equal timestamps, use their input arrival order as the deterministic tie-breaker. Part 1: Batch Processing — Keep the First Arrival Implement: dedup_keep_first(logs) -> list[tuple[int, str]] Scan logs in input order. For each message, retain only its first occurrence and ignore all subsequent occurrences, even if a later duplicate has an earlier timestamp. Return retained logs sorted by ascending timestamp; break equal-timestamp ties by original input order. Example: Input: [(5, "a"), (3, "b"), (1, "a"), (3, "c")] Output: [(3, "b"), (3, "c"), (5, "a")] Part 2: Batch Processing — Keep the Most Recent Entry Implement: dedup_keep_latest(logs) -> list[tuple[int, str]] For every message, retain the log with the largest timestamp. If multiple logs for the same message have the same maximum timestamp, retain the one that arrived last. Return retained logs sorted by ascending timestamp; break equal-timestamp ties by original input order. Example: Input: [(5, "a"), (3, "b"), (7, "a"), (3, "c"), (7, "a")] Output: [(3, "b"), (3, "c"), (7, "a")] Part 3: Streaming Processing Logs arrive one at a time. Implement: add(timestamp, message) -> None get_next() -> tuple[int, str] | None get_next() returns the valid retained log with the smallest timestamp currently available, or None if none is available. Design and implement both modes: Keep-first mode: accept the first log received for each message and ignore later duplicates. Keep-latest mode: retain the currently received log with the greatest timestamp for each message; for equal timestamps, retain the last arrival. You may use lazy deletion: old versions remain in a min-heap, and are discarded when popped if they no longer match the current latest version for that message. Explain time and space complexity. Also explain why, when arbitrarily late events are allowed, an emitted entry cannot be guaranteed to be the globally smallest timestamp in the final stream without a watermark or bounded-lateness guarantee. Example Input 1 4 5 a 3 b 1 a 3 c Output 3 b 3 c 5 a