Coding

Contains any Duplicates

Asked at

Goldman Sachs

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

Stuck? Show a way to structure it+

01Create an empty seen set.
02Scan each value once.
03Return true if it already exists.
04Otherwise add it.
05Mention sorting as a lower-space alternative.

Reference answer

Scan the array while maintaining a hash set of values already seen. Before inserting a value, test membership; if it is present, return true immediately because a duplicate has been found. If the scan finishes, all values were unique. This is the natural expected O(n)-time, O(n)-space solution. Explain that hash operations are expected constant time, not a worst-case mathematical guarantee. If modifying the array is allowed and memory is constrained, sort it and compare adjacent values instead; that costs O(n log n) time and can use O(1) or sorting-dependent extra space. Test an empty array, one value, and duplicates that appear far apart. Avoid nested pair comparisons, which are O(n squared) without need.

Then expect these follow-ups

How would you find the first duplicate by input order?
Tests: follow-up reasoning
What if values are bounded integers?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question