You're given an array prices where prices[i] is the stock price on day i, and an integer k. You may complete at most k transactions, where one transaction = one buy + one matching sell. You can hold at most one share at a time. Maximise total profit.

On any given day, you're in one of two states: holding a share or not holding. From each state, two actions: do nothing, or transition. Count a transaction at the buy (one valid convention; sell-counting also works, just be consistent).

Direct translation of the recurrence. Easy to read, easy to debug, gets full marks if you stop here cleanly.

Equivalent — sometimes easier to write because the state names are intuitive ("max profit on day i after at most j buys, currently in state X"). Pick whichever you can write without bugs.

1. "Add a transaction fee." → Subtract fee on every sell: sell[j] = max(sell[j], buy[j] + price - fee). LC 714.
2. "Add a 1-day cooldown after sell." → Now buy on day i requires sell happened ≤ day i-2. State becomes (holding, just_sold); or carry one extra row of dp. LC 309.
3. "Now there are M stocks running in parallel — same k pooled." → Concatenating arrays doesn't work because order matters per stock. You'd merge in time order and add a "which stock" dimension. Discuss the curse of dimensionality and propose greedy heuristics if k is small.
4. "Prices are streamed; recompute online as each new price arrives." → Hard problem. The DP is forward-only in i, so you can incrementally extend each day. Just keep the current buy/sell arrays, do one inner loop per new tick → O(k) per tick. This is a great answer; emphasise it.
5. "What if k can also change between ticks?" → If k only increases monotonically, you can extend buy/sell with new entries (each new buy[j] initialised from sell[j-1] - price). If k can shrink, you have to discard and recompute from history — flag this.
6. "Prove correctness of the edge case k ≥ n/2." → A transaction needs ≥ 1 day to buy + ≥ 1 day to sell. With n days, you can do at most ⌊n/2⌋ disjoint transactions. So when k ≥ ⌊n/2⌋, k is non-binding and the optimum equals the unconstrained optimum, which by a classic exchange argument = sum of positive consecutive deltas.

• Forgetting the k ≥ n/2 shortcut. For large k (LC test cases go up to 10⁹), the O(n·k) DP TLEs and you fail. The shortcut is mandatory, not optional.
• Counting transactions inconsistently. Saying "I'll count on buy" and then writing the sell line as if you counted on sell. Off-by-one is the death of DP problems.
• Initialising buy to 0 instead of -inf. Then "holding without ever buying" looks free.
• Updating dp in place when transitions reference both old and new values. Use a fresh row, or order updates carefully and explain why the order is safe.
• Returning dp[k][1]. The answer must be in the flat (not-holding) state; otherwise you're holding a share whose value isn't realised profit.

First clarification. "Transaction" is overloaded. It could mean:

• Order event — a new order, cancel, or modify hitting your gateway. (Highest volume; this is what exchanges measure.)
• Match / trade — a buy crossed with a sell, producing a fill. (Lower volume; bounded by liquidity.)
• Settlement transaction — moving cash + securities post-trade. (Much lower volume; T+1 or T+2.)

"Millions per second" most naturally means order events. Confirm: "Are we sizing for ingress order rate, or for matched trades?" That single question signals you understand the domain.

• Scale. Peak vs average TPS? "Millions" — let's pin to 5M order events/sec at peak, 100K matched trades/sec.
• Latency budget. HFT-grade microseconds (sub-100µs end-to-end) or institutional ms? Different architecture.
• Order types. Market, limit, stop, IOC, FOK, GTC? Cancels and modifies?
• Universe. Single-asset class? Equities + futures + options? Symbol count (1K? 100K?).
• Geography. One datacenter or globally distributed? (Multi-region matching is not a thing in serious exchanges; matching is single-DC, market data is replicated globally.)
• Regulation. Is this an exchange (subject to MiFID II / Reg NMS), a broker (best-execution + audit), or an internal trading desk?
• Read/write ratio. Order book reads (market data subscribers) vastly exceed writes — pin a number.

Always do back-of-envelope before architecture. Rough numbers:

