Combinatorics & Probability

Interview Relevance: Combinatorics and probability questions appear frequently in Google interviews — both as standalone math questions and as the analytical backbone of algorithmic problems. Understanding counting principles helps you compute time complexity, reason about randomized algorithms, and solve a wide class of "how many ways" problems.

Part 1: Counting Principles

Rule of Sum (Addition Principle)

If task A can be done in m ways and task B can be done in n ways, and the tasks are mutually exclusive (can't both happen), then "A or B" can be done in m + n ways.

Example: You can take bus (3 routes) or train (5 routes) to work.
Total options = 3 + 5 = 8

Formally: |A ∪ B| = |A| + |B|  when A ∩ B = ∅

Rule of Product (Multiplication Principle)

If task A can be done in m ways and for each way, task B can be done in n ways, then "A and B" can be done in m × n ways.

Example: You pick a shirt (4 options) AND pants (3 options).
Total outfits = 4 × 3 = 12

Formally: |A × B| = |A| × |B|

Worked Example: Counting 3-Digit Numbers with Distinct Digits

How many 3-digit numbers (100-999) have ALL different digits?

Position:     Hundreds    Tens    Ones
Choices:         9    ×    9   ×   8   = 648
              (1-9)    (0-9     (0-9
            can't be  minus    minus
              zero)   hundreds) both)

Why 9 for tens? We have digits 0-9 (10 digits), minus the one used for hundreds.
Why 8 for ones? 10 digits minus the two already used.

Complementary Counting

Sometimes it's easier to count what you don't want and subtract.

Count(what we want) = Count(everything) - Count(what we don't want)

Example: How many 4-digit numbers have at least one repeated digit?
  Total 4-digit numbers: 9000 (1000 to 9999)
  Numbers with ALL distinct digits: 9 × 9 × 8 × 7 = 4536
  Answer: 9000 - 4536 = 4464

Part 2: Permutations

Permutations (Ordered Arrangements)

A permutation is an ordered arrangement. The order matters: ABC != BAC.

n! = n × (n-1) × (n-2) × ... × 1

0! = 1  (by convention)
1! = 1
5! = 120
10! = 3,628,800
20! ≈ 2.4 × 10^18  (overflows 64-bit int!)

P(n, r) = number of ways to choose r items from n items where order matters:

P(n, r) = n! / (n - r)!

P(5, 3) = 5! / 2! = 120 / 2 = 60

Intuition: Fill r positions from n items:
  Position 1: n choices
  Position 2: n-1 choices
  ...
  Position r: n-r+1 choices
  Product: n × (n-1) × ... × (n-r+1) = n! / (n-r)!

Permutations with Repetition

When elements repeat, we divide out the redundant arrangements.

"MISSISSIPPI" has 11 letters:
  M: 1, I: 4, S: 4, P: 2

Arrangements = 11! / (1! × 4! × 4! × 2!)
             = 39,916,800 / (1 × 24 × 24 × 2)
             = 39,916,800 / 1,152
             = 34,650

Why divide? Consider the 4 I's. If we label them I₁I₂I₃I₄,
we get 4! = 24 arrangements that look identical when labels are removed.
Same logic for S's and P's.

Circular Permutations

Arranging n distinct objects in a circle: (n-1)!

Next Permutation Algorithm (LeetCode 31)

Find the next lexicographically greater permutation.

Algorithm:
1. From right, find first i where nums[i] < nums[i+1]  (the "dip")
2. From right, find first j where nums[j] > nums[i]     (smallest larger)
3. Swap nums[i] and nums[j]
4. Reverse everything after position i

Example: [1, 3, 5, 4, 2]
Step 1: i=1 (nums[1]=3 < nums[2]=5)
Step 2: j=3 (nums[3]=4 > nums[1]=3)
Step 3: Swap → [1, 4, 5, 3, 2]
Step 4: Reverse after pos 1 → [1, 4, 2, 3, 5]

CPP

// LC 31: Next Permutation
void nextPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;

    // Step 1: Find first decreasing element from right
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;

    if (i >= 0) {
        // Step 2: Find smallest element larger than nums[i] from right
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;

        // Step 3: Swap
        swap(nums[i], nums[j]);
    }

    // Step 4: Reverse suffix
    reverse(nums.begin() + i + 1, nums.end());
}

