hims & hers·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Coding round at hims & hers with a classic array problem that has a neat in-place trick most people either know or don't.

Questions Asked (1)

Given an integer array of length n where every value is between 1 and n and each value appears once or twice, find all the duplicates. Must run in O(n) time with constant extra space.

Algorithms & Data Structures

Author's notes

I knew this one but blanked on articulating why the negation trick works under the space constraint.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use the array itself as a hash table by marking visited indices through sign flipping or value negation. Iterate through the array, and for each value, treat its absolute value minus one as an index; if the value at that index is already negative, the current value is a duplicate. Otherwise, negate the value at that index to mark it as seen.

Pro tip: Clarify upfront that the input array is mutable and that modifying it is acceptable; if not, mention that the problem requires a different approach or additional space. Also, handle edge cases like n=0 or n=1 explicitly.

1. Understand constraints and clarify assumptions

Confirm that the array can be modified in-place and that values are 1-indexed. Discuss time and space complexity requirements.

2. Choose in-place marking technique

Decide between sign flipping (negation) or adding n to visited indices. Sign flipping is simpler but fails if zeros are present; here values are 1..n, so it's safe.

3. Iterate and mark visited indices

For each element, compute index = abs(value) - 1. If array[index] is negative, record abs(value) as duplicate. Else, negate array[index].

4. Collect duplicates and restore array (optional)

After the pass, the duplicates list is complete. If the array must be restored, do a second pass to take absolute values.

5. Analyze complexity and edge cases

State O(n) time and O(1) extra space (excluding output). Discuss edge cases: no duplicates, all duplicates, n=0, n=1.

Key Points to Mention

In-place modification using the array as a hash map
Sign flipping technique to mark visited indices
Time complexity O(n) with a single pass (or two passes for restoration)
Constant extra space O(1) excluding the output list
Handling of edge cases such as empty array or single element
Clarifying that the input array is mutable and values are within 1..n

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.