What is the Union-Find data structure used for in interviews?

Union-Find (Disjoint Set Union) is used for connected components, cycle detection in undirected graphs, and grouping items dynamically. Classic problems: Number of Connected Components, Redundant Connection, Accounts Merge. With path compression and union by rank, operations run in near-O(1) amortized time.

When should I use a Trie instead of a HashMap?

Use a Trie when you need prefix-based operations: autocomplete, word search, prefix existence checks. A HashMap tells you if a complete word exists, but cannot efficiently answer 'how many words start with prefix X?' Tries solve prefix queries in O(prefix length) time.

What is Kadane's algorithm?

Kadane's algorithm finds the maximum sum contiguous subarray in O(n) time. At each element, the current subarray either extends (add current element) or restarts (start fresh). Track the global maximum throughout. Used in Maximum Subarray (LeetCode 53).

Essential Code Snippets 💎

The 12 most important algorithms and data structures you must know cold before any interview. Every snippet is correct, optimized, and shown in all three languages.

How to use this

Use the language tabs to switch between C++, Java, and Python. Memorize the patterns — not just the code. Understanding the why lets you adapt them on the fly.

1. GCD & LCM

Euclidean algorithm: gcd(a, b) = gcd(b, a % b), base case gcd(a, 0) = a. LCM = (a × b) / gcd(a, b). Always compute LCM this way to avoid overflow.

C++

// Recursive GCD — O(log(min(a,b)))
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Iterative GCD (avoids stack overhead)
int gcdIter(int a, int b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}

// LCM — divide first to prevent overflow
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

// C++17: std::gcd and std::lcm in <numeric>
// #include <numeric>
// int g = std::gcd(12, 8);  // 4
// int l = std::lcm(4, 6);   // 12

Java

static int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

static long lcm(long a, long b) {
    return a / gcd((int)a, (int)b) * b;
}

// Usage
gcd(12, 8);   // 4
lcm(4, 6);   // 12

Python

from math import gcd, lcm  # Python 3.5+ / 3.9+

# Manual implementations
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b  # // avoids float

gcd(12, 8)  # 4
lcm(4, 6)  # 12

2. Fast Power (Binary Exponentiation)

Compute aⁿ in O(log n) instead of O(n). Essential for modular exponentiation. Pattern: if exponent is odd → multiply result by base; always square base and halve exponent.

C++

// Fast power: a^n mod m — O(log n)
long long power(long long a, long long n, long long m) {
    long long res = 1;
    a %= m;
    while (n > 0) {
        if (n & 1) res = res * a % m;  // odd exponent
        a = a * a % m;                  // square base
        n >>= 1;                        // halve exponent
    }
    return res;
}
// power(2, 10, 1e9+7) → 1024

Java

