Coding interviews
Reveal answer and reasoning
Find the first value that occurs exactly once, returning a nullable integer when no such value exists. The main learning objective is testing: compare an optimized count-map implementation with an independently structured nested-loop oracle. A small specified integer generator supplies reproducible cases without assuming that framework random sequences are stable across all runtime versions. The oracle and optimized method share a public contract but use different control structures.
One counts every candidate through nested loops; the other builds a frequency map and makes a second ordered pass. This reduces the chance that a copied indexing mistake or selection shortcut appears identically in both implementations.
Fast uses expected O(n) time and O(u) stored counts. Oracle can take O(n squared) time but requires constant auxiliary state. The slow method is intentionally retained only for small verification inputs, where simplicity and independence can be more valuable than speed. Because lengths remain at most twelve, the intentionally quadratic oracle is cheap enough for this bounded harness. Generated-case count and input bounds should be included in the test report.
A passing count alone does not describe which contracts were tested or imply coverage of every integer value and array length.
What a strong answer covers
- Find the first value that occurs exactly once, returning a nullable integer when no such value exists.
- The generator is a specified unchecked unsigned recurrence, followed by modulo five and a shift into the small signed domain.
- Fast uses expected O(n) time and O(u) stored counts.
Common pitfall
Two implementations sharing the same mistaken selection rule can agree while both are wrong. Generated tests therefore complement explicit examples such as empty input, all duplicates and a unique negative value. Passing two hundred cases is bounded evidence, not an exhaustive proof or a benchmark.
Follow-up questions
- Deliberately change Fast to return the smallest unique value and add a fixture whose first unique value is larger. Hint: the oracle must preserve the stated first-occurrence contract, not just membership in the set of unique values.
- What additional mechanism would turn this deterministic generator into a test system with shrinking?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.