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

Hiring now

Get the Goldman Sachs interview, not just the prep

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Or practice this question first

Next question