Track Previously Seen Values

Practice Exercise Interview Easy Hashing

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement track_seen_values(values). Return a list of booleans with one entry per input value. An entry is True exactly when the same value appeared at an earlier index; the first occurrence of every value produces False.

Starter code

def track_seen_values(values):
    pass

Test cases

repeated-values

{
  "args": [
    [
      4,
      1,
      4,
      4,
      2,
      1
    ]
  ]
}

Expected: [false,false,true,true,false,true]

all-distinct

{
  "args": [
    [
      "a",
      "b",
      "c"
    ]
  ]
}

Expected: [false,false,false]

Wizard outline

Step 1: Create one output slot per input value
Establish the empty-result contract before tracking state. The function returns observations in input order, so the result list is the first independent piece of state.
Step 2: Mark first occurrences as unseen
Emit False while every processed value is distinct. This separates output length and order from duplicate detection.
Step 3: Detect an immediately repeated value
Compare the current value with the value at the previous index. An adjacent duplicate is the smallest case that proves a later occurrence must emit True.
Step 4: Track every earlier value
Replace the adjacency check with a hash-set membership check over the entire prefix. Non-adjacent duplicates require memory of every value seen so far, not only the previous value.

Footguns and prerequisites

Adding the current value before checking membership marks every position as already seen.
Scanning the entire prefix for each value changes the intended linear pass into quadratic work.
hashing and sets

Reviewed references

Python Set Types — set and frozenset

Prepared Interview Problems

Diagonal Traverse II(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing diagonal traverse two as a complete Interview Problem.
Group Words by Anagram Signature(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing group anagrams as a complete Interview Problem.
Longest Consecutive Sequence(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing longest consecutive sequence as a complete Interview Problem.
Two Sum(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing two sum as a complete Interview Problem.
Validate a Partial Sudoku(opens in a new tab)
Track Previously Seen Values isolates before processing index i, seen contains exactly the distinct values from indices smaller than i. That focused state discipline is required when implementing valid sudoku as a complete Interview Problem.

Recommended approach and implementation

Membership questions about everything processed so far usually call for a hash set rather than repeated prefix scans. Before processing index i, seen contains exactly the distinct values from indices smaller than i.

Why it works: Initially seen is empty, matching the empty prefix. Each value is tested before insertion, so a reported duplicate has an earlier occurrence; otherwise insertion preserves the invariant for the next index.

def track_seen_values(values):
    seen = set()
    result = []
    for value in values:
        result.append(value in seen)
        seen.add(value)
    return result