• Single-threaded matching sacrifices CPU parallelism for correctness. A multi-threaded matcher would shave microseconds but introduce ordering bugs that are nightmarish in finance. The trade is correct.
• Strong consistency within a symbol; eventual across symbols. AAPL's order book is perfectly serialised. Cross-symbol arbitrage signals see microsecond skew between matchers — that's acceptable; clients with co-located strategies handle it.
• UDP for market data trades reliability for fanout. You build sequence-number gap detection on top.
• Memory speed vs persistence. Order book lives in RAM (microseconds); log writes go through SSD or NVMe with battery-backed cache. The synchronous "write to log before ack" step is your latency floor.
• Hot/warm/cold tiering for log storage. Last hour in NVMe, last week in SSD, archival in S3-class object storage. Most queries hit hot.

• Time-in-force modifiers: GTC (good-til-cancel), IOC (immediate-or-cancel), FOK (fill-or-kill), DAY.
• Order types beyond market/limit: stop, stop-limit, peg, iceberg (display only part), hidden.
• Price-time priority — the universal matching rule: best price first, ties broken by submission time.
• Co-location — clients renting rack space inside the exchange to minimise wire latency.
• Self-match prevention (SMP) — preventing a client from crossing their own order (regulatory).
• FIX protocol — text-based; OUCH/ITCH — binary, what NASDAQ uses internally.
• Kernel bypass (DPDK, Solarflare OpenOnload), RDMA, FPGA-offload matching — for HFT-grade latency.

Implement a data structure with two operations:

• insert(x) — add a price to the stream
• findMedian() — return the current median over all prices seen so far

Required: insert in O(log n), findMedian in O(1) ideally. The interviewer's required bound (O(log n) for both) leaves several solutions on the table.

Walk it from naive to optimal. This narration is what gets you the offer; jumping straight to "two heaps" looks pre-memorised.

Maintain three invariants and the median is always free:

1. Every element in lo ≤ every element in hi.
2. Sizes balanced: |lo| - |hi| ∈ {0, 1}. (We let lo be the bigger one when odd.)
3. Median: if odd total → lo.peek(); if even → (lo.peek() + hi.peek()) / 2.

1. "Sliding window of size W instead of all-time median." → Now you also need removeOldest. Heap doesn't support arbitrary delete in O(log n). Two answers:
   • Lazy deletion: tag entries with index, mark removed, skip on peek. Amortised O(log n) but pathological cases.
   • Two SortedList / multiset (Python SortedList from sortedcontainers, C++ multiset): supports add and remove in O(log W). Cleaner. This is LC 480.
2. "Now find the 95th percentile, not the median." → Two heaps generalise: keep the bottom 95% in one heap, top 5% in the other, maintain ratios on insert. Or use an order statistic tree (balanced BST with subtree size). Cleaner.
3. "What if the stream is too big to fit in memory?" → You can't compute the exact median anymore. Approximate with:
   • t-digest — clustered quantile sketch, mergeable across machines. State of the art.
   • Greenwald-Khanna (GK) summary — bounded-error quantiles in O(log n / ε) space.
   • Reservoir sampling — uniform random sample, then take median of sample. Crude but trivial to implement.
   Mentioning t-digest by name is the easy way to look like you've worked with streaming statistics before.
4. "How would you make this distributed across N shards?" → Each shard maintains its own sketch (t-digest), then merge centrally. The two-heap structure does NOT merge cleanly — you'd have to ship all elements. T-digest is mergeable; that's its whole reason for existing.
5. "What if prices can be deleted by sequence number?" → Index-based lazy deletion in the heaps; or move to a balanced BST keyed by (price, seq_id).
6. "What's the median of medians?" → Different topic — that's the deterministic O(n) selection algorithm. If they ask, redirect: "That's the linear-time selection trick — O(n) to find the kth element by partitioning around medians of 5-element groups. Different problem from the streaming version, but worth flagging."

• Robust statistics. In market data, mean is corrupted by fat-finger trades and outliers. Median and quantile-based stats (median absolute deviation, IQR) are far more robust — they're what risk monitors use.
• VWAP and TWAP. Volume-weighted and time-weighted average prices use streaming aggregations of the same shape (running sums, running quantiles).
• Anomaly detection thresholds. "Flag any trade more than 3 MAD from the rolling median" — directly uses streaming median + streaming MAD. Same data structure pattern.
• Risk reporting. P&L distributions are reported with quantiles (VaR is the 95th or 99th percentile loss). Online quantile estimation is the production use case.

