MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 3 – Arrays and hashing

Knowing what to track in one pass

After every character of a stream, report the first one seen exactly once so far, and learn to choose the state a one-pass loop must keep.

  • Intermediate
  • 20 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0 and quickjs 0.32.0
  • By MySmartCoPilot
Free: The problem: the letter sent only once. With a pass: the other 9 sections and 3 interview answers, about 16 minutes.

What you will learn

  • Decide which summary state (counts, first index, last index, running best) answers a query in one pass
  • Report the first value seen exactly once after every arrival in O(n) total time
  • Check a bijection with two maps, and show the input that fools a single map
  • Use first- and last-occurrence tables to answer questions about distances and spans

Before you start

What you’ll learn · Before you start

What you will learn

  • Decide which summary state (counts, first index, last index, running best) answers a query in one pass
  • Report the first value seen exactly once after every arrival in O(n) total time
  • Check a bijection with two maps, and show the input that fools a single map
  • Use first- and last-occurrence tables to answer questions about distances and spans

Before you start

On this page

After every message of the stream zxzyx, a quiz screen must show the earliest letter sent exactly once so far: z z x x y. Knowing what to track means deciding, before you write the loop, what a single pass must remember about the items it has already read, so that it can answer for the current item at once. The answer is usually a small table: a count for each value, the first or last position of each value, or one running best, and choosing it is most of the algorithm. With the right state the screen costs a few steps per character; without it, a scan of everything read so far.

The problem: the letter sent only once

The problem

A radio quiz takes answers by text message, one lowercase letter per message. After every message, the studio screen shows a letter that has arrived in exactly one message so far, the earliest such letter if there are several, or # when every letter so far has arrived at least twice. Given the messages in the order they arrive, return what the screen shows after each one.

Constraints: up to 2 × 10⁵ messages, each a letter from a to z; the screen must change before the next message.

Messages so far Sent once Screen
z z z
zx z, x z
zxz x x
zxzy x, y x
zxzyx y y

So zxzyx gives z z x x y, aabb gives a # b #, and q gives q.

The brute force: counts and a scan from the start

Keep a count for each letter and, after every message, scan the messages from the first one until a letter with a count of 1 turns up. The counts cost O(1) per message, but the scan may read every message so far:

Counts and a scan from the start after every message Python · brute/brute.py 
"""The screen after every message, by brute force: keep counts, then scan the messages from the start each time."""
import random


def screen_brute(messages):
    """For each prefix, the earliest letter sent exactly once so far, or '#'. Also returns the letters scanned."""
    counts, shown, scanned = {}, [], 0
    for k, letter in enumerate(messages):
        counts[letter] = counts.get(letter, 0) + 1
        answer = "#"
        for earlier in messages[: k + 1]:  # every message so far, oldest first
            scanned += 1
            if counts[earlier] == 1:
                answer = earlier
                break
        shown.append(answer)
    return " ".join(shown), scanned


for messages in ("zxzyx", "aabb", "q"):
    print(f"{messages} -> {screen_brute(messages)[0]}")

rng = random.Random(26)
for n in (1_000, 2_000, 4_000):
    messages = "".join(rng.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(n))
    print(f"n = {n:,}: {screen_brute(messages)[1]:,} letters scanned")

Output

zxzyx -> z z x x y
aabb -> a # b #
q -> q
n = 1,000: 492,532 letters scanned
n = 2,000: 1,993,561 letters scanned
n = 4,000: 7,995,121 letters scanned

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 brute.py

The scans add up to about n²/2 letters: 7,995,121 for 4,000 random messages, four times as many for each doubling. For 200,000 messages that is about 2 × 10¹⁰ letters, far more than any time limit allows, and recounting every prefix from scratch would be worse still, O(n³). Step through the rescans on zxzyx:

Interactive · step by step Rescanning the messages of zxzyx after each one Step through the five messages. After each one the scan starts again at the first message; the narration counts the letters it reads.
Rescanning the messages of zxzyx after each one, step 6 of 6. Showing message 1: z, message 2: x, message 3: z, message 4: y, message 5: x, screen after 1 (z, after 1 read), screen after 2 (z, after 1 read), screen after 3 (x, after 2 reads), screen after 4 (x, after 2 reads), screen after 5 (y, after 4 reads). In focus: screen after 1, screen after 2, screen after 3, screen after 4, screen after 5.message 1: zmessage 2: xmessage 3: zmessage 4: ymessage 5: xscreen after 1z, after 1 readscreen after 2z, after 1 readscreen after 3x, after 2 readsscreen after 4x, after 2 readsscreen after 5y, after 4 reads

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text
  1. After z. z has been sent once. The scan reads message 1, z, whose count is 1, so the screen shows z after 1 letter read.
  2. After x. The scan starts again at message 1. z is still sent once, so the screen shows z. 2 letters read so far.
  3. After the second z. z has now been sent twice. The scan passes it and finds x at message 2. 4 letters read so far.
  4. After y. The scan passes z again and stops at x, still sent once. 6 letters read so far.
  5. After the second x. z, x and z are passed, and y at message 4 is the earliest letter sent once. 10 letters read in all.
  6. Why it is slow. Every message starts a new scan from the first one, so the scans add up to about n²/2 letters, 7,995,121 for 4,000 random messages in the recorded run.

What to notice

The answer depends on only two facts about the past, how often each letter has been sent and the order in which letters were first sent. A count never goes down, so a letter sent twice can never be the answer again, and the answer only moves forward along the letters in order of first arrival, as the screen column of the table shows: z, then x, then y. A queue of candidates keeps letters in that order and drops a letter from its front once it has been sent twice. An insertion order: The order in which keys were first added to a map. Python's dict, JavaScript's Map and Java's LinkedHashMap iterate in insertion order; a plain Java HashMap promises no order at all. map, such as Python’s dict or Java’s LinkedHashMap, can hold just the letters sent once. With only 26 letters, scanning 26 counters is a third way.

