Spot the first repeated badge at the door

Arrays, strings and hash maps Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
seen: set[int] = set()
out = -1
for b in [4, 9, 2, 9, 4]:
    if b in seen:
        out = b
        break
    seen.add(b)
print(out)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 9

Right: 9 is the first value that is already in the set when it comes round again.

The scan stops at index 3, the earliest second sighting, so later repeats never matter.

Why not the others?
  • B 4. 4 repeats too, but its second sighting comes after 9's.
  • C -1. The loop finds a repeat, so out is overwritten before the loop ends.

30-second answer

Walk the log once and keep a set of badges already seen. The first badge that is already in the set is the answer. Each check and insert is O(1) on average, so the whole scan is O(n) time and O(n) extra space, against O(n²) for comparing every pair.

Practise saying it · 45 s. No recording, just a timer

Explain how you find the first repeated badge and what it costs.

Say your answer out loud, then check which of these points you covered:

  • Set of seen values, one pass
  • O(n) time, O(n) space
  • Mentions the O(n²) brute force

Deep dive

A set answers 'have I seen this?' by hashing the value to a bucket, so the cost does not grow with the log length on average.

Return as soon as you find the repeat: 'first to repeat' means the earliest second sighting, which is exactly the first hit in a left-to-right scan.

If memory is tight and the log may be reordered, sorting and comparing neighbours uses O(1) extra space but costs O(n log n) and loses the original order.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def first_repeat(badges: list[int]) -> int:
    seen: set[int] = set()
    for b in badges:
        if b in seen:
            return b
        seen.add(b)
    return -1

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun firstRepeat(badges: List<Int>): Int {
    val seen = HashSet<Int>()
    for (b in badges) {
        if (!seen.add(b)) return b
    }
    return -1
}

Common mistakes

  • Checking b in badges[:i]: that rescans the prefix every time and is O(n²).
  • Returning the value that repeats most often, or the first value that has any repeat later, which are different questions.

Senior take & follow-ups

Say the brute force and its cost first, then the set. Interviewers listen for the trade: O(n) extra memory buys the drop from O(n²) to O(n).

Follow-up questions

Think of your answer first, then open the hint.

  1. What if the badges are numbers from 0 to n-1?

    Show hint

    You can mark seen values in a list of booleans instead of a set: same O(n), smaller constant.

  2. What changes for a stream that never ends?

    Show hint

    Memory grows with distinct badges; a Bloom filter trades exactness for fixed memory.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.