Time: O(n), Space: O(1)

Part 3: Combinations (n choose k)

Definition

C(n, k) = "n choose k" = number of ways to choose k items from n items, order doesn't matter.

C(n, k) = n! / (k! × (n - k)!)

C(5, 2) = 5! / (2! × 3!) = 120 / (2 × 6) = 10

The 10 subsets of size 2 from {A,B,C,D,E}:
  {A,B} {A,C} {A,D} {A,E}
  {B,C} {B,D} {B,E}
  {C,D} {C,E}
  {D,E}

Essential Properties

C(n, 0) = C(n, n) = 1             ← empty set / full set
C(n, 1) = C(n, n-1) = n           ← choose one / leave one out
C(n, k) = C(n, n-k)               ← symmetry (choosing k = leaving out n-k)
C(n, k) = C(n-1, k-1) + C(n-1, k) ← Pascal's identity

Pascal's identity intuition:
  Consider element n. Either:
  - Include it: choose remaining k-1 from n-1 → C(n-1, k-1)
  - Exclude it: choose all k from n-1 → C(n-1, k)

Binomial Theorem

(x + y)^n = Σ C(n, k) × x^(n-k) × y^k    for k = 0 to n

Setting x=1, y=1:  2^n = Σ C(n, k)  ← total number of subsets
Setting x=1, y=-1: 0 = Σ (-1)^k × C(n, k)  ← even/odd subsets balance

Pascal's Triangle

Computing C(n, k) in Code

Method 1: Pascal's Triangle DP — Good for Multiple Queries

CPP

// Precompute all C(i, j) for 0 ≤ i ≤ n, 0 ≤ j ≤ i
// Time: O(n²), Space: O(n²)
vector<vector<long long>> pascalTriangle(int n) {
    vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
    return C;
}

// LC 118: Pascal's Triangle
vector<vector<int>> generate(int numRows) {
    vector<vector<int>> triangle;
    for (int i = 0; i < numRows; i++) {
        triangle.push_back(vector<int>(i + 1, 1));
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    return triangle;
}

Method 2: Direct Computation — Single Query, Avoid Overflow

CPP

// Compute C(n, k) directly without computing full factorials
// Key insight: compute iteratively, dividing as we go to keep numbers small
// Time: O(k), Space: O(1)
long long nCr(int n, int k) {
    if (k > n - k) k = n - k; // optimization: C(n,k) = C(n,n-k)
    long long result = 1;
    for (int i = 0; i < k; i++) {
        result = result * (n - i) / (i + 1);
        // This division is always exact because:
        // result * (n-i) / (i+1) = C(n, i+1) which is always an integer
    }
    return result;
}

Why does division always work exactly? At step i, we have computed C(n, i). Multiplying by (n-i) and dividing by (i+1) gives C(n, i+1), which is always an integer.

Method 3: Modular Arithmetic — Competitive Programming / Large Values

When answers must be computed mod a large prime (typically 10^9 + 7):

CPP

const int MOD = 1e9 + 7;

// Binary exponentiation: compute base^exp % mod in O(log exp)
long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

// Modular inverse using Fermat's Little Theorem
// a^(-1) ≡ a^(p-2) (mod p) when p is prime
long long modInverse(long long a, long long mod) {
    return power(a, mod - 2, mod);
}

// C(n, k) mod p
long long nCrMod(int n, int k) {
    if (k > n) return 0;
    if (k == 0 || k == n) return 1;

    long long num = 1, den = 1;
    for (int i = 0; i < k; i++) {
        num = num * ((n - i) % MOD) % MOD;
        den = den * ((i + 1) % MOD) % MOD;
    }
    return num % MOD * modInverse(den, MOD) % MOD;
}

Method 4: Precomputed Factorials — Many Queries with Same Mod

CPP

const int MAXN = 200001;
const int MOD = 1e9 + 7;
long long fact[MAXN], inv_fact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i-1] * i % MOD;

    inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}

long long nCrFast(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] % MOD * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

Time: O(N) precomputation, O(1) per query.

Part 4: Common Counting Problems

Stars and Bars (Balls and Urns)

Problem: Distribute n identical objects into k distinct bins.

"How many ways to put n identical balls into k distinct boxes?"

