Set (Set ADT) — Interview Preparation¶

Junior Questions¶

Middle Questions¶

Senior Questions¶

Coding Challenge (3 Languages)¶

Challenge: Intersection of Two Arrays in O(n + m)¶

Given two integer arrays a and b, return the elements present in both, each appearing once. Order does not matter.

Example: a = [1, 2, 2, 3, 4], b = [2, 3, 3, 5] → [2, 3].

Approach: Build a HashSet from the smaller array. Walk the larger array, adding each member of both into a result set. The result set automatically deduplicates. Time: O(n + m). Space: O(min(n, m)).

Go¶

package main

import "fmt"

func intersection(a, b []int) []int {
    // Choose smaller array as the lookup set.
    small, large := a, b
    if len(b) < len(a) {
        small, large = b, a
    }

    seen := make(map[int]struct{}, len(small))
    for _, x := range small {
        seen[x] = struct{}{}
    }

    result := make(map[int]struct{})
    for _, x := range large {
        if _, ok := seen[x]; ok {
            result[x] = struct{}{}
        }
    }

    out := make([]int, 0, len(result))
    for x := range result {
        out = append(out, x)
    }
    return out
}

func main() {
    a := []int{1, 2, 2, 3, 4}
    b := []int{2, 3, 3, 5}
    fmt.Println(intersection(a, b)) // some order of [2 3]
}

Java¶

import java.util.*;

public class Intersection {
    public static int[] intersection(int[] a, int[] b) {
        int[] small = a, large = b;
        if (b.length < a.length) { small = b; large = a; }

        Set<Integer> seen = new HashSet<>(small.length);
        for (int x : small) seen.add(x);

        Set<Integer> result = new HashSet<>();
        for (int x : large) {
            if (seen.contains(x)) result.add(x);
        }

        int[] out = new int[result.size()];
        int i = 0;
        for (int x : result) out[i++] = x;
        return out;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 2, 3, 4};
        int[] b = {2, 3, 3, 5};
        System.out.println(Arrays.toString(intersection(a, b)));
    }
}

Python¶

def intersection(a: list[int], b: list[int]) -> list[int]:
    small, large = (a, b) if len(a) <= len(b) else (b, a)
    seen = set(small)
    return list({x for x in large if x in seen})


if __name__ == "__main__":
    print(intersection([1, 2, 2, 3, 4], [2, 3, 3, 5]))  # e.g. [2, 3]

Variations to Discuss¶

• Preserve order: walk the larger array and emit each new match into an order-preserving structure.
• Sorted inputs: switch to two-pointer merge for O(n + m) time and O(1) extra space.
• Streaming: build the set from the bounded side and probe the stream — O(min(n, m)) memory.
• Approximate: replace the seen-set with a Bloom filter for huge inputs; accept rare false-positive matches.
• Multiset semantics (count duplicates): use frequency maps instead of sets.

A senior interviewer often pushes from the base problem into these variations — be ready to switch strategies when the input shape changes.

Behavioral and Whiteboard Tips¶

Common Wrong Answers (and Why They Fail)¶

Quick-Recall Set Identities (Often Asked)¶

|A ∪ B|  =  |A| + |B| - |A ∩ B|                          (inclusion-exclusion)
|A △ B|  =  |A ∪ B| - |A ∩ B|  =  |A| + |B| - 2|A ∩ B|
A \ B    =  A ∩ B^c                                       (de Morgan)
(A ∪ B)^c =  A^c ∩ B^c                                    (de Morgan)
A ⊆ B    ↔  A ∩ B = A   ↔   A ∪ B = B
A and B disjoint ↔  A ∩ B = ∅   ↔   |A ∪ B| = |A| + |B|

These show up in subtle whiteboard problems — "count elements seen exactly once across two streams" reduces to |A △ B|, which can be computed in one pass with a single counter using inclusion-exclusion.