← Hims & Hers Interview Insights

Hims & Hers·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Coding screen at hims & hers with a classic array problem. Nothing fancy, but the O(n) time plus constant space constraint is the part that trips people up if they haven't seen it before.

Questions Asked (1)

Q1

Given an integer array of length n where every value is between 1 and n and each value appears once or twice, find all values that appear twice. Your solution must run in O(n) time and use constant extra space.

Algorithms & Data Structures
Author's notes

The naive answer is a hashmap and they'll let you say it, but then they ask you to drop the extra space and that's where it gets interesting.

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. For each element, treat its value as an index and negate the value at that index; if it's already negative, the value is a duplicate. This achieves O(n) time and O(1) space without modifying the input permanently (or note that modification is acceptable).

Pro tip: Clarify whether the input can be modified; if not, propose an alternative like Floyd's cycle detection. Also, mention that the solution relies on values being in the range 1 to n, which is a key constraint.

1. Understand the constraints

Confirm that the array length is n, values are between 1 and n, and each value appears once or twice. This allows using values as indices.

2. Choose the marking technique

Decide to use the array itself to track seen numbers by negating the value at the index corresponding to the current number.

3. Iterate and mark

For each element, compute the index as abs(value) - 1. If the value at that index is negative, the number is a duplicate; otherwise, negate it.

4. Collect duplicates

When a duplicate is found, add the absolute value to the result list.

5. Restore array (optional)

If the problem requires the original array to be unchanged, iterate again and take absolute values to restore.

Key Points to Mention

  • Time complexity: O(n) because we iterate through the array once (or twice if restoring).
  • Space complexity: O(1) extra space, as we only use the input array for marking.
  • The technique of using the array as a hash map by negating values.
  • Handling edge cases: values that are already negative due to previous markings.
  • The importance of the constraint that values are in [1, n].
  • Potential need to restore the array if modification is not allowed.

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