Checkpoint

Check: The earliest letter sent exactly once · Counts and a scan from the start, and its cost · What the past must tell the loop

  1. Question 1 of 3 What does the screen show after each message of aabb?

    Choose one answer.

    Show the answer

    Answer: a # b #

    The screen shows the earliest letter sent exactly once so far, or # when there is none: a, #, b, #.

  2. Question 2 of 3 How many letters does the brute force read in all on the stream zxzyx?

    Type a number.

    A hint

    Each scan starts at the first message and stops at the first letter sent once.

    Show the answer

    Answer: 10 letters

    The scans read 1, 1, 2, 2 and 4 letters, 10 in all, as the figure counts them.

  3. Question 3 of 3 Why can a letter that has been sent twice never be the answer again?

    Choose one answer.

    Show the answer

    Answer: Counts never go down, so its count can only stay above 1

    Because counts only grow, the answer only moves forward along the letters in the order of their first message.

The practice below starts with whatever you know least.

Practice that adapts to you

Practise this lesson

9 questions about 10 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 9 What does the studio screen show after a message?

    Choose one answer.

    Show the answer

    Answer: The earliest letter that has arrived in exactly one message so far, or # if there is none

    For zxzyx the screen shows z z x x y: the earliest letter sent once after each message.

  2. Question 2 of 9 After the first four messages of zxzyx, which letters have been sent exactly once?

    Choose one answer.

    Show the answer

    Answer: x and y, so the screen shows x

    The table of the problem shows x, y as the letters sent once after zxzy, and x on the screen.

  3. Question 3 of 9 A stream sends every letter of the alphabet twice, a b c … z a b c … z. What does the screen show after the 30th message?

    Choose one answer.

    Show the answer

    Answer: e

    After 30 messages, a to d have been sent twice and e to z once, so the earliest letter sent once is e.

  4. Question 4 of 9 What makes the brute force slow?

    Choose one answer.

    Show the answer

    Answer: After every message it scans the messages from the first one again

    The counts are cheap; the repeated scan from the start is what grows with n².

  5. Question 5 of 9 The brute force read 1,993,561 letters for 2,000 random messages. About how many for 4,000?

    Choose one answer.

    Show the answer

    Answer: About 8 million, four times as many

    Each doubling of the stream made about four times the reads in the run: 492,532, 1,993,561, 7,995,121.

  6. Question 6 of 9 For 200,000 messages the scans read about 2 × 10¹⁰ letters. With about 10⁷ simple steps a second in CPython, what does that mean?

    Choose one answer.

    Show the answer

    Answer: About 2,000 seconds, far beyond a limit of a second or two

    The brute force cannot keep the screen up to date at this size, so the loop must remember more about the past.

  7. Question 7 of 9 Which two facts about the past does the answer depend on?

    Choose one answer.

    Show the answer

    Answer: How often each letter has been sent, and the order in which letters were first sent

    A count per letter and the order of first arrival hold everything the screen needs.

  8. Question 8 of 9 With only 26 letters, which way of answering needs no queue at all?

    Choose one answer.

    Show the answer

    Answer: Scanning the 26 counters in the order of first arrival after each message

    With 26 letters a scan of the counters is a third way; with arbitrary values it is not.

  9. Question 9 of 9 The values are ticket numbers up to 10⁹ instead of letters. Which of these still works?

    Choose one answer.

    Show the answer

    Answer: A queue of candidates with counts in a map

    The queue relies only on counts never falling and on the order of first arrival, not on the alphabet.

Counts and a queue of candidates, step by step Pro

In this part:

  • A dry run on zxzyx
  • Why it is correct and O(n), with the work measured
  • The same screen in 14 languages
  • An ordered map instead of a queue, and where it slows down
  • Choosing the state for other one-pass questions
    • Two maps for a bijection, and the input that fools one
  • Edge cases, tests and variants
    • Edge cases and the tests that catch them
    • Variants
  • Practice: the first ticket read once
    • The first value seen once, after every arrival
  • Interview questions
    • Before you write a one-pass loop over an array or a stream, how do you decide what state to keep?
    • A gate scanner streams ticket IDs, up to 10⁷ arrivals and 10⁶ distinct IDs, and a dashboard must show after each arrival the earliest ID read exactly once so far. What state do you keep, how much memory does it need, and which structures in your language keep the work per arrival constant?
    • A function checks whether a pattern such as abba matches a sentence such as red blue blue red, one word per letter. It keeps one dictionary from letters to words and passes every test the team wrote. Which input breaks it, how do you fix it, and how would you have found it without guessing?
    • The radio screen now counts only the last k messages: after every message it shows the earliest letter sent exactly once within the last k messages, or #. Why does the queue of candidates stop working, and what do you use instead, for letters and for arbitrary IDs?
  • Key takeaways

1 diagram · 7 runnable examples (JavaScript, Python) · 1 exercise with sample tests · 3 interview answers · about 40 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

bijection
A pairing in which every item on one side goes with exactly one item on the other side, and the other way round, such as the letters of a pattern and the words of a sentence that matches it.
insertion order
The order in which keys were first added to a map. Python's dict, JavaScript's Map and Java's LinkedHashMap iterate in insertion order; a plain Java HashMap promises no order at all.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. JavaScript & TypeScript Online Compiler Write, run and debug JS or TS snippets — safely sandboxed, nothing to install.

Report a problem with this lesson