static long power(long a, long n, long m) {
    long res = 1;
    a %= m;
    while (n > 0) {
        if ((n & 1) == 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}
// power(2, 10, 1_000_000_007L) → 1024

Python

def power(a, n, m):
    res = 1
    a %= m
    while n > 0:
        if n & 1:
            res = res * a % m
        a = a * a % m
        n >>= 1
    return res

# Python built-in is even better:
pow(2, 10, 10**9+7)  # 3-arg pow = modular exponentiation!

3. Modular Arithmetic

MOD = 10⁹+7 (prime). Use when the answer can be astronomically large. Key rule: never subtract and then mod — always add MOD before modding a subtraction.

Operation	Formula	Why
Addition	`(a + b) % MOD`	Simple, no overflow if a,b < MOD
Subtraction	`((a - b) % MOD + MOD) % MOD`	Result can be negative; +MOD fixes it
Multiplication	`(1LL * a * b) % MOD`	Cast to long long before multiply
Division	`a * modInverse(b, MOD) % MOD`	Only when MOD is prime (Fermat's theorem)
Modular Inverse	`power(b, MOD-2, MOD)`	b^(MOD-2) mod MOD (Fermat's little theorem)

C++

const long long MOD = 1e9 + 7;

long long add(long long a, long long b) {
    return (a + b) % MOD;
}
long long sub(long long a, long long b) {
    return ((a - b) % MOD + MOD) % MOD;
}
long long mul(long long a, long long b) {
    return (a % MOD) * (b % MOD) % MOD;
}
long long modInv(long long a, long long m = MOD) {
    return power(a, m - 2, m); // requires power() from above
}

Java

static final long MOD = 1_000_000_007L;

static long add(long a, long b) { return (a + b) % MOD; }
static long sub(long a, long b) { return ((a - b) % MOD + MOD) % MOD; }
static long mul(long a, long b) { return (a % MOD) * (b % MOD) % MOD; }
static long modInv(long a) { return power(a, MOD - 2, MOD); }

Python

MOD = 10**9 + 7

add = lambda a, b: (a + b) % MOD
sub = lambda a, b: (a - b + MOD) % MOD
mul = lambda a, b: a * b % MOD
# Python ints never overflow — but still use mod for large answers
mod_inv = lambda a: pow(a, MOD - 2, MOD)

4. XOR Tricks

XOR is the secret weapon for many interview problems. Key properties: a ^ a = 0, a ^ 0 = a, a ^ b ^ a = b (commutative & associative).

Trick	Code	Why it works
Swap without temp	`a^=b; b^=a; a^=b;`	a^b^b = a, b^a^a = b
Find single non-duplicate	`XOR all elements`	Pairs cancel out (x^x=0)
Missing number (0..N)	`XOR 0..N with array`	All present cancel; missing remains
Check same sign	`(a ^ b) >= 0`	Sign bit: 0=positive, 1=negative
Toggle case (ASCII)	`c ^ 32`	Bit 5 flips 'A'↔'a'

C++

// Find the single non-duplicate element
int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int x : nums) res ^= x;
    return res;
}

// Find missing number in [0..n]
int missingNumber(vector<int>& nums) {
    int res = nums.size();
    for (int i = 0; i < nums.size(); i++)
        res ^= i ^ nums[i];
    return res;
}

// XOR swap (avoid for equal addresses!)
void xorSwap(int& a, int& b) {
    if (&a != &b) { a ^= b; b ^= a; a ^= b; }
}

Java

int singleNumber(int[] nums) {
    int res = 0;
    for (int x : nums) res ^= x;
    return res;
}

int missingNumber(int[] nums) {
    int res = nums.length;
    for (int i = 0; i < nums.length; i++)
        res ^= i ^ nums[i];
    return res;
}

Python

from functools import reduce
import operator

def single_number(nums):
    return reduce(operator.xor, nums)  # XOR all

def missing_number(nums):
    n = len(nums)
    return reduce(operator.xor, nums) ^ reduce(operator.xor, range(n + 1))

5. Bit Manipulation Essentials

Operation	C++ / Java	Python	What it does
Check bit i	`(n >> i) & 1`	`(n >> i) & 1`	Returns 1 if bit i is set
Set bit i	`n \| (1 << i)`	`n \| (1 << i)`	Forces bit i to 1
Clear bit i	`n & ~(1 << i)`	`n & ~(1 << i)`	Forces bit i to 0
Toggle bit i	`n ^ (1 << i)`	`n ^ (1 << i)`	Flips bit i
Count set bits	`__builtin_popcount(n)`	`bin(n).count('1')`	Number of 1 bits
Is power of 2	`n && !(n & (n-1))`	`n > 0 and not n & (n-1)`	True if exactly one bit set
Lowest set bit	`n & (-n)`	`n & (-n)`	Isolates the rightmost 1 bit
Remove lowest set bit	`n & (n-1)`	`n & (n-1)`	Turns off rightmost 1 — core of Kernighan's algo

C++

// Count set bits — Brian Kernighan's algorithm O(k) where k = set bits
int countBits(int n) {
    int count = 0;
    while (n) { n &= (n - 1); count++; }
    return count;
}
// Or use built-in: __builtin_popcount(n)

bool isPowerOfTwo(int n) { return n > 0 && !(n & (n - 1)); }

// Enumerate all subsets of a bitmask
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // process subset `sub`
}

Java

int countBits(int n) {
    return Integer.bitCount(n);  // built-in
}
boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }
int highestOneBit(int n)  { return Integer.highestOneBit(n); }
int lowestOneBit(int n)   { return n & (-n); }

