How does Interview Prep handle hash set?

Interview Prep covers this with 2 copy-ready snippets on this page. The "Finding Duplicates" snippet in Interview Prep uses `Approach 1: Hash set - O(n) time, O(n) space`.

Which code does the Interview Prep example use?

The "Finding Duplicates" snippet uses `Approach 1: Hash set - O(n) time, O(n) space`, from the Arrays & Strings section of the Interview Prep cheat sheet.

What other Interview Prep snippets are shown for "hash set"?

Besides "Finding Duplicates", this page also shows "Intersection of Collections".

Hash set

2 snippets in Interview Prep

DSAInterview Prep

Finding Duplicates

DSA · Arrays & Strings

Syntax

Approach 1: Hash set - O(n) time, O(n) space
Approach 2: Sort first - O(n log n) time, O(1) space
Approach 3: Floyd's cycle (special constraints) - O(n) time, O(1) space

Example

// JavaScript - Hash set approach
function containsDuplicate(arr) {
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return true;
    seen.add(val);
  }
  return false;
}

function findDuplicate(arr) {
  // Values in range [1, n], exactly one duplicate
  const seen = new Set();
  for (const val of arr) {
    if (seen.has(val)) return val;
    seen.add(val);
  }
}

# Python
def contains_duplicate(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return True
        seen.add(val)
    return False

def find_duplicate(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return val
        seen.add(val)

Output

contains_duplicate([1,2,3,1]) → True
find_duplicate([1,3,4,2,2]) → 2

Note The hash set approach is the go-to. If asked for O(1) space with values in [1,n], use Floyd's tortoise and hare or index marking (negate values). Always clarify constraints: can you modify the input? What is the value range?

Intersection of Collections

DSA · Hash Maps & Sets

Syntax

Convert one collection to a set, iterate the other and check membership.
For sorted arrays: use two pointers instead.

Example

// JavaScript
function intersection(arr1, arr2) {
  const set1 = new Set(arr1);
  const result = [];
  const seen = new Set();
  for (const val of arr2) {
    if (set1.has(val) && !seen.has(val)) {
      result.push(val);
      seen.add(val);
    }
  }
  return result;
}

# Python
def intersection(arr1, arr2):
    return list(set(arr1) & set(arr2))

# With duplicates preserved:
def intersect_with_dupes(arr1, arr2):
    from collections import Counter
    c1, c2 = Counter(arr1), Counter(arr2)
    return list((c1 & c2).elements())

Output

intersection([1,2,2,1], [2,2]) → [2]
intersect_with_dupes([1,2,2,1], [2,2]) → [2, 2]

Note Set approach: O(n + m) time, O(min(n,m)) space. Sorted two-pointer approach: O(n log n + m log m) time, O(1) extra space. Ask the interviewer: unique results or preserve duplicates? Are inputs sorted?

Frequently asked questions

How does Interview Prep handle hash set?: Interview Prep covers this with 2 copy-ready snippets on this page. The "Finding Duplicates" snippet in Interview Prep uses `Approach 1: Hash set - O(n) time, O(n) space`.
Which code does the Interview Prep example use?: The "Finding Duplicates" snippet uses `Approach 1: Hash set - O(n) time, O(n) space`, from the Arrays & Strings section of the Interview Prep cheat sheet.
What other Interview Prep snippets are shown for "hash set"?: Besides "Finding Duplicates", this page also shows "Intersection of Collections".
Is there anything to watch out for?: Yes. For "Finding Duplicates": The hash set approach is the go-to. If asked for O(1) space with values in [1,n], use Floyd's tortoise and hare or index marking (negate values). Always clarify constraints: can you modify the input? What is the value range?