Case 1: Each bin can have 0 or more → C(n + k - 1, k - 1)
Case 2: Each bin has at least 1   → C(n - 1, k - 1)

Intuition for Case 1:
  Imagine n stars ★ and k-1 bars | as separators.
  Any arrangement of these n + k - 1 symbols gives a distribution.

  Example: n=5 balls, k=3 boxes
  ★★|★★★|  → (2, 3, 0)
  |★★★★|★ → (0, 4, 1)
  ★|★|★★★ → (1, 1, 3)

  Total arrangements: C(5+3-1, 3-1) = C(7, 2) = 21

Intuition for Case 2:
  Pre-place 1 ball in each box. Now distribute n-k remaining balls
  with 0+ per box: C(n-k+k-1, k-1) = C(n-1, k-1)

Interview application: "How many non-negative integer solutions does x₁ + x₂ + ... + x_k = n have?" Answer: C(n + k - 1, k - 1).

Inclusion-Exclusion Principle

For counting the union of multiple sets:

|A ∪ B| = |A| + |B| - |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C|
             - |A∩B| - |A∩C| - |B∩C|
             + |A∩B∩C|

General:
|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ∩Aⱼ| + Σ|Aᵢ∩Aⱼ∩Aₖ| - ...

Example: Divisibility Counting

How many integers from 1 to 1000 are divisible by 2, 3, or 5?

A₂ = multiples of 2: |A₂| = ⌊1000/2⌋ = 500
A₃ = multiples of 3: |A₃| = ⌊1000/3⌋ = 333
A₅ = multiples of 5: |A₅| = ⌊1000/5⌋ = 200

A₂ ∩ A₃ = multiples of 6:  |A₆|  = ⌊1000/6⌋  = 166
A₂ ∩ A₅ = multiples of 10: |A₁₀| = ⌊1000/10⌋ = 100
A₃ ∩ A₅ = multiples of 15: |A₁₅| = ⌊1000/15⌋ = 66

A₂ ∩ A₃ ∩ A₅ = multiples of 30: |A₃₀| = ⌊1000/30⌋ = 33

Answer = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734

Code: Counting Numbers Not Divisible by Any Given Primes (Euler's Totient)

CPP

// Count numbers 1..n coprime to m using inclusion-exclusion
long long countCoprime(long long n, vector<int>& primeFactors) {
    int k = primeFactors.size();
    long long count = 0;

    // Iterate over all 2^k subsets of prime factors
    for (int mask = 1; mask < (1 << k); mask++) {
        long long product = 1;
        int bits = __builtin_popcount(mask);

        for (int i = 0; i < k; i++) {
            if (mask & (1 << i))
                product *= primeFactors[i];
        }

        if (bits % 2 == 1)
            count += n / product;  // add
        else
            count -= n / product;  // subtract
    }

    return n - count; // coprime = total minus divisible
}

Catalan Numbers

One of the most important sequences in combinatorics.

C_n = C(2n, n) / (n + 1)

Recurrence: C_n = Σ C_i × C_(n-1-i)  for i = 0 to n-1
            C_0 = 1

First few:  1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
Index:      0  1  2  3   4   5    6    7     8     9

The Catalan number C_n counts:

Valid parentheses sequences of length 2n

n=3: ((())), (()()), (())(), ()(()), ()()()  → 5 = C_3

Full binary trees with n+1 leaves (or n internal nodes)

L L L L L L L L L L L L L L L L L L L L 5 shapes with 3 internal nodes (filled) and 4 leaves (L) = C_3 = 5

Paths in n×n grid staying below the diagonal (Dyck paths)

01 23 01 23 (0,0) (3,3) y = x R = right, U = up At any prefix: #R >= #U RRRUUU RRURUU RRUURU RURURU RURRUU 5 paths = C_3

Triangulations of a polygon with n+2 sides
Number of BSTs with n nodes (distinct keys 1..n)
Mountain ranges with n upstrokes and n downstrokes

CPP

// Catalan number computation
long long catalan(int n) {
    return nCr(2 * n, n) / (n + 1);
}

// Catalan with modular arithmetic
long long catalanMod(int n) {
    return nCrMod(2 * n, n) * modInverse(n + 1, MOD) % MOD;
}

// Catalan via DP (recurrence)
vector<long long> catalanDP(int n) {
    vector<long long> C(n + 1, 0);
    C[0] = C[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            C[i] += C[j] * C[i - 1 - j];
        }
    }
    return C;
}