Python

count_bits = lambda n: bin(n).count('1')
is_power_of_two = lambda n: n > 0 and not (n & (n - 1))
lowest_set_bit = lambda n: n & (-n)

# Python has arbitrary precision — no overflow, but << can produce huge ints

6. Sieve of Eratosthenes

Find all primes up to N in O(N log log N). The classic: mark multiples of each prime as composite.

C++

vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;  // is_prime[i] == true means i is prime
}

Java

boolean[] sieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
        }
    }
    return isPrime;
}

Python

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n + 1, i):
                is_prime[j] = False
    return is_prime

7. Binary Search Templates

Three templates you must memorize. The key insight: always define what lo and hi represent, and maintain the invariant through every iteration.

C++

// Template 1: Exact match
int binarySearch(vector<int>& a, int target) {
    int lo = 0, hi = a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // avoids overflow
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

// Template 2: Lower bound — first index where a[i] >= target
int lowerBound(vector<int>& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;  // == a.size() if target > all elements
}

// Template 3: Upper bound — first index where a[i] > target
int upperBound(vector<int>& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
// C++ STL: lower_bound(a.begin(),a.end(),t), upper_bound(...)

Java

int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        else if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}
// Arrays.binarySearch(arr, target) — returns index or negative insertion point

Python

import bisect

# bisect_left = lower_bound (first index >= target)
bisect.bisect_left(a, target)

# bisect_right = upper_bound (first index > target)
bisect.bisect_right(a, target)

# Manual exact match
def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        elif a[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

8. Union-Find (Disjoint Set Union)

Find connected components, detect cycles in undirected graphs. With path compression + union by rank: nearly O(α(N)) ≈ O(1) per operation.

C++

struct DSU {
    vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;      // already connected
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
    bool connected(int x, int y) { return find(x) == find(y); }
};

Java

class DSU {
    int[] parent, rank;
    DSU(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    boolean unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) { int t = x; x = y; y = t; }
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
    boolean connected(int x, int y) { return find(x) == find(y); }
}

Python

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y = y, x
        self.parent[y] = x
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

9. Prefix Sum

Build once in O(N), then answer range sum queries in O(1). One of the most useful preprocessing tricks in competitive programming.

C++

// 1D prefix sum
vector<int> buildPrefix(vector<int>& a) {
    int n = a.size();
    vector<int> prefix(n + 1, 0);
    for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + a[i];
    return prefix;
}
// Sum of a[l..r] (0-indexed, inclusive)
int rangeSum(vector<int>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];
}

Java

int[] buildPrefix(int[] a) {
    int[] p = new int[a.length + 1];
    for (int i = 0; i < a.length; i++) p[i + 1] = p[i] + a[i];
    return p;
}
int rangeSum(int[] p, int l, int r) { return p[r + 1] - p[l]; }

Python

def build_prefix(a):
    prefix = [0] * (len(a) + 1)
    for i, v in enumerate(a):
        prefix[i + 1] = prefix[i] + v
    return prefix

def range_sum(prefix, l, r):  # inclusive [l, r]
    return prefix[r + 1] - prefix[l]

# Python: itertools.accumulate is elegant
from itertools import accumulate
prefix = [0] + list(accumulate(a))

10. Kadane's Algorithm — Maximum Subarray

Find the contiguous subarray with the maximum sum in O(N). Key insight: at each position, the best subarray ending here is either just the current element, or the current element extended from the best subarray ending at the previous position.

C++

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0], cur = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        cur = max(nums[i], cur + nums[i]);
        maxSum = max(maxSum, cur);
    }
    return maxSum;
}
// To also return the subarray indices, track start/end when cur resets

Java

int maxSubArray(int[] nums) {
    int maxSum = nums[0], cur = nums[0];
    for (int i = 1; i < nums.length; i++) {
        cur = Math.max(nums[i], cur + nums[i]);
        maxSum = Math.max(maxSum, cur);
    }
    return maxSum;
}

