coding challenges · medium

First Duplicate Order ID in a Stream

Asked at MCX India: given a stream of order IDs, return the first one that repeats. Scan once into an unordered_set; std::unordered_set::insert returns {iterator, inserted}, and the first time .second is false you've found an ID seen before — return it. O(n) time, O(n) space. For {101,203,101,305,203} the answer is 101 (its second copy appears before 203 repeats). Follow-ups: first NON-repeating element (count occurrences, then re-scan for the first with count 1) and, when IDs are bounded to 1..n, the index-sign in-place trick for O(1) extra space.

The code

#include <vector>
#include <unordered_set>
#include <cstdio>

// First value that appears twice while scanning the stream: a hash set, O(n).
int firstDuplicate(const std::vector<int>& ids) {
    std::unordered_set<int> seen;
    for (int id : ids)
        if (!seen.insert(id).second) // insert fails -> already seen
            return id;
    return -1; // no duplicate
}

int main() {
    std::vector<int> ids = {101, 203, 101, 305, 203};
    printf("%d\n", firstDuplicate(ids)); // 101
}

What this lesson walks through

1. 01Remember everything you've seen
2. 02101 — first time seen
3. 03203 — first time seen
4. 04101 again → insert FAILS
5. 05Complexity & follow-ups

Scan the stream once, inserting each id into a hash set. insert returns {iterator, inserted?}; the first time inserted is false, you've found an id seen before.