Interview application: "How many structurally unique BSTs can store values 1..n?" → C_n (LC 96)

CPP

// LC 96: Unique Binary Search Trees
int numTrees(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int root = 1; root <= i; root++) {
            // root splits into left subtree (root-1 nodes) and right (i-root nodes)
            dp[i] += dp[root - 1] * dp[i - root];
        }
    }
    return dp[n];
}

Derangements

A derangement is a permutation where no element appears in its original position.

D(n) = number of derangements of n elements

Recurrence: D(n) = (n - 1) × (D(n-1) + D(n-2))

Intuition: Element 1 goes to position k (n-1 choices for k). Then:
  - If element k goes to position 1: derange remaining n-2 → D(n-2)
  - If element k goes elsewhere: like deranging n-1 elements → D(n-1)

D(0) = 1  (empty permutation is a derangement by convention)
D(1) = 0  (1 must go to position 1)
D(2) = 1  ({2,1})
D(3) = 2  ({2,3,1}, {3,1,2})
D(4) = 9
D(5) = 44

Closed form: D(n) = n! × Σ (-1)^k / k!  for k = 0 to n
           ≈ n! / e  (rounded to nearest integer)

CPP

long long derangements(int n) {
    if (n == 0) return 1;
    if (n == 1) return 0;

    long long prev2 = 1, prev1 = 0; // D(0), D(1)
    for (int i = 2; i <= n; i++) {
        long long curr = (i - 1) * (prev1 + prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Stirling Numbers

Stirling numbers of the second kind S(n, k): number of ways to partition n elements into exactly k non-empty subsets.

S(n, k) = k × S(n-1, k) + S(n-1, k-1)

Intuition for element n:
  - Add to one of k existing groups: k × S(n-1, k)
  - Create a new singleton group: S(n-1, k-1)

S(4, 2) = 7:
  {1,2,3},{4}    {1,2,4},{3}    {1,3,4},{2}    {2,3,4},{1}
  {1,2},{3,4}    {1,3},{2,4}    {1,4},{2,3}

Bell Numbers

B(n) = total number of partitions of n elements = Σ S(n, k) for k = 0 to n.

B(0) = 1, B(1) = 1, B(2) = 2, B(3) = 5, B(4) = 15, B(5) = 52

Part 5: Probability

Basic Definitions

Sample space Ω: set of all possible outcomes
Event A: a subset of Ω
P(A) = |A| / |Ω|  (for uniform probability)

Axioms:
  0 ≤ P(A) ≤ 1
  P(Ω) = 1
  P(A ∪ B) = P(A) + P(B) when A ∩ B = ∅

Core Rules

Complement:     P(A') = 1 - P(A)
Union:          P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
Independence:   P(A ∩ B) = P(A) × P(B)  iff A and B are independent

Conditional Probability

P(A | B) = P(A ∩ B) / P(B)

"Probability of A, given that B has occurred"

Example: Roll two dice.
  P(sum = 8 | first die = 3)?

  Given first = 3, we need second = 5.
  P = 1/6

  Formally:
  P(sum=8 ∩ first=3) = P(first=3, second=5) = 1/36
  P(first=3) = 1/6
  P(sum=8 | first=3) = (1/36) / (1/6) = 1/6  ✓

Bayes' Theorem

P(A | B) = P(B | A) × P(A) / P(B)

Classic example: Disease testing
  P(disease) = 0.001          (1 in 1000 people have it)
  P(positive | disease) = 0.99   (99% sensitivity)
  P(positive | no disease) = 0.05  (5% false positive)

  P(disease | positive) = ?

  P(positive) = P(pos|disease)×P(disease) + P(pos|no disease)×P(no disease)
              = 0.99 × 0.001 + 0.05 × 0.999
              = 0.000990 + 0.049950
              = 0.050940

  P(disease | positive) = 0.99 × 0.001 / 0.050940 ≈ 0.0194

  Only ~2%! Even with a positive test, 98% chance of no disease.
  (This is the "base rate fallacy" — common interview discussion point)

Law of Total Probability

P(B) = Σ P(B | Aᵢ) × P(Aᵢ)    where {Aᵢ} partitions Ω

Example: P(positive) above was computed this way.

Part 6: Expected Value

Definition

E[X] = Σ x × P(X = x)

Expected value of a die roll:
E[X] = 1×(1/6) + 2×(1/6) + 3×(1/6) + 4×(1/6) + 5×(1/6) + 6×(1/6)
     = 21/6 = 3.5

Linearity of Expectation (THE Most Important Property)

E[X + Y] = E[X] + E[Y]

This ALWAYS holds, even if X and Y are NOT independent!
This is incredibly powerful for solving problems.

Example: Expected Number of Inversions in Random Permutation

An inversion is a pair (i, j) where i < j but a[i] > a[j].

For each pair (i, j), let Xᵢⱼ = 1 if it's an inversion, 0 otherwise.
Total inversions X = Σ Xᵢⱼ

By linearity: E[X] = Σ E[Xᵢⱼ] = Σ P(inversion at (i,j))

For any pair, P(a[i] > a[j]) = 1/2 (by symmetry)
Number of pairs: C(n, 2)

E[X] = C(n, 2) × 1/2 = n(n-1)/4

Geometric Distribution

Number of independent trials until first success, where each trial succeeds with probability p.

P(X = k) = (1-p)^(k-1) × p    for k = 1, 2, 3, ...

E[X] = 1/p

Example: Expected coin flips until heads = 1/(1/2) = 2
Example: Expected die rolls until 6 = 1/(1/6) = 6

Coupon Collector Problem

Expected number of trials to collect all n distinct coupons (each trial gives a uniformly random coupon):

After collecting k coupons, probability of getting a new one = (n-k)/n.
Expected trials to get the next new coupon = n/(n-k).

E[total] = Σ n/(n-k)  for k = 0 to n-1
         = n × (1/n + 1/(n-1) + ... + 1/1)
         = n × H(n)
         = n × (1 + 1/2 + 1/3 + ... + 1/n)
         ≈ n × ln(n) + 0.577n

For n = 100: E ≈ 100 × 5.187 ≈ 519 trials to collect all 100 coupons

Breakdown for n=4:
  Have 0, need any: E = 4/4 = 1
  Have 1, need new:  E = 4/3 ≈ 1.33
  Have 2, need new:  E = 4/2 = 2
  Have 3, need last: E = 4/1 = 4
  Total E = 1 + 4/3 + 2 + 4 = 8.33

Indicator Random Variables

A powerful technique: represent complex quantities as sums of simple 0/1 variables.

X = "number of fixed points in a random permutation"

Let Xᵢ = 1 if element i is in position i, 0 otherwise.
X = X₁ + X₂ + ... + Xₙ

E[Xᵢ] = P(element i in position i) = 1/n

E[X] = Σ E[Xᵢ] = n × (1/n) = 1

Expected number of fixed points in a random permutation = 1
(regardless of n!)

Part 7: Probability in Coding Problems

Reservoir Sampling — Select k Items Uniformly from a Stream

Problem: You see elements one at a time from a stream of unknown size. After the stream ends, output k elements chosen uniformly at random.

Algorithm (k=1):

For the i-th element (1-indexed):
  With probability 1/i, replace the current selection with element i.

Proof: After seeing n elements, P(element i was chosen) =
  P(selected at step i) × P(not replaced in steps i+1..n)
  = (1/i) × (1 - 1/(i+1)) × (1 - 1/(i+2)) × ... × (1 - 1/n)
  = (1/i) × (i/(i+1)) × ((i+1)/(i+2)) × ... × ((n-1)/n)
  = 1/n  ✓  (telescoping!)

CPP

// LC 382: Linked List Random Node
class Solution {
    ListNode* head;
public:
    Solution(ListNode* head) : head(head) {}

    int getRandom() {
        int result = head->val;
        ListNode* curr = head->next;
        int i = 2;

        while (curr) {
            // With probability 1/i, select this element
            if (rand() % i == 0) {
                result = curr->val;
            }
            curr = curr->next;
            i++;
        }
        return result;
    }
};

General Reservoir Sampling (k items)

CPP

// Select k items uniformly at random from a stream
vector<int> reservoirSample(vector<int>& stream, int k) {
    vector<int> reservoir(stream.begin(), stream.begin() + k);

    for (int i = k; i < stream.size(); i++) {
        int j = rand() % (i + 1); // random index in [0, i]
        if (j < k) {
            reservoir[j] = stream[i];
        }
    }
    return reservoir;
}

Fisher-Yates Shuffle (Knuth Shuffle)

Generate a uniformly random permutation in O(n) time.

Algorithm:
For i from n-1 down to 1:
  j = random integer in [0, i]
  swap(arr[i], arr[j])

Why it works:
  Step n-1: any element has 1/n chance of landing at position n-1
  Step n-2: any remaining element has 1/(n-1) chance at position n-2
  ...
  Total: each permutation has probability 1/n!

CPP

// LC 384: Shuffle an Array
class Solution {
    vector<int> original;
public:
    Solution(vector<int>& nums) : original(nums) {}

    vector<int> reset() {
        return original;
    }

    vector<int> shuffle() {
        vector<int> arr = original;
        for (int i = arr.size() - 1; i > 0; i--) {
            int j = rand() % (i + 1);
            swap(arr[i], arr[j]);
        }
        return arr;
    }
};

Common mistake: j = rand() % n instead of j = rand() % (i + 1). This produces a biased distribution!

Random Pick with Weight (LC 528)

Pick index i with probability proportional to w[i].

weights: [1, 3, 2]
total = 6
cumulative: [1, 4, 6]

Generate random number r in [1, 6]:
  r = 1: pick index 0
  r = 2, 3, 4: pick index 1
  r = 5, 6: pick index 2

Use binary search on cumulative prefix sums.

CPP

class Solution {
    vector<int> prefix;
    int total;
public:
    Solution(vector<int>& w) {
        prefix.resize(w.size());
        prefix[0] = w[0];
        for (int i = 1; i < w.size(); i++)
            prefix[i] = prefix[i-1] + w[i];
        total = prefix.back();
    }

    int pickIndex() {
        int r = rand() % total; // [0, total-1]
        // Find first index where prefix[i] > r
        return upper_bound(prefix.begin(), prefix.end(), r) - prefix.begin();
    }
};

Random Point in Non-overlapping Rectangles (LC 497)

CPP

class Solution {
    vector<vector<int>> rects;
    vector<int> prefix; // prefix sum of areas
    int total;
public:
    Solution(vector<vector<int>>& rects) : rects(rects) {
        total = 0;
        for (auto& r : rects) {
            // Number of integer points in rectangle [x1,y1,x2,y2]
            int area = (r[2] - r[0] + 1) * (r[3] - r[1] + 1);
            total += area;
            prefix.push_back(total);
        }
    }

    vector<int> pick() {
        int r = rand() % total;
        int idx = upper_bound(prefix.begin(), prefix.end(), r) - prefix.begin();
        auto& rect = rects[idx];
        int x = rect[0] + rand() % (rect[2] - rect[0] + 1);
        int y = rect[1] + rand() % (rect[3] - rect[1] + 1);
        return {x, y};
    }
};

Part 8: Classic Interview Problems with Solutions

Unique Paths (LC 62)

An m×n grid, start at top-left, move only right or down. Count paths to bottom-right.

Combinatorial solution: We need exactly (m-1) down moves and (n-1) right moves. Choose which (m-1) of the (m+n-2) total moves are "down":

Answer = C(m + n - 2, m - 1) = C(m + n - 2, n - 1)

Example: 3×4 grid → C(3+4-2, 3-1) = C(5, 2) = 10

CPP

// LC 62: Unique Paths — combinatorial O(min(m,n))
int uniquePaths(int m, int n) {
    // C(m+n-2, m-1)
    long long result = 1;
    int k = min(m - 1, n - 1);
    for (int i = 0; i < k; i++) {
        result = result * (m + n - 2 - i) / (i + 1);
    }
    return (int)result;
}

// Alternative: DP solution O(mn) — useful when there are obstacles (LC 63)
int uniquePathsDP(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
    return dp[m-1][n-1];
}

Count Primes (LC 204)

Count primes less than n using Sieve of Eratosthenes.

CPP

// LC 204: Count Primes
int countPrimes(int n) {
    if (n <= 2) return 0;

    vector<bool> is_prime(n, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; (long long)i * i < n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j < n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    int count = 0;
    for (int i = 2; i < n; i++)
        if (is_prime[i]) count++;
    return count;
}

Time: O(n log log n), Space: O(n)

Pow(x, n) — Fast Exponentiation (LC 50)

CPP

// LC 50: Pow(x, n)
double myPow(double x, int n) {
    long long N = n; // handle INT_MIN
    if (N < 0) {
        x = 1 / x;
        N = -N;
    }

    double result = 1.0;
    while (N > 0) {
        if (N & 1) result *= x;
        x *= x;
        N >>= 1;
    }
    return result;
}

Time: O(log n)

Permutation Sequence (LC 60)

Given n and k, return the k-th permutation of [1, 2, ..., n].

Key insight: the first (n-1)! permutations start with 1,
the next (n-1)! start with 2, etc.

For n=4, k=14:
  Each leading digit covers 3! = 6 permutations.
  k-1 = 13 (0-indexed)
  13 / 6 = 2 → third digit (1-indexed) = 3
  13 % 6 = 1 → 2nd permutation of remaining {1, 2, 4}
  1 / 2 = 0 → first remaining = 1
  1 % 2 = 1 → 2nd permutation of {2, 4}
  1 / 1 = 1 → second remaining = 4
  Remaining: {2}

  Answer: 3 1 4 2

CPP

// LC 60: Permutation Sequence
string getPermutation(int n, int k) {
    vector<int> factorial(n + 1, 1);
    for (int i = 1; i <= n; i++)
        factorial[i] = factorial[i-1] * i;

    vector<int> digits;
    for (int i = 1; i <= n; i++) digits.push_back(i);

    string result;
    k--; // 0-indexed

    for (int i = n; i >= 1; i--) {
        int idx = k / factorial[i - 1];
        result += to_string(digits[idx]);
        digits.erase(digits.begin() + idx);
        k %= factorial[i - 1];
    }

    return result;
}

Generate Parentheses (LC 22) — Catalan Application

CPP

// LC 22: Generate Parentheses
vector<string> generateParenthesis(int n) {
    vector<string> result;

    function<void(string&, int, int)> generate = [&](string& curr,
                                                      int open, int close) {
        if (curr.size() == 2 * n) {
            result.push_back(curr);
            return;
        }
        if (open < n) {
            curr.push_back('(');
            generate(curr, open + 1, close);
            curr.pop_back();
        }
        if (close < open) {
            curr.push_back(')');
            generate(curr, open, close + 1);
            curr.pop_back();
        }
    };

    string s;
    generate(s, 0, 0);
    return result;
}

Number of results: C_n (nth Catalan number)

Part 9: Probability Puzzles Often Asked in Interviews

1. Birthday Paradox

What's the probability that at least 2 people in a room of k share a birthday?

P(no collision) = 365/365 × 364/365 × 363/365 × ... × (365-k+1)/365

P(at least one collision) = 1 - P(no collision)

k=23: P ≈ 50.7%  (only 23 people for >50% chance!)
k=50: P ≈ 97%
k=70: P ≈ 99.9%

This is why hash collisions happen sooner than you'd expect.
For a hash table with n buckets, expect first collision after ~√n insertions.

2. Monty Hall Problem

Three doors: one has a car, two have goats. You pick a door. The host opens another door showing a goat. Should you switch?

Initial pick:       P(car) = 1/3
Host reveals goat.
Staying:            P(car) = 1/3
Switching:          P(car) = 2/3  ← ALWAYS SWITCH!

Intuition: Your initial choice was 1/3 likely correct.
The remaining 2/3 probability is concentrated on the one unopened door.

3. Expected Rolls to See All Faces of a Die

This is the coupon collector problem with n=6:

E = 6 × (1/6 + 1/5 + 1/4 + 1/3 + 1/2 + 1/1)
  = 6 × (0.167 + 0.200 + 0.250 + 0.333 + 0.500 + 1.000)
  = 6 × 2.450
  = 14.7 rolls

4. Random Walk

Starting at position 0, each step +1 or -1 with equal probability. Expected steps to reach position k?

E[reach k from 0] = k²

E[reach k from i] = (k - i)²  (for 0 ≤ i ≤ k)

This comes from the optional stopping theorem applied to
the martingale X_n² - n.