Hash mapseasyInsertion-ordered count map3 min · 74 of 290

The badge scanned once

Find the first badge scanned exactly once with a single pass, using the count map itself to remember arrival order.

A door reader writes one line per entry and never rewinds. Security wants the first badge in the day's log that was used once and never again.

The problem

A conference door reader appends a badge ID to its log every time someone walks in, in arrival order. Most attendees come and go several times, so their badge appears many times. Security wants the earliest badge in the log that appears exactly once across the whole day.

"Earliest" means where the badge first shows up, and the count is over the whole day, not just the part read so far. The log is a one-way feed: it can be walked from start to end once, with no way back to a line already passed.

Input. scans — a list of badge ID strings, in scan order.

Output. The first badge ID that appears exactly once in scans, or None when every badge was scanned more than once.

Example.

scans = ["G14", "B02", "G14", "T77", "B02", "M31"]   ->  "T77"

G14 and B02 were scanned twice each. T77 and M31 were scanned once each, and T77 arrived first.

A second example, which rules out answering as you read:

scans = ["Q30", "Q30", "L82", "D19", "L82", "L82"]   ->  "D19"

L82 arrives before D19 and looks like a fresh badge at the time. Only the rest of the log reveals it was scanned three times.

Constraints.

  • 0 <= len(scans) <= 10^6
  • Each badge ID is a non-empty string of at most 12 characters.
  • The log may be walked only once.

Hints

Hint 1

You cannot return to the start, so whatever you carry forward must be enough to answer at the end. What is the smallest such thing?

Hint 2

Counts alone do not answer it — "first" is a question about order. Where is arrival order already recorded, without you storing an index?

Hint 3

A badge's entry in the map is created at its first scan and never created again. Walking the map is walking first-arrival order.

Approach

Brute force

For each entry, walk the whole log counting how often that badge appears, and return the first entry whose count is 1. That is n^2 comparisons — 10^12 for a million scans — and it rewinds the feed n times, which the reader forbids.

The insight

One pass fills a map from badge to count, and because a key is created at its first scan and never re-created, the map's own key order is arrival order — so the answer is the first key with a count of 1.

The precondition is that the map preserves insertion order, which Python guarantees for dict and which is exactly what "first" needs. Insertion happens once per distinct badge, at the moment it first appears, so the map is both the tally and the order — and it holds one entry per attendee, not one per scan. In a language with no ordering guarantee, store first_index beside the count and take the smallest index among the counts of 1, still in one pass.

Algorithm

  1. Start an empty map from badge to count.
  2. For each badge in the log, increment its count, creating the key if new.
  3. Walk the map's keys in insertion order.
  4. Return the first key whose count is 1, or None if there is none.

Complexity

Time O(n) — one hash per scan, then one walk of at most n distinct keys. Space O(d), where d is the number of attendees rather than of entries.

Solution

Python 3 · standard library13 lines · 7 test cases, all passing
"""Badge scan loner — one pass into an insertion-ordered count map."""


def solve(scans):
    tally = {}
    for badge in scans:
        # invariant: a badge's key is created at its FIRST scan, and Python keeps
        # keys in creation order, so walking `tally` later walks arrival order.
        tally[badge] = tally.get(badge, 0) + 1
    for badge, times in tally.items():
        if times == 1:
            return badge
    return None
The cases that ran
TESTS = [
    ((["G14", "B02", "G14", "T77", "B02", "M31"],), "T77"),
    ((["Q30", "Q30", "L82", "D19", "L82", "L82"],), "D19"),
    ((["A05", "A05", "K19", "K19"],), None),
    ((["Z01"],), "Z01"),
    (([],), None),
    ((["R7", "R7", "R7", "S2"],), "S2"),
    ((["N4", "P8", "P8", "N4", "C1"],), "C1"),
]

Pitfalls

  • Returning the first badge you have not seen before. That fires on G14 in the first example, which is scanned again two lines later. Nothing can be decided until the log ends.
  • Keeping a set of "seen once" and discarding on a repeat. The set ends up holding T77 and M31 in the first example, and a set has no order, so which one comes out is arbitrary.
  • Overwriting the count instead of incrementing it. Assigning tally[badge] = 1 on every scan makes every badge look like a singleton and returns G14. Signalling "not found" with "" has the same flavour of bug — it is a value a badge ID could take, and None is not.

Variants