Implement anagram check and stable deduplication
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Part A — Anagram checker:
Write a function is_anagram(a: str, b: str, locale: str = 'en') -> bool that returns True iff a and b are anagrams under the following rules:
- Ignore case, whitespace, and Unicode punctuation.
- Normalize Unicode using NFKD; when locale='en', strip combining marks so accented letters compare equal to their base letters (e.g., 'é' -> 'e').
- Consider only letters and digits after normalization.
- Must work for inputs up to 10^7 characters each with O(σ) additional memory where σ is the alphabet size under the rules above, and O(n) time. Streaming solutions that do a single pass over each string are preferred; do not materialize full normalized strings.
- Return False immediately if, after filtering, the multiset lengths differ.
Follow-ups:
1) How would you adapt it to be locale-aware where 'ß' in German equals 'ss'? 2) How to handle right-to-left scripts without breaking normalization?
Part B — Stable de-duplication:
Write a function unique_stable(iterable, key=None, treat_nan_as_equal=False) that returns a lazy generator yielding the first occurrence of each distinct element while preserving original order.
- If key is None, distinctness is by the element itself (assume elements are hashable). If key is provided, distinctness is by key(x).
- If treat_nan_as_equal=True, treat all NaN floats as equal for distinctness even though NaN != NaN in Python.
- Target O(n) time and O(m) space where m is the number of distinct keys seen. The implementation must be lazy (streaming) over the input and must not sort.
Provide tight big-O bounds, and brief tests covering edge cases like empty input, all-duplicates, Unicode strings, very large inputs, and NaN handling.
Quick Answer: This question evaluates streaming algorithm design, Unicode normalization and locale-aware text processing, multiset frequency counting under tight time and memory bounds for an anagram checker, and stable, order-preserving deduplication with custom keys and NaN handling; it is in the Coding & Algorithms domain for a Data Scientist position.
Unicode-aware anagram checker
Write `is_anagram(a, b, locale='en')` returning True iff `a` and `b` are anagrams under these rules:
- Ignore case, whitespace, and Unicode punctuation.
- Normalize text using Unicode NFKD; when `locale='en'`, strip combining marks so accented letters compare equal to their base letters (e.g. 'é' → 'e').
- Consider only letters and digits after normalization.
- Return False immediately if, after filtering, the two multisets have different total lengths.
The intended solution streams over each string in a single pass and keeps only an O(σ) frequency map (σ = alphabet size under the rules), never materializing a fully normalized copy — giving O(n) time and O(σ) extra memory, suitable for inputs up to 10^7 characters.
Follow-ups to discuss: (1) make it locale-aware so German 'ß' equals 'ss'; (2) handle right-to-left scripts without breaking normalization (order is irrelevant to a multiset, so the count-based approach is RTL-safe once normalization is applied per code point).
Constraints
- 0 <= len(a), len(b) <= 10^7
- Inputs may contain arbitrary Unicode (letters, digits, punctuation, whitespace, accents).
- Comparison is case-insensitive and ignores whitespace and punctuation.
- NFKD normalization is applied; with locale='en', combining marks are stripped.
- Return False as soon as the post-filter multiset lengths differ.
Examples
Input: ('listen', 'silent')
Expected Output: True
Explanation: Classic anagram — same letters rearranged.
Input: ('Dormitory', 'Dirty Room!')
Expected Output: True
Explanation: Case-insensitive; whitespace and the '!' punctuation are ignored, leaving identical letter multisets.
Hints
- An anagram check is a multiset-equality check: count characters, don't sort. Sorting is O(n log n); counting is O(n).
- Normalize and filter each code point as you read it, so you never hold a fully normalized copy of a 10^7-char string in memory.
- For locale='en', NFKD splits 'é' into 'e' + a combining accent; unicodedata.combining() lets you drop the accent and keep the base letter.
- Short-circuit: if the two filtered totals differ, the strings cannot be anagrams — return False immediately.
Stable de-duplication (order-preserving unique)
Write `unique_stable(iterable, key=None, treat_nan_as_equal=False)` that lazily yields the first occurrence of each distinct element while preserving original order.
- If `key is None`, distinctness is by the element itself (elements are hashable). If `key` is provided, distinctness is by `key(x)`.
- If `treat_nan_as_equal=True`, treat all NaN floats as equal for distinctness (even though `NaN != NaN` in Python), so only the first NaN survives.
- Must be lazy/streaming over the input and must not sort.
Target O(n) time and O(m) space, where m is the number of distinct keys seen.
Note on this console: the reference solution below materializes the result into a list and exposes `treat_nan_as_equal` so it can be graded by the harness. The production version would `yield` instead of building `out`, making it a true lazy generator; switching `out.append(x)` to `yield x` (and dropping the final `return out`) is the only change needed.
Constraints
- Elements (or their keys when key is provided) are hashable.
- Order of first occurrence must be preserved exactly.
- Must be lazy/streaming over the input — no sorting and no buffering of the whole input beyond the seen-keys set.
- With treat_nan_as_equal=True, all NaN floats collapse to a single representative (the first one seen).
- Note: in Python, True == 1 and False == 0 hash-collide, so they are treated as duplicates of each other.
Examples
Input: ([1, 2, 2, 3, 1, 4],)
Expected Output: [1, 2, 3, 4]
Explanation: First occurrences kept in order; later repeats of 2 and 1 are dropped.
Input: ([],)
Expected Output: []
Explanation: Empty input yields nothing.
Hints
- Keep a set of keys you have already emitted; emit an element only the first time its key is unseen.
- Do not sort — sorting destroys 'first occurrence' order and costs O(n log n); a hash set gives O(n).
- NaN is its own trap: `float('nan') != float('nan')`, so a plain set would keep every NaN. Special-case NaN with a single boolean flag when treat_nan_as_equal=True.
- Watch the bool/int collision: 0 and False (and 1 and True) are equal and hash the same, so the second of each pair is dropped as a duplicate.