In finance, the answer is yes for some data, no for others. Don't rush to "strong consistency" for the entire cache. State this clearly:

Saying "let me clarify which subset of financial data needs strong consistency" buys you 30 seconds and shows you don't blindly apply patterns.

CAP theorem: in a distributed system, under network partition, you cannot have both consistency and availability. Pick one. A strongly consistent cache is a CP system: it accepts writes only when a majority quorum of replicas can ack; if you're partitioned into the minority side, you reject writes.

• CP example: etcd, ZooKeeper, Spanner, FoundationDB, TiKV. Built on consensus.
• AP example: Cassandra (default), DynamoDB (default), Riak. Eventual consistency.
• Redis Cluster: default mode is asynchronous replication = AP-leaning, NOT strongly consistent. WAIT command + Redis Sentinel can give bounded staleness, but for true linearisable strong consistency you'd reach for Redis Enterprise's CRDB or layer Raft on top yourself.

• Latency floor. A write commits only after the leader plus a majority of followers have durably persisted it. That's 1 RTT to followers + 1 fsync per replica. Realistically: 1–5ms in a single DC, 50–100ms cross-region.
• Throughput is leader-bound per shard. Single leader means single write pipeline per shard. To scale total throughput, add shards.
• Availability dips during leader election. Up to ~10s where that shard accepts no writes. The fix: more shards = smaller blast radius per election.
• Strong consistency vs read scalability. Linearisable reads only from leader (or with quorum). Followers can serve stale reads if you accept bounded staleness. Choose per workload.
• Geographic distribution = latency tax. Cross-region Raft means committing across continents. Spanner pays this; most finance systems instead deploy region-local Raft groups + asynchronous cross-region replication for DR (with explicit "this region's data may be stale" semantics).

1. "Why is this not just Redis?" → Redis async replication = bounded staleness, not linearisable. Failover can lose the last few writes. Unacceptable for ledger data.
2. "Walk me through Raft leader election." → Followers heartbeat from leader; if missed, follower becomes candidate, increments term, requests votes from peers. Majority vote wins. Term numbers prevent split-brain. Be able to draw this on paper.
3. "What happens during a network partition?" → Side with majority retains a leader, keeps committing. Side with minority loses leader, can't commit (no quorum), serves only reads (stale). Heal: minority side replays log from majority leader, discards uncommitted entries.
4. "Cache invalidation strategy?" → For a cache backed by an authoritative store, write-through (write to store + cache atomically — hard) or write-around with TTL (simple, but stale window). For a strongly consistent primary KV store, this question doesn't apply — there's no "source of truth" behind it.
5. "How do you handle a clock skew between nodes?" → Raft itself doesn't depend on clocks for correctness — uses logical sequence numbers (terms, log indices). Clocks affect performance (election timeouts) but not safety. Spanner is the exception: it uses TrueTime with bounded clock uncertainty, requires GPS + atomic clocks in every DC.
6. "Read-your-own-writes guarantees from a different datacenter?" → Either pin the client to the leader's region, or have the client carry a "read-after-seq-N" token that any replica can wait on. Sticky-by-session works in practice.

• Limiting dimensions. "Per user, per endpoint" — does that mean each (user, endpoint) pair has its own bucket? Or do users have a global cap AND each endpoint also has a per-user cap (i.e., layered limits)? Layered is the realistic answer.
• Granularity. Requests per second, per minute, per hour, per day? Multiple at once?
• Bursty vs strict. Do we allow short bursts up to capacity (token bucket), or strictly smooth (leaky bucket)?
• Where to enforce. API gateway (cheapest, coarse), per-service middleware (finer), or both?
• Failure mode. If the rate-limiter service is down, fail-open (let traffic through) or fail-closed (reject)? In finance, fail-closed for trading endpoints, fail-open for read-only metadata.
• Scale. "Millions of users × hundreds of endpoints" needs centralised state. A small internal service can do it in-memory.

In-process Python first (interview-quality, ignores distribution):

For a distributed deployment, replace the lock + dict with Redis + Lua:

Limits aren't constants — they vary by user tier and endpoint. Keep the config in a separate store, query it (cached) on each request:

• Centralised state vs eventual consistency. One Redis cluster = strong limits but adds 0.5-2ms per request. Per-gateway local state with periodic sync = faster but allows brief over-limit windows.
• Memory vs accuracy. Sliding window log is exact but stores every request timestamp; sliding window counter is O(1) but assumes uniform distribution within windows.
• Burstiness vs smoothness. Token bucket allows up-to-capacity bursts (good for legitimate user behaviour like batch syncs); leaky bucket strictly smooths (good for protecting fragile downstream services).
• Fail-open vs fail-closed. If Redis dies, do you let everything through or block everything? In finance: fail-closed for trading APIs (an outage rejecting orders is recoverable; rogue throughput is not), fail-open for read-only market data (accepting a brief unprotected window is fine).
• Clock skew. Token-bucket refill depends on time. If gateway clocks are skewed, refill rates become inconsistent. Use Redis TIME command (server-side single source) inside the Lua script to eliminate skew.

1. "Race condition between two gateways?" → Lua script in Redis runs atomically. Without it, two reads + two writes race and both succeed when only one should.
2. "What HTTP status do you return?" → 429 Too Many Requests. Include Retry-After header (seconds until next token available) and X-RateLimit-Remaining for client visibility.
3. "How do you communicate limits to clients?" → X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset response headers on every request, plus 429 with Retry-After on rejection. Documented in API docs.
4. "What about geo-distributed users?" → Per-region limits with periodic global sync. Accepts that a user can briefly exceed their global limit by spreading requests across regions; flag the trade-off.
5. "How would you protect against a single bad actor flooding the rate limiter itself?" → Defense in depth: drop traffic at the LB / edge before it reaches the limiter; per-IP fallback limit at the LB layer; circuit breaker on the limiter to fail-closed if Redis is overwhelmed.
6. "Difference between rate limiting and throttling?" → Rate limiting = hard reject when over. Throttling = slow down, queue, or degrade quality. Different actions on the same signal.

• What kind of "anomalous"? Market manipulation (spoofing, layering, wash trades), insider trading patterns, fat-finger errors, or operational anomalies (a strategy gone rogue)? Different signals.
• Latency budget. Real-time intervention (block the trade pre-execution, ~100ms) vs near-real-time alerting for analyst review (seconds to minutes) vs end-of-day surveillance (overnight batch). Each has a wildly different architecture.
• Action on detection. Block the order, alert a compliance officer, log for review, automatic kill-switch on a strategy?
• Universe. A single trading desk's flow vs firm-wide vs all market participants (exchange surveillance like SEC's CAT)?
• False positive tolerance. In compliance, false negatives are catastrophic (missed manipulation = SEC fine); false positives are merely expensive (analyst time). Recall almost always outweighs precision — F-beta with β > 1.

• Kafka — high-throughput partitioned event log; partition by symbol or trader_id for in-order processing.
• Apache Flink — stateful stream processor. Industry default for real-time fraud / anomaly; ING Bank, Capital One, Grab, Kakao Games are public references. Flink's CEP (Complex Event Processing) library expresses patterns like "BUY followed within 100ms by SELL of the same beneficial owner" in a few lines.
• Kafka Streams / ksqlDB — lighter alternative if your team is already JVM-heavy.
• Feature store — Feast, Tecton. Avoids training/serving skew on rolling features (mean, stdev, volume).
• Model serving — Seldon, KServe, Triton. Or a lightweight Python service if latency budget allows. Always shadow-deploy new versions.
• Audit storage — S3 + Glacier (cheap immutable archival), or hot tier in TimescaleDB / ClickHouse for analyst queries.
• Approximate sketches for high-cardinality streams: Bloom filter (membership), Count-Min Sketch (frequency), HyperLogLog (cardinality), t-digest (quantiles). These are the right tools when "how many distinct accounts traded this symbol in the last hour" must be O(1) memory.

• Isolation Forest. Unsupervised, tree-based, fast. Industry workhorse for tabular anomaly detection. Good first ML model.
• Autoencoder reconstruction error. Train a NN to reconstruct "normal" trade vectors; high reconstruction error = anomaly. Catches more subtle / multivariate anomalies but harder to explain.
• One-class SVM. Older, doesn't scale as well, mostly mentioned for completeness.
• Sequence models (LSTM, Transformer). For order trajectories (sequence of place/modify/cancel events), capture temporal patterns spoofing rules can miss.
• Online / adaptive models (River library, Hoeffding trees). Update on new data; useful when the "normal" distribution drifts.
• ARIMA / EWMA for univariate time-series — Confluent and AWS both ship managed ARIMA-based anomaly detection on Flink streams.

