# Deduplicate and Order Batch and Streaming Logs Each log entry is a pair `(timestamp, message)`. Two entries are duplicates when their message strings are equal. Timestamps are integers and input order is not guaranteed to match timestamp order. ### Clarifying Questions to Ask - How should equal timestamps be ordered? - Is message equality byte-for-byte, case-insensitive, or normalized? - Can an entry be corrected or retracted? - For a stream, when is it safe to claim that the next result is final? ### Part 1: Keep the First Encountered Duplicate Given the complete list, retain the first occurrence encountered in input order for each message, regardless of whether a later duplicate has a smaller timestamp. Then return the retained entries from earliest to latest. Define a deterministic tie rule and analyze complexity. #### What This Part Should Cover - A map keyed by exact message identity - Correct preservation of the first input occurrence even when timestamps are unsorted - Deterministic output ordering - Time and memory complexity ### Part 2: Keep the Latest Duplicate Change the rule so each message retains its greatest timestamp. Explain what changes and identify edge cases that should be tested. #### What This Part Should Cover - A safe replacement rule for the retained timestamp - The unchanged need for final ordering - Empty input, repeated identical entries, and timestamp ties ### Part 3: Process an Online Stream Logs now arrive individually. Support `add(timestamp, message)` and `get_next()`, which returns the smallest-timestamp currently available retained entry. First discuss the keep-first rule, then extend it to keep-latest using lazy deletion. State the semantic limitation when late events are allowed. #### What This Part Should Cover - A membership or latest-value map plus a min-heap - Recognition and removal of stale heap entries - Heap growth, compaction, and amortized complexity - Watermarks or lateness bounds for globally final ordering ### What a Strong Answer Covers - Explicit batch and streaming contracts rather than assuming arrival order - Correct deduplication state and deterministic tie behavior - Lazy-deletion invariants and bounded-state considerations - Honest discussion of out-of-order events and finality ### Follow-up Questions - How would you expire deduplication state after a time window? - How would you shard the stream while preserving per-message correctness? - What changes if consumers require exactly-once output? - When should a stale-entry heap be rebuilt?