Idempotent Event Stream
A producer pushes events onto a topic and occasionally retries them on transient errors. The consumer must process each logical event exactly once and preserve the original order of first occurrence for downstream replay.
Problem
Given an ordered list of events where each event has a string event_id and a string payload, return the de-duplicated list in the order each event_id first appeared. If the same event_id reappears with a different payload, keep the first payload (producer is the source of truth on first commit).
Input
An integer n (1 ≤ n ≤ 2·10^5) followed by n pairs (event_id, payload). event_id is up to 64 ASCII chars. payload is an opaque string up to 256 bytes.
Output
The de-duplicated list of (event_id, payload), preserving order of first occurrence.
Constraints
- 1 ≤ n ≤ 200,000
- Up to ~50% of events may be duplicates
- event_id is a unique business key (e.g. UUID); payload may legitimately differ on retries
- Memory budget: O(n)
Examples
Example 1
Input
5
evt-a {amount:10}
evt-b {amount:20}
evt-a {amount:10,retry:1}
evt-c {amount:30}
evt-b {amount:20}Output
evt-a {amount:10}
evt-b {amount:20}
evt-c {amount:30}evt-a's second occurrence is dropped (keep first payload). evt-b's duplicate is dropped. Order preserved.