Match alphanumeric patterns in a stream
Company: Optiver
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given a reference 7–8 character alphanumeric code and four candidate codes, select the exact match as quickly as possible. Design a system that:
- Efficiently determines whether any candidate exactly matches the reference (consider case sensitivity and lookalike characters such as O/0 and I/
1).
- Supports a streaming setting where batches arrive at increasing rates and latency must remain low.
- Handles input noise (e.g., OCR errors) by optionally allowing a configurable Hamming distance threshold without compromising throughput.
Discuss your data structures (e.g., hashing, tries, SIMD-friendly encodings), algorithmic choices, complexity, and how you would benchmark and scale this for high QPS.
Quick Answer: This question evaluates skills in exact and approximate alphanumeric string matching, streaming pattern lookup, noise-tolerant comparison, and performance-oriented data structures and encodings.
You are building the matching core of a high-throughput stream processor at a trading firm. Each incoming batch contains a short alphanumeric reference code (typically 7-8 characters) and a list of candidate codes (e.g. captured via OCR). You must decide which candidates match the reference.
Implement a function `matchCandidates(reference, candidates, normalizeLookalikes, maxHammingDistance)` that returns the list of indices (in ascending order) of the candidates that match the reference, where a candidate matches if:
1. It has the **same length** as the reference (different lengths never match).
2. Its **Hamming distance** to the reference (number of positions at which the characters differ) is **at most** `maxHammingDistance`.
When `normalizeLookalikes` is true, before comparing you must canonicalize both the reference and each candidate as follows, in order:
- Convert every character to **uppercase** (so matching becomes case-insensitive).
- Map the digit `'0'` to the letter `'O'`.
- Map the digit `'1'` to the letter `'I'`.
When `normalizeLookalikes` is false, compare the strings exactly as given (case-sensitive, no lookalike folding).
Return the indices of all matching candidates in increasing order. Return an empty list if none match.
Constraints
- 1 <= len(reference) <= 64
- 0 <= len(candidates) <= 10^4
- Each candidate string has length 0 to 64
- Codes contain ASCII letters and digits only
- 0 <= maxHammingDistance <= len(reference)
- Indices in the result must be in strictly ascending order
Examples
Input: ('A1B2C3D', ['A1B2C3D', 'X9Y8Z7Q', 'A1B2C3X', 'A1B2C3D'], False, 0)
Expected Output: [0, 3]
Explanation: Exact match, no normalization, threshold 0. Indices 0 and 3 are identical to the reference; index 2 differs in the last char; index 1 is entirely different.
Input: ('A1B2C3D', ['AIB2C3D', 'A1B2C30', 'a1b2c3d', 'A1B2C3D'], True, 0)
Expected Output: [0, 2, 3]
Explanation: With normalization, reference canonicalizes to 'AIB2C3D'. Index 0 ('AIB2C3D') and index 3 already match; index 2 ('a1b2c3d' -> 'AIB2C3D') matches via case+1->I folding. Index 1 ('A1B2C30' -> 'AIB2C3O') differs in the last position, so it is excluded.
Hints
- Length is a cheap pre-filter: any candidate whose length differs from the reference can never match, regardless of the Hamming threshold.
- Do the lookalike/case canonicalization once per string up front, then compare canonical forms character by character.
- When counting differing positions, short-circuit as soon as the running count exceeds maxHammingDistance to stay fast on long batches.
- Order matters in the canonicalization: uppercase first (so '1'->I and '0'->O folding applies uniformly to lowercase input too).