Patterns & Tips

# ============================================================
# PATTERN 1: Two-Pass vs One-Pass Statistics
# ============================================================

# TWO-PASS (simple and stable):
def variance_two_pass(data):
    n = len(data)
    mean = sum(data) / n                              # Pass 1
    return sum((x - mean)**2 for x in data) / (n-1)   # Pass 2

# ONE-PASS (Welford's - numerically stable):
def variance_one_pass(data):
    n = 0; mean = 0; M2 = 0
    for x in data:
        n += 1
        delta = x - mean
        mean += delta / n
        M2 += delta * (x - mean)
    return M2 / (n - 1)

# AVOID (catastrophic cancellation for large values):
def variance_NAIVE_DONT_USE(data):
    n = len(data)
    return sum(x**2 for x in data)/n - (sum(data)/n)**2  # BAD!


# ============================================================
# PATTERN 2: Log-Space Computation
# ============================================================

import math

# When multiplying many small probabilities:
# WRONG: product = p1 * p2 * p3 * ... * pn  (underflows to 0)
# RIGHT: log_product = log(p1) + log(p2) + ... + log(pn)

# Log-sum-exp trick for log(exp(a) + exp(b)):
def log_sum_exp(a, b):
    max_val = max(a, b)
    return max_val + math.log(math.exp(a - max_val) + math.exp(b - max_val))

# For a list of values:
def log_sum_exp_list(values):
    max_val = max(values)
    return max_val + math.log(sum(math.exp(v - max_val) for v in values))

# Log-factorial for combinatorics:
def log_factorial(n):
    return sum(math.log(i) for i in range(1, n + 1))

# Log-binomial coefficient:
def log_comb(n, k):
    return log_factorial(n) - log_factorial(k) - log_factorial(n - k)


# ============================================================
# PATTERN 3: Sampling With and Without Replacement
# ============================================================

import random

def sample_with_replacement(data, k):
    """Bootstrap-style sampling."""
    return [data[random.randint(0, len(data)-1)] for _ in range(k)]

def sample_without_replacement(data, k):
    """Fisher-Yates shuffle, take first k elements."""
    arr = list(data)
    n = len(arr)
    for i in range(min(k, n)):
        j = random.randint(i, n - 1)
        arr[i], arr[j] = arr[j], arr[i]
    return arr[:k]


# ============================================================
# PATTERN 4: Resampling-Based Inference
# ============================================================

def bootstrap_statistic(data, stat_func, num_bootstrap=10000):
    """General pattern for bootstrap anything."""
    n = len(data)
    stats = []
    for _ in range(num_bootstrap):
        sample = [data[random.randint(0, n-1)] for _ in range(n)]
        stats.append(stat_func(sample))
    stats.sort()
    return {
        "mean": sum(stats) / len(stats),
        "ci_95": (stats[int(0.025*num_bootstrap)], stats[int(0.975*num_bootstrap)])
    }

def permutation_p_value(a, b, stat_func, num_perms=10000):
    """General pattern for permutation test."""
    observed = stat_func(a, b)
    pooled = a + b
    count = 0
    for _ in range(num_perms):
        random.shuffle(pooled)
        perm_stat = stat_func(pooled[:len(a)], pooled[len(a):])
        if perm_stat >= observed:
            count += 1
    return count / num_perms


# ============================================================
# PATTERN 5: Bayesian Update
# ============================================================

def bayesian_update_discrete(prior, likelihood):
    """Discrete Bayes: posterior = normalize(prior * likelihood)."""
    unnorm = {h: prior[h] * likelihood[h] for h in prior}
    total = sum(unnorm.values())
    return {h: p / total for h, p in unnorm.items()}

def beta_binomial_update(alpha, beta, successes, failures):
    """Conjugate update: Beta(a,b) + Binom data -> Beta(a+s, b+f)."""
    return alpha + successes, beta + failures

import math

# ============================================================
# PITFALL 1: Catastrophic Cancellation
# ============================================================
# When subtracting two nearly-equal large numbers, relative error explodes.

# Example: variance of [1e9 + 1, 1e9 + 2, 1e9 + 3]
# Naive: E[X^2] - E[X]^2 = 1e18 + ... - 1e18 - ... (cancellation!)
# Correct: use two-pass or Welford's algorithm


# ============================================================
# PITFALL 2: Floating-Point Comparison
# ============================================================
# WRONG: if a == b
# RIGHT: if abs(a - b) < epsilon

def approx_equal(a, b, rel_tol=1e-9, abs_tol=1e-12):
    """Compare floats safely."""
    return abs(a - b) <= max(rel_tol * max(abs(a), abs(b)), abs_tol)


# ============================================================
# PITFALL 3: Probability Underflow
# ============================================================
# Multiplying 1000 probabilities of 0.1 each:
# 0.1^1000 = 1e-1000 (underflows to 0.0 in float64!)

# Solution: work in log-space
# log(0.1^1000) = 1000 * log(0.1) = -2302.6 (perfectly representable)


# ============================================================
# PITFALL 4: Log of Zero
# ============================================================
# log(0) = -inf, which breaks computations.
# Solution: add a small epsilon
LOG_EPS = 1e-300  # smallest positive float64 ~ 5e-324
safe_log = lambda x: math.log(max(x, LOG_EPS))


# ============================================================
# PITFALL 5: Overflow in Exponentials
# ============================================================
# exp(1000) overflows to inf in float64.
# Solution: the log-sum-exp trick

# log(exp(a) + exp(b)):
# WRONG: math.log(math.exp(a) + math.exp(b))  # exp(1000) = inf
# RIGHT: max(a,b) + log(exp(a-max) + exp(b-max))  # stable!


# ============================================================
# PITFALL 6: Integer Overflow in Combinatorics
# ============================================================
# 100! has 158 digits. Python handles big integers natively,
# but log-space is still better for probabilities.

# C(1000, 500) is astronomically large, but:
# log(C(1000,500)) = sum(log(i) for i in 501..1000) - sum(log(i) for i in 1..500)
# This is perfectly representable as a float.


# ============================================================
# PITFALL 7: Kahan Summation for Precision
# ============================================================
def kahan_sum(values):
    """Compensated summation - reduces error from O(n*eps) to O(eps)."""
    total = 0.0
    compensation = 0.0
    for x in values:
        y = x - compensation
        t = total + y
        compensation = (t - total) - y
        total = t
    return total

# When does Kahan matter?
# Summing 1e6 values of ~1.0: normal sum error ~ 1e-10
# Kahan sum error ~ 1e-16 (machine epsilon)
# For most interview problems, regular sum is fine.
# Mention Kahan if the interviewer asks about precision.