Python

def max_subarray(nums):
    max_sum = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        max_sum = max(max_sum, cur)
    return max_sum

11. Dutch National Flag (3-Way Partition)

Sort an array of 0s, 1s, 2s (or any 3 categories) in O(N) with O(1) space. Used in: Sort Colors (LeetCode 75), 3-way quicksort pivot partitioning.

C++

void sortColors(vector<int>& nums) {
    int lo = 0, mid = 0, hi = nums.size() - 1;
    while (mid <= hi) {
        if      (nums[mid] == 0) swap(nums[lo++], nums[mid++]);
        else if (nums[mid] == 1) mid++;
        else                    swap(nums[mid], nums[hi--]);
    }
}
// Invariant: [0,lo) = 0s, [lo,mid) = 1s, (hi,n) = 2s

Java

void sortColors(int[] nums) {
    int lo = 0, mid = 0, hi = nums.length - 1;
    while (mid <= hi) {
        if      (nums[mid] == 0) { int t=nums[lo]; nums[lo++]=nums[mid]; nums[mid++]=t; }
        else if (nums[mid] == 1) mid++;
        else                    { int t=nums[hi]; nums[hi--]=nums[mid]; nums[mid]=t; }
    }
}

Python

def sort_colors(nums):
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if   nums[mid] == 0: nums[lo], nums[mid] = nums[mid], nums[lo]; lo += 1; mid += 1
        elif nums[mid] == 1: mid += 1
        else:                nums[mid], nums[hi] = nums[hi], nums[mid]; hi -= 1

12. Trie (Prefix Tree)

A Trie stores strings character-by-character in a tree. Insert/search/prefix-check all run in O(L) where L is the word length — faster than a hash set for prefix queries. Essential for autocomplete, word search, and IP routing problems.

C++

struct TrieNode {
    TrieNode* children[26]{};
    bool isEnd = false;
};

class Trie {
    TrieNode* root;
public:
    Trie() : root(new TrieNode()) {}

    void insert(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->children[i])
                cur->children[i] = new TrieNode();
            cur = cur->children[i];
        }
        cur->isEnd = true;
    }

    bool search(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int i = c - 'a';
            if (!cur->children[i]) return false;
            cur = cur->children[i];
        }
        return cur->isEnd;
    }

    bool startsWith(const string& prefix) {
        TrieNode* cur = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!cur->children[i]) return false;
            cur = cur->children[i];
        }
        return true;
    }
};

Java

class Trie {
    private TrieNode root;

    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }

    public Trie() { root = new TrieNode(); }

    public void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) cur.children[i] = new TrieNode();
            cur = cur.children[i];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) return false;
            cur = cur.children[i];
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            int i = c - 'a';
            if (cur.children[i] == null) return false;
            cur = cur.children[i];
        }
        return true;
    }
}

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root
        for c in word:
            if c not in cur.children:
                cur.children[c] = TrieNode()
            cur = cur.children[c]
        cur.is_end = True

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return cur.is_end

    def starts_with(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

When to use a Trie

Use a Trie (not a HashMap) when you need prefix queries: "does any word start with 'pre'?" A HashSet answers exact lookups in O(1) but prefix search requires O(n·L) iteration. Trie answers prefix in O(L). Also useful when storing a large number of strings with shared prefixes (saves memory vs. storing each string separately).

⚠ Key Gotchas Across All Snippets

mid = lo + (hi - lo) / 2 — NOT (lo + hi) / 2. The latter overflows in C++/Java when lo + hi > INT_MAX.
LCM overflow — always compute as a / gcd(a, b) * b, not a * b / gcd.
Modular subtraction — always add MOD: ((a - b) % MOD + MOD) % MOD.
XOR swap — fails silently when a and b are the same variable/address. Always check &a != &b in C++.
Python recursion — default limit is 1000. Add sys.setrecursionlimit(10**5) at the top for DSU/DFS.

Practice These Patterns

Trie Graphs Dynamic Programming Binary Search Bit Manipulation