• Recall vs precision. Compliance prefers recall — missing manipulation is catastrophic; investigating a false positive is annoying. Optimise F-beta with β > 1; tune threshold to favor recall. Almost always cite this trade-off explicitly.
• Latency vs sophistication. Pre-trade gates (microseconds) get rules only. Post-trade can use heavier ML.
• Static rules vs adaptive ML. Rules don't drift but bad actors learn them. ML adapts but needs retraining and validation cycles. Layering is the answer.
• False positive cost vs analyst capacity. Each alert consumes ~30 minutes of analyst time. Set thresholds against analyst headcount, not just statistical significance.
• Online learning vs validated batch retraining. Online is responsive but can be poisoned by adversaries. Batch retraining with validation is safer in regulated environments. Most production systems batch-retrain weekly.

• SR 11-7 — Federal Reserve model risk management. Mention by name. Requires every model have documented purpose, inputs, training data lineage, validation tests, known limitations.
• SEC Consolidated Audit Trail (CAT) — every order in US equities/options must be reported. Surveillance systems are downstream consumers of CAT data.
• MAR (Market Abuse Regulation, EU) / MiFID II — explicit requirements for surveillance and pre-trade controls.
• Model versioning + auditability. Every detection logged with model version + feature snapshot. If a model is retrained, old decisions can still be reproduced.
• Shadow deployment for new models. New version runs in parallel, outputs compared, doesn't act for 2-4 weeks of validation. Standard at GS, JPM, etc.
• "Four eyes" override. Compliance officer review for any auto-block; reversibility on false positives.

1. "How do you handle concept drift?" → Monitor input feature distributions (KL divergence vs training set), monitor prediction distributions, alert on drift. Scheduled retraining + shadow validation. Mention data drift vs concept drift distinction.
2. "How do you label training data?" → Hard problem. Confirmed manipulation cases are rare and lagged. Use weak labels (analyst-flagged + investigated), synthetic injection of known patterns, semi-supervised methods. Acknowledge the difficulty — interviewers respect honesty here.
3. "What if the system itself is exploited?" → Detection thresholds become public via model probing. Defenses: rotate thresholds, add randomness, layered system means defeating one layer doesn't help, audit the auditor.
4. "How would you scale this from one desk to firm-wide?" → Partition by trader_id × symbol; aggregate at desk and firm rollup levels. Per-desk Flink job, central aggregator, hierarchical thresholds.
5. "What if a detection is wrong and you blocked a legitimate trade?" → SLA on false positive review (e.g., compliance reviews within 5 minutes), reversibility via cancel-and-resubmit, post-incident review every Friday. False-positive rate is a key SLO.
6. "How do you detect coordinated manipulation across multiple accounts?" → Graph-based detection. Build trader/account graph; look for subgraphs with correlated trades, common beneficial owner, common IP / device fingerprint. ING Bank is on record using graph methods for this.

1. "Let me clarify..." Always your first sentence. Buys 30 seconds, signals seriousness.
2. "The trade-off here is X vs Y. I'd pick X because..." Minimum 3 trade-offs per system design.
3. "Let me name the failure mode..." Don't wait to be asked.
4. "In finance, fail-closed." If you only remember one phrase across all six, this one.
5. "Append-only audit log." Mention once per system design.
6. "I don't know — but here's how I'd figure it out..." Beats bluffing every time. GS scores this higher than confident wrong answers.

• Don't memorise solutions verbatim. The interviewer's variant will be slightly different and you'll panic. Memorise patterns, derive solutions.
• Don't read silently. If you can't explain it out loud to an empty room, you can't explain it under pressure.
• Don't skip the brute-force narration. Even when you know the optimal answer immediately, walk through "naive O(n²) would work but..." — interviewers value process.
• Don't claim depth you don't have. Saying "I'm familiar with TrueTime" and then floundering when probed is worse than saying "I know Spanner uses synchronised clocks but I haven't read the paper in detail." Honest gaps + curiosity scores higher than fake depth.
• Don't grind day-of. The Saturday before the interview should be light review only. New material the night before doesn't stick and crowds out what you've already learned.