QUANT PREP TERMINAL

• P(A|B)=P(A∩B)/P(B), defined for P(B)>0. Read it as: renormalize the sample space to B.
• Chain rule: P(A∩B∩C)=P(A)·P(B|A)·P(C|A∩B) — the workhorse for sequential draws.
• Conditioning is just slicing then renormalizing; the denominator is the new universe.
• Independence ⇔ P(A|B)=P(A) ⇔ P(A∩B)=P(A)P(B). Pairwise independence does NOT imply mutual independence.
• Watch the trap: P(A|B)≠P(B|A) in general (prosecutor's fallacy).

• Partition {Bᵢ} of the sample space: P(A)=Σᵢ P(A|Bᵢ)P(Bᵢ). Average the conditionals, weighted by prior.
• Bayes: P(Bⱼ|A)=P(A|Bⱼ)P(Bⱼ)/Σᵢ P(A|Bᵢ)P(Bᵢ).
• Posterior ∝ likelihood × prior; the denominator is just the normalizer P(A).
• Odds form is fastest for two hypotheses: posterior odds = prior odds × likelihood ratio.
• Rare-event trap: even a good test produces mostly false positives when the base rate is tiny — low prior dominates.

• E[aX+bY]=aE[X]+bE[Y] ALWAYS — no independence needed. This breaks most hard problems.
• LOTUS: E[g(X)]=Σ g(x)p(x) or ∫ g(x)f(x)dx — don't derive the dist of g(X).
• Tail sum for nonneg integers: E[X]=Σₖ₌₁ P(X≥k); continuous: E[X]=∫₀^∞ P(X>x)dx.
• Decompose into indicators and sum expectations — independence is irrelevant for the mean.
• Law of total expectation: E[X]=E[E[X|Y]].

• Write the count as X=Σ Iₐ where Iₐ∈{0,1}; then E[X]=Σ P(Aₐ) by linearity.
• Key identity: E[Iₐ]=P(Aₐ) and Iₐ²=Iₐ.
• For variance of a sum of indicators: Var(X)=Σ Var(Iₐ)+ΣΣ_{a≠b} Cov(Iₐ,I_b); Cov(Iₐ,I_b)=P(Aₐ∩A_b)−P(Aₐ)P(A_b).
• Never enumerate — assign one indicator per object and sum. Handles dependence automatically for the mean.

• Var(X)=E[X²]−(E[X])²; Cov(X,Y)=E[XY]−E[X]E[Y].
• Var(aX+bY)=a²Var(X)+b²Var(Y)+2ab·Cov(X,Y). Cross term vanishes only if uncorrelated.
• ρ=Cov(X,Y)/(σ_Xσ_Y)∈[−1,1]; measures LINEAR dependence only.
• Independent ⇒ uncorrelated, but uncorrelated does NOT ⇒ independent.
• Variance of a sum of n iid: nσ²; of the mean: σ²/n.

• Tower rule: E[X]=E[E[X|Y]] — condition on whatever simplifies the problem.
• Eve's law: Var(X)=E[Var(X|Y)]+Var(E[X|Y]) = within-group + between-group variance.
• E[X|Y] is a random variable (a function of Y); plug in a value to get a number.
• First-step analysis: condition on the first move, write a recursion, solve.

• Markov (X≥0): P(X≥a)≤E[X]/a. Only the mean; loose but assumption-free.
• Chebyshev: P(|X−μ|≥kσ)≤1/k² — needs finite variance, distribution-free.
• Markov bounds the upper tail from the mean; Chebyshev bounds two-sided spread from the variance.
• Chebyshev proves the weak law of large numbers: sample mean variance σ²/n→0.
• Tighter tails (Chernoff/Hoeffding) need the MGF or boundedness — mention if asked, but those live beyond core.

• Convex φ: E[φ(X)]≥φ(E[X]). Concave: inequality flips.
• Equality iff X is constant a.s. or φ is linear on X's support.
• Consequences: E[X²]≥(E[X])² (so Var≥0), E[1/X]≥1/E[X] for X>0, E[ln X]≤ln E[X].
• A function of the average ≤ the average of a convex function — convexity adds value to dispersion.
• Finance hook: option convexity (gamma) means E[payoff(S)]>payoff(E[S]); volatility is valuable.

• Symmetry: if outcomes are exchangeable, P(A before B)=½; the k-th of n shuffled items is uniform over positions.
• States & recursion: define E from each state, condition on the first step, solve the linear system.
• Poisson-process / memoryless framing: 'who arrives first' among independent exponentials is proportional to rates.
• Before computing, ask: can symmetry, linearity, or a one-step recursion collapse this?
• Reflection/complement: count the easy complement when the event itself is messy.

• Var(aX+bY) = a²Var(X)+b²Var(Y)+2ab·Cov(X,Y).
• Law of total variance: Var(X)=E[Var(X|Y)]+Var(E[X|Y]).
• Tower: E[X]=E[E[X|Y]].
• Bivariate normal: E[Y|X=x]=μ_Y+ρ(σ_Y/σ_X)(x−μ_X).

• An estimator θ̂ is a function of the sample; it has its own sampling distribution.
• MSE = bias² + variance — MSE(θ̂)=E[(θ̂−θ)²]=(E[θ̂]−θ)²+Var(θ̂). The whole tradeoff lives here.
• Unbiased: E[θ̂]=θ for all n. Consistent: θ̂→θ in probability as n→∞. Different properties — neither implies the other.
• Efficient: smallest variance among a class; Cramér–Rao gives the floor Var(θ̂)≥1/I(θ) for unbiased estimators (I=Fisher info).
• In quant work a slightly biased, lower-variance estimator (shrinkage) often beats unbiased — minimize MSE, not bias.

• Sample variance s²=Σ(xᵢ−x̄)²/(n−1) is the unbiased estimator of σ²; dividing by n underestimates.
• x̄ is fit from the data, so deviations from x̄ are systematically smaller than deviations from the true μ.
• Mechanically: only n−1 deviations are free — they must sum to 0 (one degree of freedom is spent estimating the mean).
• Caveat: s (the std, not s²) is still slightly biased by Jensen — E[s]<σ — because √ is concave. Unbiasedness doesn't survive nonlinear transforms.
• Bias ~1/n, so it's negligible for large samples and matters mainly for small n.

• Pick the parameter that makes observed data most probable: θ̂=argmax L(θ)=argmax Πf(xᵢ;θ). Maximize the log-likelihood — sums beat products.
• Solve ∂ logL/∂θ = 0 (the score equation); check second order.
• Invariance: MLE of g(θ) is g(θ̂) — e.g. MLE of σ is √(MLE of σ²).
• Asymptotics: under regularity, θ̂ is consistent and √n(θ̂−θ)→N(0, 1/I(θ)) — attains the Cramér–Rao bound asymptotically (efficient).
• MLE can be biased in finite samples: Normal MLE of variance divides by n, not n−1.

• Method of moments (MoM): set sample moments = theoretical moments, solve for parameters. Simple, no optimization, but can be inefficient or give out-of-range estimates.
• MAP: argmax p(θ|data) ∝ argmax L(θ)·p(θ) — MLE weighted by a prior; maximizes the log-posterior logL+log prior.
• MAP = MLE + a regularizing prior; a flat (uniform) prior makes MAP = MLE.
• Gaussian prior on θ ⇒ MAP is ridge-style shrinkage toward the prior mean; Laplace prior ⇒ sparsity. Priors fight overfitting on thin data.
• MAP is a point estimate, not the full posterior — it ignores posterior spread/skew (the mode ≠ mean in general).

• For iid Xᵢ with finite mean μ and variance σ²: √n(X̄−μ)/σ → N(0,1), regardless of the underlying shape.
• SE shrinks like 1/√n: SE(X̄)=σ/√n. Quadruple the data to halve the error.
• SE = std of an estimator's sampling distribution; population std describes spread of one draw. Don't confuse them.
• What breaks CLT: infinite/undefined variance (heavy tails, e.g. Cauchy), strong dependence/autocorrelation, non-identical distributions. Markets have all three — convergence is slow and SE understated.
• Convergence rate depends on skew/kurtosis (Berry–Esseen ~1/√n); fat tails need much larger n before Normal is safe.

• Set up H₀ (null) vs H₁; pick a statistic; reject if it's extreme under H₀.
• p-value = P(data this extreme or more | H₀ true) — NOT P(H₀ true).
• Type I (α, false positive): reject a true H₀. Type II (β): fail to reject a false H₀. Power = 1−β: detect a real effect.
• Power rises with effect size, n, and α; it falls with noise. Lowering α to cut false positives raises β — a direct tradeoff.
• p < α is significance, not importance: huge n makes trivial effects 'significant'. Report effect size + CI, not just the p.

• Confidence (frequentist): the procedure covers the true fixed θ 95% of the time over repeated samples. θ is fixed; the interval is random.
• A 95% CI does NOT mean 95% probability θ is in this interval — θ is not random in the frequentist view.
• Credible (Bayesian): given a prior + this data, P(θ∈[a,b]|data)=0.95. Here θ is treated as random — the intuitive statement, but it needs a prior.
• They coincide with flat priors in simple models, but diverge when the prior is informative or the likelihood is skewed.
• CI from CLT: x̄ ± z·SE (z≈1.96 for 95%). Width ~1/√n.

• Test m hypotheses at α each and the chance of ≥1 false positive explodes: P(≥1)=1−(1−α)^m.
• FWER (family-wise error): P(any false positive). Bonferroni controls it — use threshold α/m. Simple, but conservative → low power.
• FDR controls the expected fraction of discoveries that are false — far more power when you test thousands of signals.
• Benjamini–Hochberg: sort p-values p₍₁₎≤…≤p₍ₘ₎, find largest k with p₍ₖ₎ ≤ (k/m)·q, reject all up to k. Controls FDR at q.
• Quant relevance: data-mining 1000s of factors guarantees spurious 'alpha'. Correction (or hold-out / lower threshold) is mandatory.

• Estimate an estimator's sampling distribution by resampling the data with replacement B times, recomputing the statistic each time.
• The empirical distribution stands in for the unknown population — get SE/CI/bias with no closed-form formula.
• Uses: SE and percentile CIs for messy statistics (median, Sharpe, max drawdown), bias estimation, when CLT/normality is doubtful.
• Fails / needs care: dependent data (use block bootstrap to preserve autocorrelation), extreme order statistics (max/min), tiny samples, and heavy tails where moments don't exist.
• Percentile CI: take the 2.5% and 97.5% quantiles of the B bootstrap statistics.

• Weak (covariance) stationarity: constant mean E[Xₜ]=μ, constant variance, and autocovariance γ(s,t) depends only on lag |t−s|, not on t.
• Strict stationarity: the full joint distribution is shift-invariant. Strict + finite 2nd moment ⇒ weak; weak does NOT imply strict (except Gaussian, where they coincide).
• Most time-series models (AR/MA/ARMA) assume weak stationarity — it's what makes the ACF and forecasts well-defined.
• Prices are typically non-stationary (random walk); log-returns are usually treated as (approximately) stationary.
• Stationarity = statistical properties don't drift with time; it's the precondition for estimating a stable autocovariance structure.

• ACF ρ(k)=γ(k)/γ(0): correlation between Xₜ and Xₜ₋ₖ including intermediate lags.
• PACF: correlation at lag k after regressing out lags 1..k−1 — the 'direct' effect.
• MA(q): ACF cuts off after lag q; PACF tails off (decays).
• AR(p): PACF cuts off after lag p; ACF tails off.
• ARMA(p,q): both tail off — order not readable directly; use AIC/BIC.
• Significance band ≈ ±1.96/√n under the white-noise null.
• Cut-off in ACF ⇒ MA order; cut-off in PACF ⇒ AR order. This duality is the classic identification trick.

• AR(p): Xₜ=c+Σφᵢ Xₜ₋ᵢ+εₜ — regress on own past. Stationary iff roots of 1−Σφᵢzⁱ=0 lie outside the unit circle.
• MA(q): Xₜ=μ+εₜ+Σθⱼ εₜ₋ⱼ — finite memory, always stationary; invertible iff MA roots outside unit circle.
• ARMA(p,q): combines both; parsimonious vs a long pure AR or MA.
• An invertible MA(∞) ⇔ AR(∞): an AR(1) Xₜ=φXₜ₋₁+εₜ with |φ|<1 equals Σφʲεₜ₋ⱼ.
• AR = momentum on own past; MA = shocks with finite echo. Stationarity ↔ AR roots; invertibility ↔ MA roots.

• Random walk: Xₜ=Xₜ₋₁+εₜ (φ=1) — shocks permanent, variance ∝t, best forecast is last value, not stationary, not predictable.
• Mean reverting (AR(1), |φ|<1): shocks decay, pulled back to mean c/(1−φ); half-life of a shock = ln(0.5)/ln(φ).
• The whole question 'is this tradable?' often reduces to: is φ meaningfully below 1? That's a unit-root test.
• Ornstein–Uhlenbeck is the continuous-time analog: dXₜ=θ(μ−Xₜ)dt+σdWₜ; θ>0 ⇒ reversion.
• RW = unpredictable, trade nothing; mean reversion = a fade signal with a measurable half-life. The line between them is φ=1.

• Test H₀: φ=1 (unit root, non-stationary) vs H₁: φ<1 (stationary). Run ΔXₜ=γXₜ₋₁+εₜ, test γ=0 where γ=φ−1.
• ADF adds lagged ΔX terms to absorb serial correlation; variants include drift/trend.
• Distribution under the null is NOT standard t — use Dickey–Fuller critical values (more negative than normal). Reject (very negative stat) ⇒ stationary.
• KPSS flips the null (stationary is H₀); pairing ADF + KPSS guards against low-power conclusions.
• Unit-root tests have low power: failing to reject H₀ is weak evidence, not proof of a unit root. Don't over-trust 'looks non-stationary'.

• ARIMA(p,d,q): difference d times to reach stationarity, then fit ARMA(p,q) to ΔᵈX.
• d=1 handles a stochastic trend (unit root); a deterministic linear trend is better removed by regression, not differencing.
• Choose d from unit-root tests + ACF (slowly decaying ACF ⇒ difference); over-differencing injects spurious negative MA structure.
• Order selection: minimize AIC/BIC, check residuals are white (Ljung–Box).
• d is for unit roots, not for everything — over-differencing manufactures a unit MA root and inflates variance.

• Stylized fact: returns are ~uncorrelated but |returns| / returns² are strongly autocorrelated — big moves cluster. Mean is unpredictable; variance is.
• ARCH(1): σ²ₜ=ω+α ε²ₜ₋₁. GARCH(1,1): σ²ₜ=ω+α ε²ₜ₋₁+β σ²ₜ₋₁ — today's variance from yesterday's shock and yesterday's variance.
• Persistence =α+β; <1 for stationarity. Unconditional variance =ω/(1−α−β). Equity α+β is often near 1 (long memory in vol).
• Captures fat tails and clustering; εₜ=σₜ zₜ with zₜ iid. EGARCH/GJR add the leverage (asymmetric) effect.
• GARCH models the conditional variance, not the mean — it's a vol forecaster, not an alpha signal. α+β is the vol-persistence dial.

• Two I(1) series are cointegrated if a linear combo Yₜ−βXₜ is I(0) (stationary) — they share a stochastic trend and a stable long-run spread.
• Engle–Granger: regress Y on X, ADF-test the residual (spread) for stationarity. Johansen: multivariate, tests rank / multiple cointegrating vectors.
• Trade: the stationary spread mean-reverts — short the spread when high, long when low; size by z-score, exit near mean.
• Correlation ≠ cointegration: two series can be highly correlated short-term yet drift apart (no shared trend).
• Cointegration is a long-run anchor between non-stationary series; the tradable object is the stationary spread, not either leg.

• Lookahead: using data not available at decision time — using a bar's close to trade within that bar, or a same-day fundamental released after the close.
• Survivorship bias: testing only names that survived; delisted/bankrupt tickers dropped ⇒ inflated returns.
• Leakage via fitting: normalizing/standardizing or selecting features on the full sample (incl. future) before splitting — z-scores must use only trailing data.
• Respect point-in-time data and realistic lag: signal at t trades at t+1 open; restatements and index recompositions are forward-only.
• Every transform must use only information available at the bar it acts on. The classic failure: a trailing window that silently peeks at the future.

• quoted spread = ask − bid; half-spread = (ask−bid)/2. Often quoted relative: (ask−bid)/mid.
• effective spread = 2·D·(P_trade − mid), D=+1 buy, −1 sell. Measures what you ACTUALLY paid vs mid at trade time — captures price improvement and crossing.
• realized spread = 2·D·(P_trade − mid_{t+Δ}) uses the mid a few minutes later — what the maker KEEPS after the price moves against them.
• effective = realized + price impact: the part of the effective spread that isn't realized is adverse-selection cost to the maker.

• Limit order = provides liquidity, rests in book, earns spread but bears adverse selection + non-execution risk. Market order = takes liquidity, pays spread, certain fill.
• Most venues use price–time priority: best price first, then FIFO by arrival. Queue position is an asset — being early in the queue at the best bid is valuable optionality.
• Maker–taker fees: passive fills earn a rebate, aggressive fills pay a fee. This distorts the true spread: effective cost to a taker = spread + taker fee.
• A resting limit order is a free option written to the market — informed flow picks it off (adverse selection).
• Hidden/iceberg orders sacrifice time priority for non-display; pro-rata matching (common in some futures) changes optimal order sizing vs FIFO.

• Market maker faces informed traders (know true value V) and noise traders (random). MM is competitive & risk-neutral → zero expected profit → quotes are conditional expectations.
• ask = E[V | buy order], bid = E[V | sell order]. The spread exists EVEN with zero inventory cost and zero fees — purely from information asymmetry.
• Each trade is a signal: a buy revises beliefs up, a sell down. Quotes are a martingale updated via Bayes; prices converge to V as trades arrive.
• Spread = compensation for trading against possibly-informed counterparties; more informed flow (higher α) ⇒ wider spread.
• Contrast with inventory models: G–M spread is informational, not risk-bearing.

• Single informed trader, noise traders submit order flow u, one market maker sets price from total flow x+u. Linear equilibrium: price = p₀ + λ·(order flow).
• λ is Kyle's lambda — price impact per unit of net order flow; 1/λ is market DEPTH (Kyle calls it the inverse of liquidity).
• Single-auction closed form: λ = (1/2)·√(Σ₀/σ_u²) where Σ₀ = variance of value, σ_u² = noise-trade variance. More noise traders ⇒ smaller λ ⇒ deeper market.
• In that one-shot model the informed trader sizes to avoid full revelation: in equilibrium exactly half the private-info variance is impounded into price (Σ₁ = Σ₀/2).
• Empirically λ is estimated by regressing price changes on signed order flow: ΔP = λ·(signed volume) + ε.

• Define volume imbalance at top of book: I = (Q_bid − Q_ask)/(Q_bid + Q_ask) ∈ [−1,1].
• Strong positive contemporaneous & short-lead relation: high bid size ⇒ next mid tick more likely UP. The size-weighted mid formalizes this.
• Size-weighted mid (Stoikov's microprice proxy): P_micro = (Q_ask·bid + Q_bid·ask)/(Q_bid+Q_ask) — weights the side with LESS size, i.e. tilts toward where the book is thin (the likely move).
• Imbalance predicts the next move because thin side fills first; signal decays in seconds and is mostly arbitraged at liquid names.
• Caveat: spoofing/flickering quotes contaminate raw imbalance; predictive power is regime- and tick-size-dependent.

• MM maximizes exponential (CARA, risk aversion γ) utility of terminal wealth while holding inventory q over horizon T−t.
• Reservation price r = s − q·γ·σ²·(T−t) — the mid SHIFTED away from current inventory. Long inventory (q>0) pulls quotes DOWN to encourage selling.
• Optimal total spread: δ_total = γσ²(T−t) + (2/γ)·ln(1 + γ/k), where k governs order-arrival intensity λ=A·e^{−kδ}.
• Quotes set symmetrically around r, NOT the mid: bid = r − δ/2, ask = r + δ/2. This skews fills to mean-revert inventory toward zero.
• As t→T the inventory term vanishes; quotes recenter on the mid.

• Distinct from adverse selection: a MM with finite risk capacity charges a spread to be compensated for holding unwanted, undiversified inventory exposure.
• Quotes are shaded around the true value by inventory: after a buy (MM now SHORT) it raises quotes to attract a seller; after a sell it lowers them. Mid is pushed AWAY from the true value temporarily.
• Inventory effects induce transient (mean-reverting) price pressure; adverse-selection effects are permanent. This is the key to decomposing spread components.
• Larger position, higher volatility, shorter unwind horizon, higher funding cost ⇒ wider inventory spread.
• Three classic components: order-processing (fixed cost), inventory-holding, adverse-selection.

• Permanent impact = information content of the trade, stays in the price (≈ linear in size, Kyle's λ). Temporary impact = liquidity-consumption cost that decays after you stop trading.
• Empirical square-root law: cost of executing a metaorder ≈ Y·σ·√(Q/V) — impact grows with the SQUARE ROOT of participation (Q = order size, V = daily volume, σ = vol).
• Almgren–Chriss execution: temporary impact often modeled ∝ (trade rate), permanent ∝ (size); optimal schedule trades off impact vs timing (volatility) risk.
• Concavity matters: doubling order size does NOT double cost — splitting and stretching execution reduces impact but adds price risk.

• TWAP: slice evenly over time — simple, predictable, ignores volume profile (vulnerable to gaming, bad when volume is U-shaped).
• VWAP: match the day's volume distribution (front-load opening/closing humps). Benchmark = Σ pᵢvᵢ / Σ vᵢ; beating VWAP means trading better than the average participant.
• Implementation Shortfall (Perold): IS = (paid − decision-price) on executed + opportunity cost on unexecuted. The honest all-in benchmark: it charges you for delay, impact, fees, AND missed fills.
• VWAP/TWAP measure execution quality vs the market; IS measures the total cost of the DECISION — the only one that penalizes not-trading.
• Aggressive (front-loaded) schedules cut timing risk but raise impact; IS-optimal schedules solve this trade-off explicitly (Almgren–Chriss).

• Big-O is an upper bound on growth as n→∞; drop constants and lower-order terms.
• Sum rule: sequential blocks → take the max, O(n)+O(n²)=O(n²). Product rule: nested loops multiply, O(n)·O(m)=O(nm).
• Recurrences via Master theorem: T(n)=2T(n/2)+O(n)→O(n log n) (mergesort); T(n)=2T(n/2)+O(1)→O(n) (heapify-style).
• Logs from halving (O(log n) binary search) or from balanced-tree depth; base of the log is a constant, so omit it.
• Watch hidden costs: string concat, slicing, and in on a list are each O(n) inside a loop → quietly O(n²).

• Average O(1) insert/lookup; degrades to O(n) when keys collide into one bucket or the table never resizes.
• Collision handling: chaining (linked list/bucket per slot) vs open addressing (probe to next slot). Load factor α = items/buckets drives performance.
• Resize (rehash) when α exceeds a threshold; this is what makes growth amortized O(1), not per-op O(1).
• Degradation triggers: adversarial keys all hashing to one bucket, a weak hash function, or hashing mutable objects whose value changes after insertion.
• Sets/dicts give O(1) membership; ordered structures (balanced BST) give O(log n) but keep sorted order and range queries.

• All average O(n log n); they differ on worst case, stability, memory, and constant factors.

• 	avg	worst	space	stable
  quicksort	n log n	n²	O(log n)	no
  mergesort	n log n	n log n	O(n)	yes
  heapsort	n log n	n log n	O(1)	no

• Quicksort worst case n² hits on bad pivots (already-sorted with naive first-element pivot); randomized or median-of-three pivots fix it in practice.
• Mergesort guarantees n log n and is stable → preferred for linked lists and external/disk sorts; cost is the O(n) auxiliary buffer.
• Quicksort wins on arrays despite equal asymptotics due to cache locality and in-place partitioning (small constants).

• A binary heap gives O(1) peek-min, O(log n) push/pop; build-heap from n items is O(n), not O(n log n).
• Array-backed: parent of i is (i−1)/2, children 2i+1 and 2i+2; no pointers needed.
• Top-k largest of a stream: keep a min-heap of size k; push, then pop the smallest if size>k. Cost O(n log k), space O(k).
• Use a max-heap to repeatedly extract the largest; use two heaps (max-heap of low half + min-heap of high half) to track a running median.
• Heapsort = build-heap then repeatedly extract; in-place but not stable and worse cache behavior than quicksort.

• Replace an O(n²) nested scan with one linear pass by moving two indices that never backtrack.
• Opposite-ends two-pointer needs a sorted array or a monotonic property (e.g. pair-sum: move left up if sum too small, right down if too big).
• Sliding window fits contiguous subarray/substring problems: expand the right edge, shrink the left while a constraint is violated. Amortized O(n) since each index enters and leaves once.
• Fast/slow pointers detect cycles and find midpoints in a single pass with O(1) extra space (Floyd).
• Pitfall: the window technique assumes monotonic feasibility (e.g. all-positive values); negatives can break the shrink invariant — switch to prefix-sum + hash.

• Hash set = O(n) time / O(n) space; sort-then-scan = O(n log n) time / O(1) extra; pick by whether order, memory, or stability matters.
• A single pass with a seen-set preserves first-seen order and is fastest, but needs space proportional to distinct items — bad for huge/streaming data.
• Sort then drop adjacent equals uses no extra structure but destroys original order and is slower.
• Find duplicates without extra space when values are bounded in [1,n]: index-as-hash (negate arr[abs(x)−1]) or cycle detection on the value-as-pointer graph.
• At scale (data won't fit in memory): external sort, or approximate membership with a Bloom filter (false positives, no false negatives).

• Sample k items uniformly from a stream of unknown length in one pass, O(k) memory.
• Algorithm R: keep the first k; for the i-th item (i>k) keep it with probability k/i, evicting a uniformly random current holder.
• Correctness: induction shows every seen item retains probability k/n after n items — the early-vs-late asymmetry exactly cancels.
• k=1 case: replace the held item with probability 1/i; trivial to state and a common warm-up.
• Use it when you can't store or count the data first (logs, ticks, network streams); weighted variants use the exponential-jump (A-ExpJ) trick.

• DP = overlapping subproblems + optimal substructure; define the state, the transition, the base case, and a valid evaluation order.
• Top-down memoization: recursion + cache; only computes reachable states, easy to write. Bottom-up tabulation: iterative fill, no recursion overhead, enables space rolling.
• Rolling array: if a transition only reads the previous row, keep O(width) instead of O(n·width) memory.
• Classic templates: knapsack (weight-capacity state), longest common subsequence (2-D grid), edit distance, coin change (min-count), interval DP.
• Pitfall: greedy fails when a locally optimal choice blocks a global optimum — DP enumerates all consistent choices; prove substructure before trusting greedy.

• Most interview problems are a known pattern in disguise; match the signature first, then code.
• "Sorted array / find a pair or bound" → two pointers or binary search.
• "Contiguous subarray/substring with a constraint" → sliding window or prefix-sum + hash.
• "k largest/smallest, or running order statistic" → heap (size-k or two-heap median).
• "Count/optimize over choices with reuse" → DP; "min answer satisfying a monotonic predicate" → binary search on the answer.
• "Membership / first duplicate / group-by-key" → hash set/map; "cycle or midpoint in a list" → fast-slow pointers.

• Before computing, restate the rules out loud and ask what's being optimized — half of teasers are won by clarifying constraints.
• Try the smallest / most extreme case first: n=1, n=2 often reveals the pattern or invariant.
• Hunt for an invariant (something that never changes) or a monovariant (something that only moves one way) — these prove impossibility or bound the answer.
• Work backward from the end state when the last move is forced (induction, endgames, pirate splits).
• Think out loud and narrate your search — the interviewer scores your process, not just the final number.

• If every legal move flips a quantity by a fixed parity, the reachable states are exactly those matching that parity — use it to prove a goal is impossible.
• Checkerboard coloring: a domino always covers one black + one white square, so a board with unequal colors can't be tiled.
• Mutilated chessboard: remove two opposite (same-color) corners → 32 vs 30 squares → no domino tiling.
• Light-switch / coin-flip puzzles: track the parity of "heads" or "on" switches; an odd invariant blocks the all-off state.
• Splitting a coin into two known-count groups: separate N coins from the dark, flip those N — both groups end with equal heads regardless of which were heads.

• One announced parity bit lets everyone behind deduce their own color — the first speaker sacrifices himself to broadcast the XOR of all hats he sees.
• N prisoners in a line, each sees only those ahead; back-most counts (say) red hats mod 2 and shouts that parity.
• Each subsequent prisoner counts reds still ahead, compares to the running parity announced, and infers his own hat.
• Guarantees N−1 saved; the first has a 50% guess. No probability needed — it's pure parity bookkeeping.
• Generalizes to colors mod k: announce the sum of all visible hats mod k.

• A balance has 3 outcomes per weighing (left<right, =, >), so k weighings distinguish at most 3ᵏ states — set up that information budget first.
• 12 coins, one fake of unknown direction: 24 possibilities < 3³=27, so 3 weighings suffice; design each weighing to split outcomes as evenly as possible.
• Classic 3-weighing 12-coin split: weigh 4 vs 4, then branch on the result, keeping every outcome equally informative.
• A one-pan scale (reads exact weight) gives far more info — that's the regime for the bottle-counterfeit-coin puzzle (take 1,2,3,… coins).
• Always count outcomes vs states before constructing the scheme; if states > 3ᵏ it's provably impossible.

• To identify 1 poisoned item among N with parallel yes/no testers, each item gets a binary ID and tester i drinks every item whose bit i is 1 — needs ⌈log₂N⌉ testers.
• 1000 bottles, 1 poison, one test round: 2¹⁰=1024 ≥ 1000, so 10 testers; the pattern of deaths reads off the poisoned bottle's 10-bit index.
• Key requirements: tests run in parallel (one round) and the result is per-tester binary (sick / not).
• If you have multiple sequential rounds instead, the budget grows multiplicatively — re-derive the base accordingly.
• Same trick labels prisoners or switches: assign IDs, let each "channel" carry one bit.

• When the last decision is forced, solve the final subgame first and induct backward — each player anticipates that everyone after them plays optimally.
• Pirate split (5 pirates, 100 coins, ≥50% incl. proposer's own vote needed, else proposer dies): solve the 2-pirate case, then 3, 4, 5.
• With 2 left, the senior keeps all (his own vote = 50%); knowing that, with 3 the proposer buys the cheapest vote with 1 coin, etc.
• Result for 5: proposer keeps 98, gives 1 each to the two pirates who'd get nothing in the next subgame.
• Pirates are rational, greedy, and prefer killing only when indifferent — clarify the tie-break rule before answering.

• A Nim position is losing for the player to move iff the XOR (nim-sum) of all pile sizes is 0; otherwise move to make it 0.
• Identify P-positions (previous player wins / mover loses) — these are the targets you hand your opponent.
• Winning move: pick a pile, reduce it so the total XOR becomes 0; such a move always exists when XOR ≠ 0.
• For non-Nim games, compute Grundy numbers (mex of reachable positions' Grundy values); a sum of games XORs their Grundy values (Sprague–Grundy).
• Misère Nim differs only near the end: play normal Nim until all heaps are size 1, then flip parity.

• To pick the single best of N candidates seen one-at-a-time with no recall, reject the first ~N/e (37%) automatically, then take the first one better than everyone so far.
• The first phase only calibrates a threshold (the best-so-far); the second phase commits on the first record-breaker.
• Probability of landing the very best converges to 1/e ≈ 37% as N grows — cite the result; the integral derivation lives in Probability.
• Variants change the cutoff: maximizing expected rank, or allowing a few picks, shifts the threshold — state which objective you're optimizing.
• Watch the framing trap: this maximizes P(get the absolute best), not expected value of the chosen candidate.

• Each prisoner follows the cycle: open the box labeled with his number, then the box numbered by the slip he finds, repeating — survival hinges on no permutation cycle exceeding 50.
• 100 prisoners, boxes hold a random permutation of 1–100; each may open 50 boxes and must find his own number; all must succeed.
• Naive random search → survival ≈ (1/2)¹⁰⁰, essentially zero. Cycle-following ties everyone's fate to one event: "longest cycle ≤ 50."
• That event's probability is about 31% (≈ 1 − ln 2 in the limit) — cite it; the harmonic-sum derivation belongs to Probability.
• The trick is that following slips means a prisoner traverses exactly the cycle containing his own number, and he finds it iff that cycle has length ≤ 50.

• x% of y equals y% of x — swap to whichever is easier.
• Hard: 16% of 25. Swap: 25% of 16 = 4.
• Build any percent from 10% (move decimal), 5% (half of 10%), 1% (move twice).
• Basis points: 1bp = 0.01% = 0.0001; 100bp = 1%.
• Tip-style: 15% = 10% + 5%; 17.5% = 10%+5%+2.5%.

• Memorize eighths, sixteenths, and 1/7 — they recur in odds, ticks, and yields.
• Halving chain: 1/2=.5, 1/4=.25, 1/8=.125, 1/16=.0625.
• Sixteenths: 3/16=.1875, 5/16=.3125, 7/16=.4375 (odd k: k/16).
• Sevenths cycle 142857: 1/7=.142857, 2/7=.285714, … (rotate the block).
• Useful: 1/3=.3̄, 1/6=.16̄, 1/9=.1̄, 1/11=.0909, 1/12=.0833.

• Ends-in-5 shortcut: n5² = n(n+1) followed by 25. So 35² = 3·4|25 = 1225.
• Near a base b: n² = (n+d)(n−d) + d² where d = n−b.
• Near 50: 53² = (50+3)² → 2500 + 100·3 + 9 = 2809.
• Near 100: 97² = (100−3)² = 10000 − 600 + 9 = 9409.
• General: (a±b)² = a² ± 2ab + b² — pick a as a round anchor.

• For symmetric pairs, ab = (mid)² − (gap)².
• 17×19 = 18² − 1² = 324 − 1 = 323; 38×42 = 40² − 2² = 1600 − 4 = 1596.
• ×11: write the digits with their sum between, carrying: 11×34 = 3|3+4|4 = 374.
• ×5 = ×10 ÷2; ×25 = ÷4 ×100; ×9 = ×10 − itself.
• Break-apart: 23×14 = 23×10 + 23×4 = 230 + 92 = 322.

• Pair digits from the decimal point; each pair → one result digit, so count pairs to fix the magnitude.
• Anchor squares: √2≈1.414, √3≈1.732, √5≈2.236, √7≈2.646.
• √10≈3.162 (= √2·√5); √12 = 2√3 ≈ 3.464.
• Refine with one Newton step: √S ≈ (g + S/g)/2 for guess g.
• Scaling: √(100x) = 10√x; move the decimal in pairs, not singly.

• Rule of 72: doubling time ≈ 72 / rate(%); the pure log answer is ln2×100 ≈ 69.3, but 72 corrects upward for discrete compounding and has more clean divisors.
• Near-exact at 8%: 72/8 = 9.0 vs true 9.01 yr.
• Slightly long at 7%: 72/7 = 10.29 vs true 10.24 yr.
• Use 69–70 for continuous compounding (ln2 = .693); 72 has more clean divisors.
• Tripling: from ln3 ≈ 1.10, time ≈ 110/rate (e.g. 6% → ~18 yr).

• Binomial approximation: (1+x)ⁿ ≈ 1 + nx for small x — but the dropped term is +n(n−1)x²/2, always positive, so you under-count.
• +x then −x = (1+x)(1−x) = 1 − x² — always a net loss of x².
• Compounding beats simple: 0.5%/mo → 1.005¹² = 1.0617 (6.17%, not 6%).
• Returns chain multiplicatively: total = ∏(1+rᵢ) − 1, never add unless tiny.
• Small-return shortcut: sum the logs, ln(1+r) ≈ r.

• For small x: eˣ ≈ 1 + x + x²/2 and ln(1+x) ≈ x − x²/2.
• Key logs: ln2 ≈ .693, ln10 ≈ 2.303; log₁₀2 = .301, log₁₀3 = .477, log₁₀7 = .845.
• Get the rest by addition: log₁₀5 = 1 − .301 = .699; log₁₀6 = .301+.477 = .778.
• e ≈ 2.718; e² ≈ 7.39; doubling-decibel sense: +3dB ≈ ×2 since 10^.3 ≈ 2.
• Convert bases: ln x = 2.303 · log₁₀ x.

• Daily vol → annual: ×√252 ≈ 16, so 1% daily vol ≈ 16% annual (because 16²=256≈252).
• Monthly → annual vol: ×√12 ≈ 3.46; weekly: ×√52 ≈ 7.2.
• Sharpe annualizes the same way: daily Sharpe ×√252, monthly ×√12.
• Volatility scales with √time, return scales with time — that gap is why Sharpe grows.
• P&L: notional × move; in bps, $X × bp/10000.

• Dot product: u·v = Σ uᵢvᵢ = ‖u‖‖v‖cos θ.
• u·v = 0 ⟺ vectors are orthogonal (⊥).
• Cauchy–Schwarz: |u·v| ≤ ‖u‖‖v‖.

• Not commutative: AB ≠ BA in general.
• Associative & distributive: (AB)C = A(BC), A(B+C)=AB+AC.
• (AB)ᵀ = BᵀAᵀ and (AB)⁻¹ = B⁻¹A⁻¹ (order flips).

• Orthogonal matrix: QᵀQ = I, so Q⁻¹ = Qᵀ (cheap, stable).

• det A = 0 ⟺ singular (columns dependent, map collapses a dimension, no inverse).
• det(AB) = det A · det B; det(Aᵀ)=det A; det A = ∏ eigenvalues.
• 2×2: ad−bc. 3×3: cofactor expansion.

• Full rank n (square) ⟺ invertible ⟺ det ≠ 0.
• Rank-nullity: rank(A) + nullity(A) = #columns.

• Σλ = trace(A); ∏λ = det(A) — fast sanity checks.
• Then solve (A − λI)v = 0 for each eigenvector.

• Singular values = √ eigenvalues of AᵀA; rank = #nonzero σ. Basis for PCA and compression.
• Eckart–Young: the best rank-k approximation is the top-k truncation A_k = Σᵢ₌₁ᵏ σᵢuᵢvᵢᵀ — optimal in both spectral and Frobenius norm.
• Error ‖A−A_k‖₂ = σ_{k+1}, ‖A−A_k‖_F = √(Σ_{i>k} σᵢ²). Energy captured = Σᵢ₌₁ᵏσᵢ² / Σσᵢ² (scree / variance-explained).
• Storage drops from mn to k(m+n+1) — the win when σ decays fast.

• Eigendecomposition A=VΛV⁻¹ needs A square; V orthogonal only if A is symmetric (spectral theorem).
• SVD A=UΣVᵀ exists for ANY m×n matrix; U,V always orthonormal, σᵢ≥0.
• For symmetric PSD A: the two coincide — σᵢ=λᵢ, left/right singular vectors equal eigenvectors.
• General A: singular values are σᵢ=√(λᵢ(AᵀA)); eigenvalues of A can be complex/negative, σ never; σᵢ=|λᵢ| for any normal A (e.g. rotations), not only symmetric.
• Use eigen for square symmetric (covariance, quadratic forms); use SVD when rectangular, rank-deficient, or numerically nasty.

• κ(A)=σ_max/σ_min (2-norm); for symmetric, =|λ|_max/|λ|_min.
• Measures sensitivity: relative error in x solving Ax=b can be up to κ(A) × relative error in b or A.
• Rule of thumb: lose about log₁₀κ digits of accuracy; κ≈10¹⁶ in double precision means the answer is garbage.
• Normal equations square it: κ(AᵀA)=κ(A)² — why QR/SVD beats forming AᵀA for least squares.
• High κ = nearly singular = collinear features; fix with regularization or drop/orthogonalize columns.

• Angle between vectors: cos θ = (u·v)/(‖u‖‖v‖).
• Cross product (3D): u×v is ⊥ to both, with ‖u×v‖ = ‖u‖‖v‖sin θ = area of the parallelogram they span.
• u·v measures alignment (scalar); u×v measures perpendicular spread (vector).

• Line (2D): y = mx + b, or ax + by = c.
• Plane (3D): ax + by + cz = d, with normal vector n = (a,b,c).
• Point-to-line distance (2D): |ax₀+by₀−c| / √(a²+b²). Plane version uses √(a²+b²+c²).
• Perpendicular lines: slopes multiply to −1.

• Circle: (x−h)² + (y−k)² = r²; circumference 2πr, area πr².
• Sphere: (x−h)²+(y−k)²+(z−l)² = r²; surface 4πr², volume (4/3)πr³.
• Inscribed-angle theorem: an angle subtended by a diameter is 90°.

• Side ratios equal: a/a′ = b/b′ = c/c′.
• Areas scale as the square of the linear ratio; volumes as the cube.

• Circle (d=2): P = n/2ⁿ⁻¹.
• Sphere (d=3): P = (n² − n + 2)/2ⁿ.

• Midpoint: ((x₁+x₂)/2, (y₁+y₂)/2).
• Slope: (y₂−y₁)/(x₂−x₁).
• Section formula (ratio m:n): ((mx₂+nx₁)/(m+n), (my₂+ny₁)/(m+n)).
• Centroid of a triangle: average the three vertices.

• Distance = Pythagoras generalized: 3D box diagonal = √(l²+w²+h²).
• Equilateral triangle side a: height = (√3/2)a, area = (√3/4)a².

• Shoelace is the fastest area formula given coordinates — memorize it.
• Coordinates: Area = ½|x_A(y_B−y_C)+x_B(y_C−y_A)+x_C(y_A−y_B)|. Equivalent to ½|(B−A)×(C−A)| in 2D.
• Heron (sides only): s=(a+b+c)/2, Area=√(s(s−a)(s−b)(s−c)).
• Two sides + included angle: Area=½·a·b·sinθ.
• 3D triangle: Area=½‖(B−A)×(C−A)‖ — the cross-product magnitude is twice the area.
• Sign of the shoelace (before abs) gives orientation: + counterclockwise, − clockwise. Collinear ⟺ area 0.

• Turn "random" into a uniform point in a region; the probability is a ratio of measures (length/area/volume).
• Pick coordinates: independent uniform picks → a square/cube; an angle → arc length on a circle; a stick break → a simplex.
• Shade the event region, integrate or use geometry, divide by total measure: P = measure(event)/measure(space).
• Symmetry first — many answers fall out without integrating. Conditioning restricts the sample space, so recompute the denominator.
• Classics: broken-stick triangle 1/4 (each of x, y−x, 1−y must be < ½); expected distance between two uniform points on [0,1] = 1/3; Bertrand chord — pin down the sampling rule first, "random" is ambiguous.

• Projection of a onto b: (a·b/‖b‖²)·b; its length is |a·b|/‖b‖.
• Point P to line through A with direction d (any dim): dist = ‖(P−A) − proj_d(P−A)‖. In 2D/3D: ‖(P−A)×d‖/‖d‖.
• Point P to plane n·x=c: dist = |n·P − c|/‖n‖ (signed if you drop the abs — sign tells which side).
• Closest point on the line/plane = P minus the perpendicular component; reflect P by subtracting twice that component.
• Distance between two skew lines: |(A₂−A₁)·(d₁×d₂)|/‖d₁×d₂‖.

• Within ±1σ: 68.27%; ±2σ: 95.45%; ±3σ: 99.73%.
• Two-sided 95% ⇒ z = 1.96; 90% ⇒ z = 1.645; one-sided 95% ⇒ z = 1.645.
• Gaussian tail bound: P(Z > z) ≤ (1/(z√(2π))) e^(−z²/2) for z > 0.
• φ(0) = 1/√(2π) ≈ 0.3989; E|Z| = √(2/π) ≈ 0.798.

• Binomial → Poisson: n→∞, p→0, np→λ fixed ⇒ Binomial(n,p) → Poisson(λ). Rule of thumb: n ≥ 100, np ≤ 10.
• Sum of independent normals: N(μ₁,σ₁²)+N(μ₂,σ₂²) = N(μ₁+μ₂, σ₁²+σ₂²). Variances add; for differences too.
• Poisson ↔ Exponential: Poisson(λt) counts; inter-arrival gaps are Exponential(λ), iid.
• Lognormal = exp(Normal): if ln X ~ N(μ,σ²) then X is lognormal. Used for prices (always positive).
• CLT: (X̄ − μ)/(σ/√n) → N(0,1). Sums of iid finite-variance terms become Gaussian.
• Chi-square: Σ of k iid N(0,1)² = χ²(k). t(ν) = Z/√(χ²(ν)/ν).

• Survival: P(X > t) = e^(−λt); hazard rate is constant = λ.
• Min of independent exponentials: min(Exp(λ₁),…,Exp(λₙ)) ~ Exp(λ₁+…+λₙ).
• Competing risks: P(source i fires first) = λᵢ / Σλⱼ.

• Continuous Uniform(0,1): U₍ₖ₎ ~ Beta(k, n−k+1), mean k/(n+1); max mean n/(n+1), min mean 1/(n+1).
• Probability integral transform: F(X) ~ Uniform(0,1); inverse-cdf F⁻¹(U) generates any distribution.

• Max (k=m): E = m(N+1)/(m+1) — the German tank problem; invert for N̂ = max·(m+1)/m − 1.
• Sanity: m=1 → mean (N+1)/2, var (N²−1)/12 (one uniform draw); m=N → X₍ₖ₎=k exactly (the N−m factor kills the variance).
• With replacement (iid) there is no clean closed form — E[max] = N − N⁻ᵐ·Σⱼ₌₀^(N−1) jᵐ.

• Independent sums: MGFs multiply, so means and variances always add: E[ΣXᵢ]=ΣE[Xᵢ], Var(ΣXᵢ)=ΣVar(Xᵢ) (independence needed only for variance).
• Many families are closed under addition with FIXED parameters; memorize which.
• Beware: ratios/products are NOT additive, and the sum of two iid uniforms is triangular, not uniform.

• Probability integral transform: if U~Uniform(0,1) then X=F⁻¹(U) has CDF F. Conversely F(X)~Uniform(0,1).
• Inverse-CDF sampling needs a closed-form, invertible F.
• Exponential: solve U=1−e^(−λx) ⇒ X=−ln(U)/λ (use ln U; U and 1−U are both uniform).
• Normal (no closed-form F⁻¹): Box–Muller — Z₁=√(−2 ln U₁)·cos(2πU₂), Z₂=√(−2 ln U₁)·sin(2πU₂) are iid N(0,1).
• When F⁻¹ is intractable: acceptance–rejection or other transforms.

• Permutations: P(n,k) = n!/(n−k)!.
• Combinations: C(n,k) = n!/(k!(n−k)!), and C(n,k)=C(n,n−k).
• Multiset permutations (anagrams): n!/(n₁! n₂! … nₘ!).
• Circular arrangements of n distinct: (n−1)!.

• Pascal's rule: C(n,k)=C(n−1,k−1)+C(n−1,k).
• Row sum: Σ_k C(n,k) = 2ⁿ (subsets of an n-set).
• Alternating sum: Σ_k (−1)ᵏ C(n,k) = 0 for n ≥ 1.
• Vandermonde: Σ_j C(m,j)C(n,k−j) = C(m+n,k).
• Hockey stick: Σ_{i=r..n} C(i,r) = C(n+1,r+1).

• Nonnegative solutions to x₁+…+x_k = n: C(n+k−1, k−1).
• Strictly positive (each bin ≥ 1): C(n−1, k−1).
• With lower bounds, substitute yᵢ = xᵢ − Lᵢ and reduce n.

• Values: D₁=0, D₂=1, D₃=2, D₄=9, D₅=44.
• Dₙ/n! → 1/e ≈ 0.3679 fast — the "hat-check" limit.

• Counts: balanced parenthesizations of n pairs; lattice/Dyck paths (0,0)→(n,n) staying weakly below the diagonal; binary trees with n nodes; triangulations of an (n+2)-gon; non-crossing matchings of 2n points.
• Trigger: counting objects with a never-go-negative / never-cross constraint built from n up-steps and n down-steps.
• Derive by reflection (André): total paths C(2n,n) minus bad paths (touch above the diagonal), which biject to C(2n,n+1).

• One die: x+x²+…+x⁶. Two dice: square it; coefficient of xˢ = ways to roll sum s.
• 1/(1−x) = Σ xⁿ; 1/(1−x)ᵏ = Σ C(n+k−1, k−1) xⁿ (recovers stars-and-bars).
• Probability GF: E[zˣ]; for Poisson it is e^(λ(z−1)).

• First ask two questions: does order matter, and is repetition allowed?
• Order matters, no repeat: P(n,k)=n!/(n−k)!. Order matters, repeat: nᵏ.
• Order doesn't matter, no repeat: C(n,k)=n!/(k!(n−k)!). Order doesn't matter, repeat (multiset): C(n+k−1,k) — this is stars & bars.
• Distinct objects into groups of sizes k₁…kₘ (multinomial): n!/(k₁!k₂!…kₘ!).
• Pick the cell by (order?, repeat?) before reaching for any formula — most errors are choosing the wrong cell, not the wrong arithmetic.

• Seating n distinct people around a round table: fix one person to kill rotational symmetry, giving (n−1)!.
• If reflections also count as the same (a bracelet): divide by 2 more, (n−1)!/2 for n≥3.
• The principle: when k arrangements are all equivalent under a symmetry, divide the linear count by k — valid only when every orbit has the SAME size.
• Divide-by-symmetry only works cleanly when no arrangement is fixed by the symmetry; when some are (e.g. symmetric necklaces), use Burnside instead.
• Burnside (orbit-counting): distinct configs = average number of arrangements fixed by each symmetry, (1/|G|)·Σ|Fix(g)|.

• Stationary distribution π solves πP = π, Σπᵢ = 1.
• Ergodic (irreducible + aperiodic, finite) ⇒ unique π and Pⁿ → 1π regardless of start.
• Reversible if πᵢPᵢⱼ = πⱼPⱼᵢ (detailed balance) ⇒ such π is stationary.

• Pólya recurrence: recurrent in 1D and 2D, transient in 3D and higher.
• Gambler's ruin on {0,…,N}, fair: P(hit N before 0 | start i) = i/N; expected duration = i(N−i).
• Biased (up p, down q=1−p): ruin prob uses ratio r=q/p; P(reach N)=(1−rⁱ)/(1−rᴺ).

• For SRW, both Sₙ and Sₙ² − n are martingales.
• Using Sₙ²−n at the ruin stopping time recovers E[duration].

• W₀ = 0; independent increments; Wₜ − Wₛ ~ N(0, t−s).
• Continuous paths but nowhere differentiable.
• Cov(Wₛ, Wₜ) = min(s,t).
• Self-similar: W_{ct} =ᵈ √c · Wₜ. Scales as √t (the "square-root-of-time" rule).
• Quadratic variation over [0,t] = t (deterministic).

• N(t) ~ Poisson(λt); independent increments over disjoint intervals.
• Inter-arrival times iid Exponential(λ); n-th arrival time ~ Gamma(n, 1/λ).
• Superposition: independent rates λ₁+λ₂ ⇒ Poisson(λ₁+λ₂). Thinning by p ⇒ Poisson(λp).
• Given N(t)=n, the n arrival times are distributed as n iid Uniform(0,t) order statistics.

• Drift correction: log-return has mean (μ−½σ²)t, NOT μt.
• E[Sₜ] = S₀ e^(μt); Sₜ is lognormal.
• Var(Sₜ) = S₀² e^(2μt)(e^(σ²t) − 1).

• Mean: E[Xₜ] = μ + (X₀ − μ)e^(−θt) → μ.
• Stationary variance: σ²/(2θ); stationary law N(μ, σ²/(2θ)).
• Half-life of a shock: ln 2 / θ.

• ∫₀ᵗ f dW is defined for adapted, square-integrable f; it is a martingale with E[∫f dW]=0.
• Itô isometry: E[(∫₀ᵗ f dW)²]=E[∫₀ᵗ f² ds] — converts a stochastic integral's variance into an ordinary time integral.
• Multiplication rules: dW·dW=dt, dt·dW=0, dt·dt=0. This is why second-order terms survive in Itô's lemma.
• An Itô process dX=μ(X,t)dt+σ(X,t)dW with zero drift μ≡0 is a local martingale — a true martingale when σ is square-integrable (E[∫σ²ds]<∞).
• Drift = predictable trend; diffusion = the only term carrying randomness. Kill the drift to get a martingale.
• Integration by parts (no cross term unless both are Itô): d(XY)=X dY+Y dX+dX·dY.

• Under risk-neutral ℚ, discounted assets are martingales: S₀=E^ℚ[e^{−rT}S_T]; every tradable's drift becomes r.
• Girsanov: changing measure shifts the drift but leaves volatility and quadratic variation unchanged. W̃ₜ=Wₜ+∫₀ᵗ θ_s ds is a ℚ-Brownian motion.
• Radon–Nikodym density is an exponential martingale: dℚ/dℙ=exp(−∫θ dW−½∫θ² ds).
• Market price of risk θ=(μ−r)/σ is the drift adjustment that turns the real-world drift μ into r.
• Feynman–Kac: the PDE ∂_t V+μ ∂_x V+½σ² ∂_xx V−rV=0 with terminal data V(T,x)=payoff has solution V=E^ℚ[e^{−r(T−t)}payoff].
• Girsanov re-drifts; Feynman–Kac is the bridge between the pricing PDE and the discounted expectation.

• Reflection principle (running max): P(max_{s≤t} Wₛ ≥ a) = 2·P(Wₜ ≥ a) = 2Φ(−a/√t) for a>0.
• Hitting time τ_a = inf{t : Wₜ = a} has the Lévy (stable-½) density (a/√(2πt³)) e^(−a²/2t); heavy-tailed, so E[τ_a] = ∞ for driftless BM.
• τ_a is a.s. finite (1D BM is recurrent) but has infinite mean — it hits, but you cannot bound when.
• With drift Xₜ = μt + σWₜ: hitting a>0 is certain only if μ ≥ 0; if μ < 0, P(ever hit a) = exp(2μa/σ²) < 1.
• Two-sided exit (levels −b, a), no drift: P(hit a first) = b/(a+b).

• β₁ = Cov(x,y) / Var(x)  (slope = how much y moves per unit x)
• β₀ = ȳ − β₁x̄  (line passes through the mean point (x̄, ȳ))

• XᵀX β = Xᵀy  →  β = (XᵀX)⁻¹Xᵀy (when XᵀX is invertible)
• Residuals are orthogonal to every column of X: Xᵀε = 0

• R² never decreases when you add a regressor, even a useless one → it cannot be used for model selection.
• Adjusted R² = 1 − (1−R²)(n−1)/(n−k−1) penalizes extra predictors (k = number of predictors excluding the intercept); it can fall when a variable adds noise.
• R² says nothing about whether the model is correct, whether coefficients are causal, or whether predictions will generalize. High R² with bad residual patterns is still a bad model.

• t-test for a single coefficient: t = β̂ⱼ / SE(β̂ⱼ), df = n−k−1. Tests H₀: βⱼ = 0.
• F-test for joint significance: F = (R²/k) / ((1−R²)/(n−k−1)). Tests H₀: all slopes = 0. Use the nested form F = [(SSRᵣ−SSRᵤ)/q] / [SSRᵤ/(n−k−1)] to compare a restricted vs unrestricted model.
• Rule of thumb: |t| > 2 ≈ significant at 5% for moderate df.

• Confidence interval for the mean response E[y|x₀]: width ∝ √(Var(ŷ₀)).
• Prediction interval for a single new observation y₀: adds the irreducible error variance σ²: width ∝ √(σ² + Var(ŷ₀)).

• Detect with VIF: VIFⱼ = 1/(1−Rⱼ²), where Rⱼ² is from regressing xⱼ on the other predictors. VIF > 10 (Rⱼ² > 0.9) is a common red flag.
• Fixes: drop a redundant variable, combine into an index/PCA, or use ridge regression.
• It inflates variance but does NOT bias coefficients — predictions can still be fine.

• Heteroskedasticity (Var(εᵢ) changes with x): detect via residual-vs-fitted "funnel/fan" plot, Breusch–Pagan or White test. Fix: White/Huber heteroskedasticity-robust SEs (HC).
• Autocorrelation (errors correlated over time, common in finance): detect via Durbin–Watson (≈2 means none; near 0 = positive autocorrelation) or residual ACF plot. Fix: Newey–West (HAC) SEs, which correct for both heteroskedasticity and autocorrelation up to a chosen lag.

• log(p/(1−p)) = β₀ + β₁x, so p = 1/(1 + e^−(β₀+β₁x)) (sigmoid, always in (0,1)).
• e^βⱼ is the odds ratio — the multiplicative change in odds per unit increase in xⱼ. Fit by maximum likelihood, not least squares.

• Overfitting sign: train error ≪ test error. Cure with more data, fewer features, or regularization.
• k-fold CV: split into k folds, train on k−1, validate on the rest, average. Estimates out-of-sample error and tunes λ.
• Time-series: NEVER use random k-fold — it leaks the future into the past. Use walk-forward / expanding-window validation: always train on data strictly before the validation period. Also embargo/purge around the split to avoid overlap leakage.

• Rᵢ − R_f = α + β(R_m − R_f) + ε
• β = Cov(Rᵢ, R_m) / Var(R_m) — the slope; measures systematic (non-diversifiable) risk.
• α (intercept) = risk-adjusted excess return; a significantly positive α is "alpha." Extend to Fama–French: add SMB, HML, etc., as extra regressors → multivariate OLS with one β per factor.

• Non-spherical errors Var(ε)=σ²Ω (Ω≠I) leave OLS unbiased but no longer BLUE, and the textbook SE formula is wrong.
• GLS reweights: β̂_GLS=(XᵀΩ⁻¹X)⁻¹XᵀΩ⁻¹y — equivalent to OLS on data premultiplied by Ω^(−1/2) (whitening). It is BLUE when Ω is known.
• WLS = GLS for the diagonal (pure heteroskedasticity) case: weight each obs by wᵢ=1/Var(εᵢ), downweighting noisy points. Feasible GLS estimates Ω first, then plugs in.
• If you don't trust your model for Ω, keep OLS point estimates but fix the SEs: White/HC (heteroskedasticity) or Newey–West/HAC (also autocorrelation).
• Robust SEs change inference only, not β̂; WLS/GLS change both. Robust SEs are the default in practice because misspecifying Ω can make FGLS worse than OLS.

• FWL: in y=X₁β₁+X₂β₂+ε, the OLS estimate β̂₂ is unchanged if you instead (1) regress y on X₁ and take residuals ỹ, (2) regress X₂ on X₁ and take residuals X̃₂, then (3) regress ỹ on X̃₂.
• A multiple-regression coefficient is the bivariate slope on the part of that regressor orthogonal to all the others — "holding the others fixed" made precise.
• Explains why adding a regressor changes existing coefficients: it strips shared variation out (this is exactly OVB unwound).
• Justifies demeaning for an intercept (X₁=1 ⇒ partial out the mean) and within-transform for fixed effects — you needn't carry dummies in the design matrix.
• If X̃₂ has little variation left (X₂ well-explained by X₁), that coefficient's SE blows up — the same mechanism as multicollinearity/VIF.

• Under ε~N(0,σ²I), minimizing SSR is identical to maximizing the Gaussian likelihood — OLS = MLE when errors are normal, which is why OLS inherits MLE efficiency and the exact t/F distributions.
• MLE for σ² divides SSR by n (biased); OLS uses n−k−1 (k = predictors excluding the intercept) for unbiasedness. Normality is needed for exact small-sample t/F; large samples lean on the CLT instead.
• Spurious regression: regressing one independent random walk on another yields high R² and large t-stats by pure chance — the t-distribution is invalid because residuals are non-stationary (a unit root).
• Tell-tale sign: very low Durbin–Watson (≈0) alongside high R² ⇒ suspect spuriousness, not a real relationship.
• Fix: regress in differences (returns, not prices) or use cointegration/ECM when levels share a common stochastic trend.

• ITM: call S>K, put S<K — has intrinsic value.
• ATM: S≈K — maximum time value, maximum Γ and θ.
• OTM: call S<K, put S>K — all time value, expires worthless if unmoved.

• If LHS > RHS: sell the call, buy the put, buy stock, borrow Ke^(−rT) → lock riskless profit (conversion).
• Reverse mispricing → reversal.
• Parity is model-free: it holds by replication, independent of vol or distribution.

• Assumptions: GBM (lognormal S, constant σ), continuous frictionless trading, constant r, no jumps, no transaction costs.
• Failures: real returns have fat tails & jumps; vol is stochastic and clusters; this produces the vol smile/skew that flat-σ BS cannot fit. Traders invert BS to quote implied vol rather than price.

• Variance Risk Premium (VRP) = implied variance − expected realized variance, on average > 0.
• IV typically exceeds subsequent RV (option sellers are compensated for bearing crash/vol risk) → systematic short-vol carry, but with large negative skew (sell-vol blows up in crashes).
• Trading the spread: long straddle if you think RV will exceed IV; short straddle / variance if IV is rich.

• Equity skew drivers: crash-fear (demand for downside puts), leverage effect (price down → leverage & vol up), and fat left tail.
• Term structure: normally upward-sloping (more uncertainty far out); inverts in a panic (front-month IV spikes above back-month).
• Skew steepness ≈ market's pricing of jump/crash risk; flattens in calm regimes.

• Long gamma profits when RV > IV; short gamma profits when RV < IV.
• Hedging gaps/jumps hurt long-gamma less than the theta bleed in quiet markets hurts.

• Calls: only exercise early to capture a dividend (just before ex-date if the dividend exceeds the remaining time value + carry).
• Puts: can be optimal to exercise early even with no dividends — exercising a deep-ITM put frees up cash K to earn interest now; the deeper ITM and higher r, the stronger the case. So American put > European put strictly.

• VIX = √(model-free implied variance of 30-day SPX options) × 100; computed from the same 1/K² strip, not from a single ATM option.
• VIX is a volatility (annualized %), so a "20 VIX" ≈ 20% expected annualized SPX vol ≈ 20/√252 ≈ 1.26% expected daily move.
• Variance (not vol) is the cleanly tradeable/replicable quantity → quotes are often in variance then square-rooted.

• Vega of an ATM option ≈ 0.4·S·√T (per 100% vol; divide by 100 for per-1%-vol).
• A straddle (call+put) ATM ≈ 0.8·S·σ·√T.
• Scaling: halving T shrinks the price by √2 ≈ 1.41×, not 2×.

• European call lower bound: C ≥ max(0, S − Ke^(−rT)) — below this, buy call + short stock + lend Ke^(−rT) for a riskless profit.
• Upper bounds: C ≤ S (call never worth more than the stock); P ≤ Ke^(−rT) (European put ≤ PV of strike). American put ≤ K.
• Comparative statics (which way price moves as one input rises):

  Input ↑	Call	Put
  S	↑	↓
  K	↓	↑
  σ	↑	↑
  T	↑*	↑/↓*
  r	↑	↓

• *Longer T raises an American option monotonically; for European a long-dated put can be worth less than a short-dated one (discounting of K dominates).
• Option value is convex in S (gamma ≥ 0) and monotone — these shape constraints are themselves arbitrages (a call spread can't cost more than its width, a butterfly can't be negative).

• Vol cone: plot the historical min/median/max of realized vol per horizon (e.g. 10d, 30d, 90d, 1y). Overlay today's implied curve — IV near the top of the cone for a tenor = rich; near the bottom = cheap. A richness gauge across tenors, not strikes.
• Variance is additive in time, so forward (between-date) variance is extractable from two spot vols:
  σ_fwd = √[(σ₂²·T₂ − σ₁²·T₁)/(T₂ − T₁)].
• A calendar spread (short near / long far, same K) is a long forward-vol / long calendar-vega position — it wants stillness now and a higher implied later.
• Front-month IV can spike above back-month (inverted / backwardated term structure) in a panic; normally it is upward-sloping (contango).

• Index variance is a correlation-weighted sum of constituent variances: for an equal-weight basket, σ_idx² ≈ ρ̄·(Σwᵢσᵢ)² + (1−ρ̄)·Σwᵢ²σᵢ²; with many names the second term vanishes, so σ_idx ≈ √ρ̄ · Σwᵢσᵢ.
• Implied correlation backs ρ̄ out of index IV and single-name IVs — the market's price of co-movement. It tends to be high (index puts are bid for crash protection), so index vol is often rich vs the basket.
• Dispersion trade: sell index vol, buy single-name vol (via straddles/var swaps). Short implied correlation — profits if names move idiosyncratically (low realized ρ); the classic risk is a correlated crash where ρ→1.
• Single-name skew is typically flatter than index skew precisely because idiosyncratic crashes aren't correlated — index skew embeds the correlation-spike fear.

• Key dates: declaration → ex-date (price drops; buyer no longer entitled) → record → payment.
• Total return = price return + dividend yield; option pricing uses dividend yield q to discount the forward.
• Buybacks return cash without the forced taxable event — often preferred to dividends.

• Macaulay duration = PV-weighted average time to cash flows (years).
• Modified duration D_mod = D_mac/(1+y) → %ΔP ≈ −D_mod·Δy.
• DV01 = dollar value of 1bp = D_mod·P·0.0001.
• Convexity corrects the linear estimate: %ΔP ≈ −D_mod·Δy + ½·Cvx·(Δy)²; convexity is always +ve for vanilla bonds (helps you both ways).

• Contango: F > S (carry markets). Backwardation: F < S (high convenience yield / tight supply).
• Futures vs forwards: futures are exchange-traded, daily marked-to-market with margin (cash flows daily); forwards are OTC, settled once. MTM creates small correlation-with-rates convexity differences.
• Margin: post initial margin, top up to maintenance via variation margin as MTM moves.

• Pay-fixed/receive-float = short duration (gains when rates rise) — like being short a bond.
• Swap rate = par yield: S = (1 − D(T_n)) / Σ τᵢ·D(Tᵢ) where D = discount factors.
• Uses: convert floating debt to fixed, express rate views, hedge duration. DV01 of a swap behaves like the underlying bond.

• Borrower of cash = repo (gives collateral, pays repo rate). Borrower of the security = reverse repo (lends cash).
• Lender protects via a haircut (lends less than collateral value).
• Special collateral repo rate < general collateral (GC) rate when a bond is in high demand to borrow (e.g. to short).

• ETF trading above NAV (premium) → AP buys the underlying basket, delivers it to the issuer, receives new ETF shares, sells them → pushes price down.
• ETF below NAV (discount) → AP buys ETF shares, redeems for the basket, sells the basket → pushes price up.
• This arbitrage is why liquid ETFs track NAV tightly; in-kind transfers are also tax-efficient.

• General collateral (GC): easy-to-borrow, low fee. Hard-to-borrow / special: scarce float → high fee, even negative rebate.
• Short must pay any dividends to the lender ("manufactured dividend").
• Risks: unlimited loss, short squeeze, recall (lender demands shares back → forced buy-in).

• Exchange-traded: standardized, lit central limit order book, anonymous, centrally cleared (futures, listed options, most equities).
• OTC: bilateral, customizable, bears counterparty credit risk (swaps, forwards, bonds) — though many swaps are now CCP-cleared post-2008.
• Central Counterparty (CCP): novates each trade so it becomes buyer-to-every-seller and seller-to-every-buyer; mutualizes default risk via margin + a default fund → removes bilateral counterparty risk.
• Settlement: US equities moved to T+1 (trade date + 1 business day) in May 2024; options settle T+1; spot FX T+2; cash/Treasuries often T+0/T+1.

• Leverage = position size / equity; magnifies both return and loss.
• Futures margin is a performance bond (a few % of notional), reset daily by MTM — far more leverage than Reg-T equity margin.
• Liquidation price = where falling equity hits maintenance.

• Callable bond = straight bond − issuer call option. You are short the call, so P_callable = P_straight − C; price is capped near the call price as yields fall.
• Callables (and MBS) show negative convexity: when rates drop, the call/prepay option kicks in, so price compression beats price appreciation.
• YTM is misleading for callables — quote yield-to-worst (YTW) = min over yield-to-call at each call date and YTM.
• OAS (option-adjusted spread) = the spread over the curve after stripping out embedded-option value via a rates model. It is the apples-to-apples spread vs an option-free bond.
• Convertible = straight bond + investor equity call. conversion ratio = par/conversion price; parity (conversion value) = ratio × stock. Trades as max(bond floor, parity) plus option time value.
• Convert greeks: delta (equity sensitivity) rises as stock climbs — "busted" (deep debt-like, low delta) vs "in-the-money" (equity-like). Convert arb = long bond, short delta×stock.

• Covered interest parity (CIP): F = S · (1+r_d·τ)/(1+r_f·τ) — the forward locks in the rate differential; no arbitrage if you can borrow/lend/spot freely. Higher-rate currency trades at a forward discount.
• FX forward points = F − S quote the rate differential, not a forecast of spot. Points are added/subtracted to spot; sign follows which leg has the higher rate.
• FX swap = spot leg + offsetting forward leg; the workhorse for rolling/funding FX positions and the dominant FX instrument by volume.
• Cross-currency basis = the persistent CIP violation: the extra spread on the funding leg (esp. borrowing USD via FX swaps). A negative EUR/USD basis means paying a premium to get dollars.
• Drivers of the basis: USD funding scarcity, balance-sheet/regulatory costs (limits to arbitrage), quarter/year-end demand. CIP is not a law — it holds only when balance sheet is free.

• TRS: total-return receiver gets all price appreciation + coupons/dividends on a reference asset; pays a floating funding leg (e.g. SOFR + spread) and reimburses any depreciation. The payer holds/hedges the asset.
• A TRS is synthetic leveraged ownership: economic exposure to the asset with no upfront purchase — the funding leg IS the embedded financing.
• Uses: synthetic prime brokerage / leverage, off-balance-sheet exposure, gaining access to assets you can't easily hold (foreign, restricted), and a sec-lending alternative for synthetic shorts.
• Risks: counterparty risk (bilateral, collateralized by margin/CSA), concentration hidden from public filings (no 13F on swap exposure), and forced unwind on margin calls.
• Archegos (2021) is the canonical cautionary case: massive concentrated TRS positions across prime brokers, no aggregate visibility, gap-down forced liquidations.

• list: ordered, mutable, contiguous; great for stacks (append/pop).
• tuple: immutable, hashable (usable as dict keys / set members).
• dict: insertion-ordered since 3.7; keys must be hashable.
• Need O(1) at both ends? Use collections.deque (O(1) appendleft/popleft).

seen = set(big_list)        # build once: O(n)
hits = [x for x in queries if x in seen]   # each lookup O(1)
# vs. `if x in big_list` -> O(n) per query -> O(n*m) total

squares  = [x*x for x in range(10)]            # list
evens    = [x for x in range(10) if x % 2 == 0]  # filter
pairs    = [(i, j) for i in range(3) for j in range(3)]  # nested
price_by = {sym: px for sym, px in quotes}     # dict comp
uniq     = {round(x, 2) for x in samples}      # set comp
# ternary goes BEFORE the for:
clip     = [x if x > 0 else 0 for x in vals]

total = sum(x*x for x in data)   # O(1) extra memory, no list built

def moving_sum(stream, k):
    from collections import deque
    win, s = deque(), 0
    for x in stream:
        win.append(x); s += x
        if len(win) > k:
            s -= win.popleft()
        if len(win) == k:
            yield s

for ms in moving_sum(prices, 20):   # one value at a time
    ...

• A generator is exhausted after one pass — iterate again and you get nothing.
• next(gen) pulls one value; StopIteration at the end.

import itertools
def naturals():
    n = 0
    while True:
        yield n; n += 1
list(itertools.islice(naturals(), 5))   # [0,1,2,3,4]

def bad(x, acc=[]):     # BUG: same list reused
    acc.append(x); return acc
bad(1)  # [1]
bad(2)  # [1, 2]  <-- leaked!

def good(x, acc=None):
    if acc is None:
        acc = []
    acc.append(x); return acc

import copy
a = [[1, 2], [3, 4]]
b = a                  # alias: b is a -> True
c = a.copy()           # shallow: c is a -> False, but c[0] is a[0] -> True
d = copy.deepcopy(a)   # full clone: d[0] is a[0] -> False
a[0].append(99)        # also shows up in c (shared inner list), NOT in d

• Shallow copy: new outer container, same inner objects.
• Use is None / is not None — never == None.
• Small ints (−5..256) and interned strings may share identity; don't rely on is for value equality.

# BEFORE: pairwise returns in a Python loop  (slow)
rets = []
for i in range(1, len(px)):
    rets.append(px[i] / px[i-1] - 1)

# AFTER: vectorized  (no Python-level loop)
import numpy as np
px = np.asarray(px)
rets = px[1:] / px[:-1] - 1            # whole-array slice arithmetic
logret = np.diff(np.log(px))          # log returns, one call

• Avoid growing lists then converting; preallocate or operate on whole arrays.
• Boolean masks replace if-loops: x[x < 0] = 0.
• np.where(cond, a, b) is a vectorized ternary.

z = (x - x.mean()) / x.std()

import pandas as pd
df = pd.DataFrame({"sym": ["A","A","B"], "px": [10.,11.,20.], "qty": [5,3,2]})

df["notional"] = df.px * df.qty            # vectorized, no loop
vwap = (df.groupby("sym")
          .apply(lambda g: (g.px*g.qty).sum()/g.qty.sum()))   # per-group
by_sym = df.groupby("sym").agg(tot=("notional","sum"),
                               n=("px","count"))
df["ret"] = df.groupby("sym").px.pct_change()   # group-aware diff

• .loc[mask, col] for label/boolean selection and safe assignment (avoids chained-assignment warnings).
• merge = SQL join; concat = stack frames.
• shift(1) for lagging — careful not to leak future data.

px, qty = 1234.5678, 50
f"{px:.2f}"        # '1234.57'  (2 decimals)
f"{px:,.2f}"       # '1,234.57' (thousands sep)
f"{px:10.2f}"      # '   1234.57' (width 10, right-aligned)
f"{qty:<6}|"       # '50    |'   (left-align in width 6)
f"{0.0734:.1%}"    # '7.3%'
f"{255:#x}"        # '0xff'
f"{px=}"           # 'px=1234.5678'  (debug: name + value, 3.8+)

f"{sym:<4} {bid:>8.2f} {ask:>8.2f}"

# Two-sum: O(n) using a hash map of value -> index
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return (seen[target - x], i)
        seen[x] = i
    return None

# Counter: frequencies, most common
from collections import Counter
c = Counter("abracadabra")
c.most_common(2)        # [('a', 5), ('b', 2)]

# Reservoir sampling: uniform sample of k from a stream of unknown length
import random
def reservoir(stream, k):
    res = []
    for i, x in enumerate(stream):
        if i < k:
            res.append(x)
        else:
            j = random.randint(0, i)   # inclusive
            if j < k:
                res[j] = x
    return res

0.1 + 0.2 == 0.3          # False
0.1 + 0.2                 # 0.30000000000000004

import math
math.isclose(0.1 + 0.2, 0.3, rel_tol=1e-9)   # True

sum([0.1]*3) == 0.3       # False (0.30000000000000004)
math.fsum([0.1]*3) == 0.3    # True (exact summation)

• For money use decimal.Decimal or integer cents — not floats.
• float('nan') == float('nan') is False; test with math.isnan.
• Catastrophic cancellation: subtracting two near-equal large floats loses precision.

import itertools as it
from collections import defaultdict, deque, Counter, OrderedDict

it.accumulate([1,2,3,4])         # 1,3,6,10  (running sum -> prefix sums)
it.chain([1,2], [3,4])           # 1,2,3,4   (flatten)
it.combinations([1,2,3], 2)      # (1,2),(1,3),(2,3)
it.product([0,1], repeat=2)      # (0,0),(0,1),(1,0),(1,1)
it.groupby(sorted(data))         # consecutive runs (sort first!)
it.pairwise([1,2,3])             # (1,2),(2,3)   (3.10+)

dd = defaultdict(list)           # auto-creates [] on missing key
dd["A"].append(1)                # no KeyError
dq = deque(maxlen=3)             # ring buffer; oldest drops on overflow

• list.append O(1) amortized; occasional resize is O(n) but rare.
• list.insert(0, x) / pop(0) O(n) — shifts everything; use deque.
• x in list/tuple O(n); x in set/dict O(1) average, O(n) worst (hash collisions).
• sorted() / list.sort() O(n log n), Timsort, stable.
• "".join(parts) O(total) — never += strings in a loop (O(n²)).
• heapq push/pop O(log n); heapify O(n).
• dict/set build from n items O(n); slicing a[i:j] O(j−i) (copies).

import heapq
def topk(stream, k):
    h = []
    for x in stream:
        if len(h) < k:
            heapq.heappush(h, x)
        elif x > h[0]:
            heapq.heapreplace(h, x)   # pop smallest, push x
    return sorted(h, reverse=True)

• Broadcasting aligns shapes right to left: dims must be equal or one of them 1; a size-1 dim is stretched without copying.
• Shapes (3,1) and (1,4) broadcast to (3,4) — the classic outer-op pattern. Incompatible: (3,) vs (4,) → error.
• Basic slicing returns a view (shares memory; writes propagate); fancy/boolean indexing returns a copy.
• Check with arr.base is not None (view) and np.shares_memory(a,b).
• reshape returns a view when possible; ravel may view, flatten always copies.

• Arithmetic between objects aligns on index/columns first; non-matching labels yield NaN, not positional pairing.
• a + b reorders to the union of labels. a.add(b, fill_value=0) stays label-aligned but fills labels missing on one side with 0 instead of NaN; for true positional math use a.values + b.values.
• Assign through one .loc, never chain. df[m]["c"]=1 writes to a temporary and may be lost (SettingWithCopyWarning); use df.loc[m,"c"]=1.
• .loc is label-based (endpoint inclusive); .iloc is positional (endpoint exclusive).
• To detach explicitly use .copy(); reindexing/filtering may return a view or copy ambiguously.

• Late binding: closures capture the variable, not its value. [lambda: i for i in range(3)] all return 2; fix with a default arg lambda i=i: i.
• −5..256 and short string literals are interned, so is can accidentally match == — never rely on it (identity vs value lives in the copies card).
• sorted(..., key=...) sorts by the key; it is stable, so equal keys keep input order — chain sorts least-significant-key first.
• dict preserves insertion order (3.7+); equality ignores order, iteration respects it.
• a += b on a list mutates in place (extend); a = a + b rebinds to a new list.

void by_val(int x)  { x = 9; }   // local copy; caller unchanged
void by_ref(int& x) { x = 9; }   // edits caller's object
void by_ptr(int* p) { if (p) *p = 9; }   // may be null; deref carefully

int a = 1;
by_val(a);  // a == 1
by_ref(a);  // a == 9
by_ptr(&a); // a == 9

• A reference must be bound at init and can't be rebound or null.
• A pointer can be null, reassigned, and do arithmetic.
• Prefer references for "must exist"; pointers for "optional / owns nothing / iterates".

int sum(const std::vector<int>& v);   // won't modify v; avoids a copy

const int* p;        // pointer to const int  (can't change *p)
int* const q = &a;   // const pointer to int  (can't reseat q)
const int* const r = &a;  // both fixed

struct Px {
    double mid() const { return (bid + ask) / 2; }  // const member fn
    double bid, ask;
};

• Read declarations right-to-left: const int* p = "p is a pointer to a const int".
• A const member function may not modify members (unless mutable) and can be called on const objects.

#include <memory>
auto u = std::make_unique<Order>(id);   // sole owner; freed at scope exit
auto s = std::make_shared<Book>();      // ref-counted shared ownership
std::weak_ptr<Book> w = s;              // non-owning observer (breaks cycles)

void f() {
    auto p = std::make_unique<int>(42);
    may_throw();          // if it throws, p is still freed -- no leak
}                          // destructor runs here

std::vector<int> v{3, 1, 2};
v.push_back(4);
std::unordered_map<std::string, double> px;
px["AAPL"] = 190.5;             // insert or update
auto it = px.find("AAPL");      // O(1) avg; it == px.end() if absent
if (it != px.end()) use(it->second);

std::vector<int> v{1, 2, 3};

for (int x : v)        { /* copy each element */ }
for (int& x : v)       { x *= 2; }          // modify in place
for (const auto& x : v){ use(x); }          // read-only, no copy

for (auto it = v.begin(); it != v.end(); ++it)
    use(*it);                               // classic iterator loop

• Use const auto& to avoid copying non-trivial elements.
• Modifying a container (e.g. erase/push_back) during iteration can invalidate iterators.
• erase returns the next valid iterator: it = v.erase(it);

template <typename T>
T max_of(const T& a, const T& b) {
    return (a < b) ? b : a;
}
max_of(3, 7);          // T = int
max_of(2.5, 1.5);      // T = double

template <typename It>
auto mean(It first, It last) {
    using V = typename std::iterator_traits<It>::value_type;
    V s{};
    long n = 0;
    for (; first != last; ++first) { s += *first; ++n; }
    return s / n;
}

std::vector<int> make();        // returns a big vector
std::vector<int> a = make();    // move (or RVO) -- no deep copy

std::vector<int> b = a;             // COPY: duplicates all elements
std::vector<int> c = std::move(a);  // MOVE: c takes a's buffer
// after move, `a` is valid-but-unspecified (typically empty)

• std::move is just a cast to an rvalue reference — it enables a move, it doesn't move anything itself.
• Don't use an object after moving from it (except to reassign/destroy).
• Return local objects by value and let RVO / move handle it — don't std::move a return value (it can disable RVO).

double price(const std::string& sym);   // no copy of the string
double price(int id);                   // cheap; by value is fine

void consume(std::vector<int> v);        // takes a copy you'll own
void inspect(const std::vector<int>& v); // read-only, no copy

• By value when you need your own copy anyway (then you can move it).
• const T& binds to temporaries too, so callers can pass literals.

void f() {
    int x = 5;                 // stack: freed automatically
    std::array<int, 64> buf;    // stack: fixed size, fast

    auto p = std::make_unique<int[]>(n);  // heap: size known at runtime
}                              // x, buf freed here; p frees its heap block

• Stack is small (often ~1–8 MB) — large or unknown-size data goes on the heap.
• Heap allocation can fragment and stalls latency — avoid in hot loops.
• Prefer RAII wrappers (containers, smart pointers) over raw new/delete.

• No GC pauses: deallocation is deterministic (destructor at scope end), so there are no unpredictable stop-the-world stalls.
• Cache locality: vector/array store data contiguously; sequential access prefetches well — node-based structures chase pointers and miss cache.
• Zero-overhead abstractions: templates/inlining compile away; you pay only for what you use.
• Control: stack allocation, custom allocators/memory pools, std::array to avoid heap in hot paths.
• Mechanical sympathy: avoid allocations, branches, and false sharing in the hot path; measure with a profiler.

#include <algorithm>
#include <vector>
struct Quote { std::string sym; double px; };

std::vector<Quote> book = /* ... */;

// sort by price descending, ties by symbol ascending
std::sort(book.begin(), book.end(),
    [](const Quote& a, const Quote& b) {
        if (a.px != b.px) return a.px > b.px;
        return a.sym < b.sym;
    });

int thresh = 100;
auto n = std::count_if(book.begin(), book.end(),
    [thresh](const Quote& q){ return q.px > thresh; });  // capture by value

• [x] capture by value, [&x] by reference, [=]/[&] capture all.
• A comparator must be a strict weak ordering — return false for equal elements, never <=.

• Latency hierarchy (approx, order-of-magnitude): L1 ~1ns, L2 ~4ns, L3 ~10ns, main RAM ~100ns. A cache miss to RAM costs ~100× an L1 hit.
• Cache line is 64 bytes; a load pulls the whole line. Keep hot data contiguous and small so one line serves many accesses.
• std::vector is contiguous → linear scans are prefetcher-friendly; std::list/node-based maps chase pointers → a miss per node.
• Struct-of-Arrays (SoA) beats Array-of-Structs (AoS) when you touch one field across many records — no wasted bytes loaded.
• False sharing: two threads writing different vars on the same line ping-pong the line between cores; pad/align hot per-thread data to a line.

• RVO/copy elision lets the compiler construct a returned object directly in the caller's slot — zero copies or moves. Since C++17 it is mandatory for returning a pure prvalue (e.g. return T{...};).
• So return std::move(local); on a return statement is an anti-pattern — it blocks elision and forces a move. Just return local;.
• A forwarding (universal) reference T&& in a deduced template binds to lvalues and rvalues; std::forward<T>(x) preserves the original value category.
• std::move is just a cast to rvalue ref — it moves nothing by itself; the move happens in the chosen overload.

• A reallocation or rehash invalidates iterators/pointers/references into a container; know which ops trigger it per type.

• Container	Insert invalidates	Erase invalidates
  vector	all if capacity grows, else from insert point	at/after erased
  deque	all iterators (refs to ends survive)	all unless an end
  list	none	only the erased
  map/set	none	only the erased
  unordered_*	iterators on rehash; refs survive	only the erased

• vector::reserve(n) up front avoids growth reallocations and keeps iterators stable.