Hash set

2 snippets in Interview Prep

DSAInterview Prep

Finding Duplicates

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?