OpenAI Software Engineer Interview Prep Guide

Focus most on coding-round stream processing, out-of-order network packets, concurrency, cache eviction, and transaction/snapshot semantics; those are explicitly selected or called out as shaky/new. You're solid on core graph algorithms like BFS, Dijkstra, topological sort, union-find, and you self-rated Coding & Algorithms 5/5, so allocator mechanics and familiar graph traversal stay brief. For OpenAI-specific prep, this plan highlights GPU credit scheduling, streaming conversational AI delivery, production ML evaluation/safety, and unreliable event-time telemetry. With less than a week, budget roughly 100 minutes total: prioritize the emphasized coding addenda first, then skim the brief system-design topics.

Technical Screen — 81 min

System Design

Focus area — OpenAI-specific infrastructure angle; practice deterministic credits, expiration, idempotency, and scheduler integration under concurrent multi-tenant GPU demand.

What's being tested

Candidates must show practical mastery of designing a multi-tenant, real-time resource accounting and scheduling system that prevents double-spend, enforces budgets, and schedules heterogeneous GPUs. Interviewers probe distributed-systems primitives (consistency, partitioning, idempotency), APIs and failure modes (retries, node failure, clock skew), and scheduler algorithms (gang scheduling, bin-packing, fairness). Expect the interviewer to evaluate clear tradeoffs between strict correctness (no overspend) and scalable, low-latency allocation paths.

Core knowledge

• Credit ledger data model: per-tenant balance, per-transaction idempotency key, monotonic sequence or vector timestamp to order updates; store in a strongly consistent partition (etcd, Spanner, Postgres with SELECT FOR UPDATE) when linearizability is required.

• Idempotency: clients must send an idempotency key; server stores (key -> result) for retry-safe semantics; eviction policy based on TTL and transaction finality to bound storage.

• Reservation vs commit: implement a two-phase flow: reserve (temporary lease reducing available balance) then commit (final deduction), supporting rollback on node failure; leases expire automatically to avoid stuck resources.

• Fast-path local checks: use a cached bucket/token (leaky token-bucket) per tenant for sub-second approvals; reconcile with authoritative ledger periodically to bound over-commit risk.

• Distributed partitioning: partition ledger by tenant-id or account-hash; scale to millions by sharding and routing RPCs to the shard owner, minimizing cross-shard transactions.

• Heterogeneous GPU costing: normalize GPUs using cost-rate (credits/sec) per device type; billing = sum(cost_rate_i * seconds_used_i). Support preemption and partial refunds with precise time accounting.

• Scheduler algorithms: for multi-GPU jobs use gang scheduling + bin-packing heuristics (best-fit decreasing) or Dominant Resource Fairness (DRF) for fairness; backfilling reduces fragmentation for short jobs.

• Atomicity & concurrency control: for strict correctness prefer linearizable updates (compare-and-set, serializable DB txns); for higher throughput consider optimistic allocation with bounded reconciliation windows.

• Failure modes: handle node crashes (leases expire), network partitions (reject writes if quorum not available for linearizability), and clock skew (use server timestamps or monotonic counters).

• Observability & SLAs: track p99 allocation latency, double-spend incidents, reconciliation drift, and per-tenant throttles; emit events to Kafka/ingestion pipeline for billing pipeline.

• Security & multi-tenancy: authenticate calls via strong identity (mTLS, IAM), enforce RBAC for transfers, and audit every ledger mutation for dispute resolution.

• Scaling numbers: for N tenants ~10M, keep per-tenant metadata in a scalable KV store; avoid multi-tenant cross-shard txns—they kill throughput. Use asynchronous reconciliation and incremental snapshots for export.

Worked example — "Design GPU credit allocator"

First 30 seconds: ask expected scale (tenants/sec, concurrent allocs), consistency SLA (strict no-overspend vs eventual), GPU heterogeneity, and whether allocations are preemptible. Declare assumptions: target 100k allocs/sec, strict per-tenant no-overspend, heterogeneous GPUs with known cost rates.

Skeleton of an answer:

1. API design: Reserve(tenant, amount, idempotency_key), Commit(reservation_id), Release(reservation_id); synchronous response for Reserve.

2. Ledger implementation: shard by tenant; each shard owner provides linearizable reservations via SELECT FOR UPDATE or etcd CAS. Store reservations with TTL.

3. Fast-path: local token-bucket cache for micro-requests; falls back to authoritative Reserve RPC when cache misses.

4. Scheduler integration: scheduler requests reservations for GPU set (gang), scheduler commits when job starts, releases on preemption.

Explicit tradeoff: using strong linearizability prevents double-spend but requires cross-shard coordination for transfers—choose to ban cross-shard atomic transfers or implement async transfer with temporary credit holds. Closing: if more time, prototype shard-split logic, run chaos-testing (node failures, retries), and design reconciliation jobs to detect and correct drift.

A second angle — "Design credit balance with vector-clock expirations"

This variant emphasizes concurrent updates from multiple disconnected clients and expiry semantics. Use vector clocks or per-shard monotonic counters to track causality of credit events; model balance as an eventually-consistent CRDT only if occasional overspend is acceptable. To support expirations, attach expiry metadata to each credit delta and garbage-collect with causal ordering to avoid prematurely dropping recent updates. The primary shift: when strict single-source ordering is impossible, rely on deterministic merge functions and compensation transactions, and be explicit about allowed windows for inconsistency.

Common pitfalls

Pitfall: Relying solely on a cheap local cache for immediate approvals without any authoritative reconciliation. This leads to silent double-spend when many nodes grant allocations simultaneously; prefer bounded fast-path windows and periodic reconciliation or pessimistic reservations for high-value ops.

Pitfall: Forgetting idempotency keys and storing results only transiently. Retries will create duplicated charges; store idempotency mapping with TTL and ensure idempotent handlers are deterministic.

Pitfall: Designing the scheduler independently from credit semantics. Scheduling multi-GPU jobs requires atomic reservations across multiple GPUs (gang scheduling); otherwise partial allocations result in wasted resources and complex refunds. Flag the need for a coordinated reserve-and-commit for multi-device jobs.

Connections

Interviewers may pivot to adjacent topics: designing the billing/export pipeline and offline reconciliation (data engineering), or to fine-grained scheduler optimization (resource management research like Borg/Omega). They may also ask about monitoring and alerting thresholds (SRE concerns).

Further reading

• Designing Data-Intensive Applications — Martin Kleppmann — strong treatment of consistency, partitioning, and CRDTs for ledger-like systems.

• Dynamo: Amazon’s Highly Available Key-value Store — background on partitioning, eventual consistency, and vector-clock techniques.

• Stripe: Idempotency keys — practical pattern and tradeoffs for retry-safe financial operations.

Practice questions

• Event-Time Telemetry For Unreliable Devices (Focus) — covered in depth under Onsite below.

• In-Memory Databases And Query Engines — covered in depth under Onsite below.

ML System Design

Focus area — Highly OpenAI-relevant and overlaps your stream focus: token streaming, cancellation, state, admission control, and resilient client behavior.

What's being tested

Candidates must show end-to-end engineering judgment for building low-latency, robust streaming chat systems: real-time transport choices, transient client state management, concurrency and cancellation, backpressure/admission control, and availability tradeoffs. Interviewers probe whether you can design practical, testable interfaces (APIs, idempotency, resume tokens), reason about tail latency and resource isolation, and communicate clear failure modes and mitigations a Software Engineer would implement.

Core knowledge

• Streaming transport options — tradeoffs between `WebSocket`, Server-Sent Events (SSE), HTTP/2+gRPC streaming, and HTTP chunked responses; choose by bidirectionality, proxy compatibility, and browser support.

• Chunked transfer & framing — send discrete token/delta frames; include sequence numbers, content-type application/json-seq, and explicit end-of-stream markers to enable reassembly and resume.

• Resume tokens & idempotency — attach a compact resume cursor or token with each frame so clients can reconnect and request "resume from offset X"; use server-side idempotency keys for request deduplication.

• Backpressure & admission control — use token-bucket or leaky-bucket per-client rate limiting and global admission control; reject or queue requests when CPU/latency budgets exceed thresholds to protect p99 latency.

• Cancellation semantics — propagate client cancels immediately to compute layer; implement soft-cancel (stop token generation) and hard-cancel (kill compute) with timeout/window for graceful cleanup.

• Stateless fronting with sticky state — keep frontends stateless relays but use sticky session routing or external session store (small Redis) for ephemeral streaming metadata (resume tokens, partial buffers).

• Transient UI state model — represent in client as immutable message tree with in-progress flags and append-only token deltas; reconcile streams by id/seq to avoid flicker and duplicates.

• Persistence model: snapshots & event log — store conversation as append-only event log plus periodic snapshots for reads; snapshotting at message boundaries speeds restores and sharing use-cases.

• Consistency and concurrent updates — use optimistic concurrency control (CAS) for edits and snapshot writes; design for last-writer-wins or CRDT merge only if multi-author editing required.

• Latency budgeting — set tight budgets: e.g., client RTT + server queueing + model compute ≤ target (e.g., 500ms for response start), monitor p95/p99 for throttling decisions; expose graceful degrade path (shorter summary instead of full generation).

• Monitoring & observability signals — instrument request lifecycle: enqueue time, start time, token emission rate, bytes streamed, cancellation rate, resume success rate; alert on rising resume/retry counts and p99 token gaps.

• Testing & determinism — add deterministic replay hooks and synthetic load tests that simulate partial-frame loss, reconnects, and slow clients; mock providers with configurable latency and tokenization.

Worked example — Build a Reliable Streaming Chat UI

First 30 seconds: clarify client constraints (browser vs native), expected throughput (users concurrently streaming), allowed transports (`WebSocket` vs SSE), and what “reliable” means (resume on reconnect, no duplicated tokens, consistent UI ordering). Skeleton answer pillars: (1) transport + framing (frame = {msg_id, seq, resume_token, delta}), (2) client state management (immutable message list with an in-progress entry and id/seq reconciliation), (3) resume & idempotency (server issues resume cursors and supports resume API), and (4) admission/backpressure (client-level rate-limits & server-side admission).

One tradeoff to flag: using `WebSocket` gives bidirectional control and built-in backpressure semantics in some stacks, but is harder to proxy and scale through certain load balancers—SSE is simpler but uni-directional. Implementation detail to call out: include sequence numbers and a server-signed resume token to avoid accepting stale resumes after conversation deletion. Close with next steps: if time remains, sketch tests (reconnect fuzzing), performance targets (p95 start latency), and how to instrument for out-of-order or missing frames.

A second angle — Design a Highly Available Conversational AI Service

This question emphasizes availability, regional isolation, and dependency failures. Apply the same streaming principles but shift focus to system-level resilience: front-door load shedding, multi-region routing, replica isolation, and graceful degradation. With streaming, you must plan admission control globally (reject to preserve p99 for existing streams), fall back to cached or summarised responses on dependency failure, and implement cross-region resume tokens so clients reconnect to nearest healthy region without redoing expensive compute. Also design per-tenant quotas and circuit breakers around an external LLM provider: if provider latency spikes, return a short canned reply or progress bar while preserving connection and allowing resume. The core primitives (framing, resume, cancellation, instrumentation) are identical, but you now prioritize isolation, capacity planning, and failover strategies.

Common pitfalls

Pitfall: assuming TCP backpressure is enough — TCP windows don't provide application-level flow control for tokenized JSON frames; you still need explicit rate or frame control and client-side buffering limits to avoid OOM or UI jank.

Pitfall: resuming by raw byte offset — resumes should be by logical token/sequence id with server validation; byte offsets break across different encodings, partial serialization, and middleware rewrites.

Pitfall: client optimistic UI that blindly appends streamed deltas without deduplication — this yields duplicated text after reconnects; reconcile on msg_id + seq and keep an idempotency filter.

Connections

Interviewers may pivot to adjacent topics like model-serving orchestration (scaling inference backends, warm pools) or data consistency (event sourcing vs relational snapshots) — be prepared to discuss how streaming primitives interact with those systems, especially for admission control and snapshot durability.

Further reading

• Designing Data-Intensive Applications (Martin Kleppmann) — event logs, snapshots, and distributed consistency patterns for conversation stores.

Practice questions

Focus area — OpenAI-specific review area; focus on serving, evaluation, monitoring, rollout, and safety trade-offs rather than ML theory breadth.

What's being tested

Candidates must show practical, systems-focused debugging and design skills for production ML: diagnosing pipeline and model failures, instrumenting reliable serving, and choosing safe rollout strategies. Interviewers probe the candidate’s ability to structure an investigation, read telemetry, and propose engineering fixes (retries, feature parity, canaries, rollbacks) rather than invent new ML algorithms.

Core knowledge

• Data drift vs concept drift: know the difference—data distribution change (input features) vs label relationship change (P(y|x)); detect with population statistics, PSI, or simple KS tests on feature histograms.

• Feature parity: ensure offline-features and online-features are computed identically; mismatches are a top cause of production failures. Reproduce feature pipelines locally before blaming the model.

• Model versioning and lineage: use MLflow or artifact stores to track model binary, training data hash, feature-transformation code, and config; make rollbacks deterministic by pinning all artifacts.

• Serving patterns: know the tradeoffs of online inference (low latency, strong consistency) vs batch/async (higher throughput, relaxed freshness). Implement with Kubernetes + TensorFlow Serving/PyTorch Serve or a lightweight microservice.

• Canary & shadow deployment: route a small % of live traffic to a new model (canary) for latency/quality checks; mirror traffic to a new model with no user effect (shadow) to validate parity.

• Monitoring & SLOs: instrument p95/p99 latency, error rate, and throughput; add model-specific telemetry: input distribution summaries, feature null rates, and top-10 features by contribution. Alert on threshold breaches.

• Model evaluation signals: track surface metrics (accuracy, precision, recall) plus calibration (reliability diagrams, Brier score) and production proxies (CTR, downstream conversion) when labels are delayed.

• Drift detection and retraining triggers: use sliding-window comparisons, population-stability-index (PSI), or statistical change detectors; avoid retraining on transient spikes — require persistence or multiple signals.

• Observability tools: integrate Prometheus for metrics, Grafana dashboards, structured logs for request/response, and distributed traces to correlate model latency with upstream/downstream services.

• Operational robustness: implement idempotent requests, graceful degradation (cached fallback model), circuit breakers, and exponential backoff for retriable failures; log inputs that hit fallbacks for analysis.

• Privacy & safety guardrails: enforce input sanitization and rate limits, redact PII before logging, and add a pre-check to block toxic or out-of-distribution inputs.

Tip: capture a reproducible failing request (input, feature values, model version) so engineers can replay production behavior locally.

Worked example — Debug a failing ML classifier

Start by framing: ask what “failing” means (latency, accuracy drop, calibration drift, or increased false positives), when it started, rollout/versions, and whether labels are available in production. Organize the investigation into three pillars: (1) reproduce the failure locally (replay production requests), (2) inspect pipeline differences (feature-parity, preprocessing), and (3) inspect runtime signals (latency, memory, OOMs, infra errors). Triage steps: check recent deployments and config changes, verify feature histograms for top features against training distribution, and run the model binary on a sample of production inputs to compare predicted scores and confidences. A concrete tradeoff to call out: if retraining is easy, you can quick-retrain on recent data, but that risks reinforcing label bias—prefer validating drift and running a controlled canary retrain. Close by proposing short-term mitigations (canary rollback, serving fallback) and long-term fixes (add feature-parity tests, automated drift alerts, and reproducible replay pipelines), and say: “if I had more time, I’d add a shadow test harness and automated A/B quality gates with live labels.”

A second angle — Design a response-ranking ML system

Ranking introduces high-throughput, latency-critical serving and heavy instrumentation needs. The same debugging primitives apply: ensure feature parity between offline ranker training and online scorer, use shadowing to mirror traffic to new ranking models, and monitor both ranking-specific metrics (NDCG, CTR at k) and system SLOs. Unique constraints include candidate-generation latency (multi-stage pipelines), stateful session features, and the need for online batch scoring or pre-computed candidate scores. A software engineer must design efficient feature lookup (in-memory cache or Redis), ensure deterministic sort order under ties, and provide fast rollbacks because model mistakes directly affect user experience and revenue.

Common pitfalls

Pitfall: Blaming the model first.
Jumping to retrain without checking feature pipelines or infra issues wastes time. A better approach is to first reproduce requests end-to-end and confirm that the model gets the same inputs offline as online.

Pitfall: Relying solely on offline metrics.
Offline evaluation (e.g., cross-val accuracy) can miss production mismatches. Always correlate with production telemetry, shadow experiments, and delayed-label feedback loops.

Pitfall: Over-alerting on transient noise.
Triggering retrains or rollbacks on single spikes causes churn. Require multiple corroborating signals (persisting drift, label degradation, increased error rates) before automating heavyweight changes.

Connections

Interviewers may pivot to adjacent systems topics: feature stores and their consistency semantics, or deployment pipelines like CI/CD for models and canary automation. They might also ask about distributed tracing and SLO-driven incident response for ML services.

Further reading

• Hidden Technical Debt in Machine Learning Systems — Sculley et al., NIPS 2015 — seminal paper on production ML failure modes and engineering debt.

• Designing Data-Intensive Applications — Martin Kleppmann — practical reference for durable storage, stream processing, and system reliability patterns relevant to ML serving.

Practice questions

Coding & Algorithms

Focus area — Added from your special requirement: coding practice for packets arriving out of order, duplicates, gaps, sequence numbers, and buffering.

What's being tested

This concept tests whether you can design a reliable stream reassembler from unordered, duplicated, delayed, overlapping, and fragmented packets. The interviewer is probing data-structure choice, sequence-number arithmetic, gap detection, memory bounds, and clear handling of malformed or adversarial input. At OpenAI, this matters because production services depend on robust protocol implementations, bounded resource usage, and debugging discipline under partial failure—not merely the happy path of receiving packets in order.

Core knowledge

• A packet reassembler converts records (stream_id, sequence_number, payload, flags) into an ordered byte stream. Clarify whether sequence numbers identify bytes or fragments, whether packets may be duplicated, and whether multiple streams must be isolated.

• The standard design keeps a contiguous frontier next_expected, plus a sorted interval map of buffered out-of-order data. When a packet begins at next_expected, emit it and repeatedly consume adjacent buffered intervals.

• For arbitrary sequence numbers, use an ordered map such as std::map, a balanced tree, or a heap plus hash index. Insertion and merging cost O(log k) for k buffered intervals; emitting a run costs O(number of merged intervals + bytes emitted).

• A hash map keyed by exact sequence number is simpler but performs poorly when packets overlap or start at different offsets. An interval tree or ordered disjoint interval map is preferable when fragmentation and overlap are common.

• Normalize every packet into an interval [start, end) with payload length end - start. Half-open intervals make adjacency precise: [0, 100) and [100, 150) can merge without ambiguity, while [0, 100) and [101, 150) contain a one-byte gap.

• Handle overlap using an explicit policy. For trusted transport, “first byte received wins” or “latest byte wins” may be acceptable; for security-sensitive reassembly, inconsistent overlapping payloads should be rejected or surfaced because different endpoints may interpret them differently.

• Bound memory with a receive window, maximum buffered bytes, maximum interval count, and packet-size limits. Without these controls, an attacker can send far-future sequence numbers and force unbounded storage; reject or evict data outside the configured window.

• Sequence-number wraparound requires modular comparison rather than ordinary integer comparison. For a sequence space of size $2^n$, compare differences only when the valid receive window is less than $2^{n-1}$; otherwise “before” and “after” become ambiguous.

• Duplicate suppression should occur after clipping against already delivered and buffered ranges. A packet fully below next_expected contributes nothing; a partially overlapping packet should retain only its unseen suffix or disjoint portions.

• Packet arrival does not imply stream progress. A reassembler should distinguish received bytes, delivered bytes, highest observed sequence, and end-of-stream; a FIN/end marker may arrive before the final missing bytes.

• Correctness invariants are more valuable than ad hoc tests: emitted bytes are strictly ordered, each byte is emitted at most once, next_expected advances only through contiguous data, and buffered intervals never overlap after normalization.

• Concurrency requires a clear ownership model. A per-stream mutex is straightforward; sharding streams across workers improves throughput. Never let callbacks execute while holding the reassembly lock, or a slow consumer can block packet ingestion and create avoidable deadlocks.

• Recovery policy depends on protocol semantics. For a reliable transport, retain gaps and wait for retransmission; for a bounded-latency telemetry stream, expose a timeout or gap marker. The choice is a correctness-versus-latency tradeoff, not an implementation detail.

Worked example: Network Packet Stream Reassembly

For “Network Packet Stream Reassembly,” a strong candidate first clarifies whether packets can arrive out of order, whether sequence numbers wrap, whether overlapping payloads are legal, and whether the API must block, timeout, or report gaps. They would declare a byte-oriented model, half-open intervals, one logical stream per reassembler, and a finite receive window. The answer can be organized around four pillars: normalize and validate packets, merge them into an ordered interval structure, advance the contiguous frontier, and enforce resource and concurrency limits. The key state is next_expected, an ordered set of non-overlapping buffered intervals, buffered-byte count, and optional end-of-stream metadata. A concrete decision to flag is “first-wins versus latest-wins” overlap handling, since inconsistent policies can create endpoint desynchronization and security bugs. They should explain that a duplicate packet is harmless after clipping, while a packet containing a gap is buffered rather than emitted. They would close by saying that, with more time, they would add property-based tests, wraparound tests, fuzzing for malformed intervals, and metrics for gap age, buffer pressure, and rejected bytes.

A second angle

A different framing is a live log or media stream where waiting forever for a missing packet is unacceptable. The same interval machinery applies, but the API now needs gap timers, maximum reassembly latency, and an explicit policy such as skip, zero-fill, or terminate the stream. The candidate should separate transport correctness from application policy: the core can report “bytes available through offset X, gap begins at X,” while the caller decides whether latency or completeness matters more. This version also makes backpressure and cancellation central, because a slow consumer must not allow buffered data to grow without bound.

Common pitfalls

Pitfall: Treating packets as indivisible chunks and appending them whenever they arrive fails on out-of-order delivery and overlapping ranges. Store byte intervals and advance output only from the contiguous frontier.

Pitfall: Saying “use a hash map” without discussing overlap, ordering, or complexity sounds incomplete. Name the invariant, explain how intervals merge, and state why an ordered structure is appropriate.

Pitfall: Ignoring sequence wraparound, malicious far-future packets, or memory limits is a depth mistake. A production answer should specify modular comparison, receive-window validation, and measurable resource caps.

Connections

The interviewer may pivot to TCP receive windows, sliding-window protocols, backpressure, and flow control. Other natural extensions include checksum validation, retransmission timers, event-loop concurrency, and property-based testing of stream invariants.

Further reading

• RFC 793 — Transmission Control Protocol — foundational TCP sequencing, acknowledgments, and receive-window behavior.

• RFC 9293 — Transmission Control Protocol — current consolidated TCP specification, including sequence-number and reassembly semantics.

• RFC 5961 — Improving TCP’s Robustness to Blind Attack — useful security context for sequence validation and adversarial packets.

Practice questions

Focus area — You selected streams and rated reservoir sampling, sliding windows, and HyperLogLog shaky; review online state updates and approximations.

What's being tested

Streaming algorithms and online aggregation test whether you can compute useful answers over unbounded, high-velocity data without storing every event. The interviewer is probing algorithm selection, error guarantees, memory/latency tradeoffs, mergeability across workers, and behavior under duplicates, out-of-order arrivals, and changing time windows. For a Software Engineer at OpenAI, this matters when building low-latency telemetry, usage limits, evaluation dashboards, safety counters, and operational metrics where exact batch recomputation is too slow or expensive.

Core knowledge

• Online aggregation processes each item once, maintaining a compact state rather than retaining the full stream. State should support update(event), query(), and ideally merge(other) so independently processed partitions can be combined.

• Exact counters and sums require $O(1)$ state per key, but unbounded distinct keys require storage proportional to cardinality. For bounded keyspaces, use sharded maps and atomic increments; for millions of keys, explicitly discuss eviction, quotas, or approximate summaries.

• Welford’s algorithm computes a numerically stable mean and variance online. For each value $x_n$, update $\delta=x_n-\mu_{n-1}$, $\mu_n=\mu_{n-1}+\delta/n$, and $M_{2,n}=M_{2,n-1}+\delta(x_n-\mu_n)$; variance is $M_2/(n-1)$.

• Count-Min Sketch estimates item frequency using $d$ hash rows and width $w$. It guarantees, with probability at least $1-\delta$, overestimation error roughly $\epsilon N$ when $w\approx e/\epsilon$ and $d\approx\ln(1/\delta)$; it never underestimates, assuming nonnegative updates.

• Heavy hitters can be found with a Count-Min Sketch plus a candidate set, or with Space-Saving. A sketch alone does not identify which keys are frequent; retaining candidates, sampling keys, or maintaining a heap is necessary for top-$K$ queries.

• HyperLogLog estimates distinct cardinality using $m$ registers and leading-zero statistics. Its relative standard error is approximately $1.04/\sqrt m$; union is mergeable by register-wise maximum, making it useful across workers and shards.

• Reservoir sampling maintains a uniform sample of $k$ items from an unknown-length stream using $O(k)$ memory. Keep the first $k$ items; for item $i>k$, replace a random reservoir element with probability $k/i$. The result is unbiased only if every item has equal sampling eligibility.

• Sliding windows are different from lifetime aggregates. Exact time windows need expiring state, commonly ring buffers of fixed buckets; approximate windows use tumbling or hopping buckets. A five-minute tumbling window can have boundary artifacts, while hopping windows improve smoothness at higher compute cost.

• Exponential decay emphasizes recent events without explicit expiration: $A_t=\lambda^{\Delta t}A_{\text{previous}}+x_t$, where $0<\lambda<1$. Choose half-life $h$ with $\lambda=e^{-\ln 2/h}$; this is efficient but does not represent a strict “last five minutes” count.

• Mergeability is a central design criterion. Sums, counts, min/max, HyperLogLog, and compatible sketches merge naturally; medians and exact quantiles do not. For quantiles, use t-digest or KLL sketches, and state their approximation behavior rather than claiming exactness.

• Approximate quantiles must distinguish rank error from value error. A rank-error guarantee says the returned value is near position $qN$ in sorted order; this is more meaningful than a fixed numeric error when latency distributions span milliseconds to hours.

• Distributed correctness requires deciding how duplicates and retries behave. Use event IDs with deduplication when exact counting matters, or design updates to be idempotent; “at-least-once delivery plus increment” can inflate counters. State whether results are immediately consistent, eventually consistent, or bounded-stale.

• Numerical and operational limits matter: use 64-bit counters, guard timestamp overflow, define behavior for negative updates, and monitor sketch saturation. Memory should be estimated explicitly—for example, a sketch with $d=7$ and $w=20{,}000$ needs about 140,000 counters before metadata and sharding overhead.

Worked example

Because no concrete interview prompt was supplied, use this representative prompt: “Design an online aggregation API for request metrics.” In the first 30 seconds, clarify whether the API needs exact counts, distinct users, percentiles, or top endpoints; define acceptable error, freshness, retention window, event volume, and duplicate semantics. I would organize the answer around four pillars: per-key state, time-window representation, horizontal partitioning and mergeability, and query latency plus operational safeguards. For exact request counts over a bounded set of metrics, I would use sharded counters; for distinct users, HyperLogLog; and for latency percentiles, a mergeable KLL or t-digest rather than storing samples indefinitely. I would partition updates by metric key, periodically merge shard summaries, and expose the timestamp or window represented by each result. The key tradeoff is exactness versus memory: exact five-minute per-endpoint percentiles may be too expensive, while an approximate sketch can provide a documented rank-error bound with predictable memory. I would explicitly address retries by requiring event IDs or accepting bounded overcounting if the source is at-least-once. If I had more time, I would specify hot-key mitigation, snapshot and recovery behavior, benchmark update/query p99, and test error against an exact offline computation.

A second angle

A different representative prompt is “Maintain the top 100 most-used tokens from an unbounded stream.” The framing shifts from general metric aggregation to identifying keys, so a simple counter is insufficient: the algorithm needs candidate retention and replacement. A Count-Min Sketch can estimate frequencies compactly, while a min-heap or Space-Saving structure maintains likely heavy hitters. The important constraint is that approximate frequency estimates may reorder near-tied items, so the API should document that the returned boundary is not exact. In a distributed deployment, merge behavior and candidate reconciliation become as important as per-event update cost.

Common pitfalls

Pitfall: Saying “use a hash map” for every stream problem ignores unbounded cardinality and can turn a constant-time update into an eventual out-of-memory failure. State when exact state is bounded, and choose a sketch, sampling method, TTL, or eviction policy when it is not.

Pitfall: Claiming that a Count-Min Sketch gives exact counts, or that HyperLogLog returns exact distinct users, is a serious analytical error. Name the direction of bias, error metric, confidence or relative-error bound, and how you would validate approximation against a smaller exact sample.

Pitfall: Jumping directly to Kafka, databases, and deployment diagrams without first clarifying the aggregate, window, freshness, and duplicate requirements misses the algorithmic decision. Start with the state transition and correctness contract, then map it onto distributed components.

Connections

An interviewer may pivot to consistent hashing, idempotency, checkpointing, and fault recovery, or to rate limiting algorithms such as token bucket and leaky bucket. They may also connect this topic to distributed snapshots, approximate quantiles, and observability systems such as Prometheus, where cardinality control and label design directly affect memory and query cost.

Further reading

• “An Optimal Algorithm for the Estimation of Frequencies in Streams” — seminal Count-Min Sketch paper and error analysis.

• “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm” — foundational distinct-counting algorithm and mergeability properties.

• Mining of Massive Datasets, Chapter 4: Mining Data Streams — practical treatment of sampling, sketches, filtering, and stream constraints.

Practice questions

Focus area — You selected caching, and LRU, LFU, TTL expiration, invalidation, and cache stampede were all marked shaky.

What's being tested

This topic tests whether you can design a bounded, low-latency data structure while preserving clear concurrency semantics, correct eviction behavior, and predictable failure modes. The interviewer is probing beyond “use a hash map plus LRU”: they want synchronization boundaries, complexity analysis, capacity accounting, and a plan for contention, expiration, invalidation, and cache misses. This matters for a Software Engineer because a cache often sits directly on a critical request path, where a race or lock convoy can become a broad availability or latency incident.

Core knowledge

• A basic LRU cache combines a hash map for key lookup with a doubly linked list for recency ordering: Get, Put, promotion, and eviction are all $O(1)$ time and $O(N)$ space. Updating recency makes reads mutating operations.

• Define linearizability before choosing locks: each Get, Put, delete, or eviction should appear to take effect at one instant. Decide whether stale reads are acceptable; strict recency and strict capacity usually require stronger synchronization than eventual cache metadata.

• A single mutex around the map and list is the simplest correct design, but all readers and writers serialize. It can be appropriate for modest traffic, while high-contention workloads usually need sharding or finer-grained synchronization.

• Lock striping partitions keys across $S$ shards, each with its own map, list, lock, and capacity. Operations remain expected $O(1)$, but global LRU becomes approximate unless cross-shard coordination is added; per-shard limits can waste capacity under skew.

• A concurrent read-write lock is not automatically better: LRU promotion means a Get writes metadata, so it often cannot use a shared read lock. Separate immutable values from recency bookkeeping only when the weaker consistency is explicitly acceptable.

• Capacity must have a precise unit: entries, bytes, weighted cost, or a mixture. For weighted entries, evict until $\text{current\_weight} \le \text{max\_weight}$, and handle an item whose weight alone exceeds the limit deterministically—usually reject or avoid caching it.

• TTL expiration and recency eviction solve different problems. Lazy expiration checks timestamps on access and avoids a timer per entry; proactive expiration requires a heap, timing wheel, or janitor thread and introduces shutdown, scan, and synchronization concerns.

• Avoid cache stampedes when many callers miss simultaneously. A per-key single-flight mechanism lets one caller load the value while others await the same result; bound loader time, propagate errors, and decide whether failures are cached.

• Eviction policy affects hit rate, not just implementation complexity. LRU favors temporal locality; LFU can preserve historically hot keys; TinyLFU-style admission resists one-time scans but requires frequency metadata and more complex aging.

• Distinguish cache state transitions: absent, loading, present, expired, invalidated, and failed. If deletion races with an in-flight load, use a generation/version token or invalidate-after-load rule so an old result cannot resurrect deleted data.

• Instrument behavior with hit_rate, miss rate, eviction count and reason, load latency, entry count, resident weight, lock-wait time, and p50/p99 operation latency. A high hit rate can still hide unacceptable tail latency caused by contention or serialization.

• State the consistency and failure contract explicitly: whether values may be stale, whether eviction is best effort, whether Get can invoke user code, and what happens when the cache is full, the loader fails, or the process restarts.

Worked example — Concurrent Cache Design And Eviction

Start by clarifying the API, maximum size, whether size means entries or bytes, whether values may be stale, required Get/Put latency, and whether exact global LRU is mandatory. I would assume a process-local cache with concurrent callers, bounded weighted capacity, optional TTL, and a best-effort eviction policy unless the interviewer specifies otherwise. I would organize the design around four pillars: the hash-map/list representation, synchronization and linearizability, eviction and expiration semantics, and stampede protection plus observability. The simplest baseline is one mutex protecting both the map and LRU list, giving expected $O(1)$ operations and an easy correctness argument. If contention is demonstrated, I would move to sharded caches, explicitly accepting approximate global recency or adding a more expensive global admission mechanism. I would ensure loaders execute outside the shard lock, while a per-key in-flight record prevents duplicate loads and a version check prevents stale results from repopulating an invalidated key. The key tradeoff is exact global LRU versus scalable concurrency: exact ordering requires coordination across shards, while approximate per-shard eviction is usually cheaper and more robust. If I had more time, I would specify benchmark workloads, lock-contention tests, eviction-race tests, memory accounting, and shutdown behavior for TTL workers.

A second angle — TTL, invalidation, and cache stampede

A cache for configuration or authorization data frames the problem differently from a pure hot-object cache: correctness may depend more on bounded staleness than on maximizing hit rate. The design should combine TTL with explicit invalidation, and it should define what happens during an upstream outage after an entry expires. Single-flight loading prevents a synchronized expiration from overwhelming the backing service, while jittered TTLs reduce synchronized refreshes across processes. The interviewer may also probe whether an invalidation racing with refresh can be lost; versioned entries or invalidate-after-load semantics provide a concrete answer.

Common pitfalls

Pitfall: Treating Get as read-only and protecting it with a shared read lock while it updates LRU metadata creates races or inconsistent list pointers. Either serialize promotion correctly or state that recency is approximate and use a separate safe mechanism.

Pitfall: Saying “use LRU” without defining capacity, expiration, and concurrent miss behavior leaves the important contract unspecified. A stronger answer names the state transitions, lock scope, oversized-entry policy, and whether duplicate loads are coalesced.

Pitfall: Overengineering immediately with lock-free lists, custom atomics, or exact global ranking obscures the correctness baseline. Start with a single-lock implementation, identify measured bottlenecks, then justify sharding or approximate policies with workload assumptions.

Connections

An interviewer may pivot to consistent hashing for a distributed cache, cache-aside versus write-through invalidation, or single-flight request coalescing. They may also connect eviction to memory allocators, backpressure, observability, and tail-latency debugging.

Further reading

• “The Adaptive Replacement Cache” — foundational work on balancing recency and frequency under changing workloads.

• “TinyLFU: A Highly Efficient Cache Admission Policy” — explains admission control that improves hit rate under scan-heavy traffic.

• Go sync/singleflight documentation — concrete reference for suppressing duplicate concurrent loads.

Practice questions

Focus area — You selected transactions/snapshots; MVCC, snapshot isolation, and serializable isolation were marked new, with OCC and WAL shaky.

What's being tested

This topic tests whether you can reason precisely about concurrent transactions, not merely recite isolation-level names. You should be able to identify anomalies, explain how MVCC implements visibility, choose an appropriate isolation level, and recognize when locks or serializable execution are required. OpenAI systems often coordinate durable state, quotas, jobs, permissions, and billing-like invariants, where a rare race can become a correctness or safety incident. The interviewer is probing whether you can connect an abstract guarantee to concrete database behavior, latency, contention, and failure modes.

Core knowledge

• Atomicity, consistency, isolation, durability (ACID) are separate properties. Isolation controls interleaving; consistency means declared constraints remain valid; durability depends on logging and storage. Do not claim “ACID” automatically means every transaction behaves serializably.

• Read committed usually prevents dirty reads but allows non-repeatable reads and phantoms. In Postgres, each statement gets a snapshot; two SELECTs in one transaction may observe different committed states.

• Repeatable read provides a stable transaction-level snapshot in many MVCC databases. In Postgres, it prevents ordinary non-repeatable reads and phantoms but can abort on concurrent update conflicts; MySQL InnoDB has related but not identical semantics.

• Serializable isolation guarantees an outcome equivalent to some serial transaction order. Implementations use strict two-phase locking, Serializable Snapshot Isolation (SSI), or validation; stronger correctness costs blocking, aborts, memory, or throughput.

• MVCC stores multiple row versions, commonly with transaction IDs and commit metadata. A reader chooses versions visible to its snapshot, so readers can avoid blocking writers; old versions require garbage collection such as VACUUM in Postgres.

• A snapshot is typically defined by committed transactions visible at a point in time. A version is visible if its creating transaction committed before the snapshot and its deleting transaction was not yet visible; exact metadata and rules are engine-specific.

• Lost update occurs when concurrent read-modify-write operations overwrite one another. Prevent it with an atomic SQL update, a conditional predicate such as WHERE version = ?, SELECT ... FOR UPDATE, or serializable execution—not merely by wrapping reads and writes in a transaction.

• Write skew is the critical snapshot-isolation anomaly: two transactions read a shared invariant, update disjoint rows, and jointly violate that invariant. Lock a common coordination row, use a constraint that the database can enforce, or use serializable isolation.

• Pessimistic locking acquires locks before changing or reading protected data; SELECT ... FOR UPDATE is a common pattern. Optimistic concurrency control detects conflicts at commit or through version predicates, often improving throughput when contention is low but causing retries under load.

• Deadlocks arise from cyclic lock waits, even when every individual transaction is correct. Keep transactions short, access tables and rows in a consistent order, configure lock timeouts, and retry only bounded, safely replayable transactions.

• Isolation is distinct from durability and replication visibility. A committed write on the primary may not immediately appear on a lagging replica; route correctness-sensitive reads appropriately, and do not use replica reads for a read-your-writes guarantee without a session or log-position mechanism.

• Transaction boundaries should match the invariant being protected. Holding a transaction across network calls increases lock duration and failure exposure; doing the business decision outside the transaction without a recheck creates a race. Prefer short database-local transactions with explicit predicates.

Worked example

Representative prompt: “Explain transaction isolation and MVCC.” In the first 30 seconds, a strong candidate would ask which database engine is intended, whether the goal is throughput or strict serializability, and whether examples should include concurrent writes, while declaring that isolation semantics are engine-specific. They would organize the answer around four pillars: anomalies and guarantees, snapshot/version visibility, lock-based versus optimistic conflict handling, and operational tradeoffs such as aborts, deadlocks, and vacuum. They would explain that READ COMMITTED commonly takes statement snapshots, while repeatable read takes a transaction snapshot, so readers can avoid blocking writers but may observe different behavior across engines. They would use a write-skew example, such as two doctors independently taking themselves off call while an invariant requires one doctor to remain, to show why snapshot isolation is not always serializable. They would explicitly flag the tradeoff between serializable isolation and lower isolation: serializable protects invariants but may increase blocking or transaction retries. They would distinguish SELECT ... FOR UPDATE from a plain read and explain why a lock must cover the rows or coordination object relevant to the invariant. They would close by saying that, with more time, they would examine the engine’s execution plans, lock-wait metrics, retry policy, and replica-read behavior under failure.

A second angle

Representative prompt: “Two concurrent requests can both observe available quota and exceed the limit; how would you prevent it?” The framing shifts from explaining internals to selecting a correctness mechanism for a concrete invariant. A strong answer would prefer an atomic conditional update such as UPDATE quota SET used = used + ? WHERE used + ? <= limit, then verify affected-row count, rather than relying on a separate read followed by a write. If the invariant spans multiple rows or resources, they would consider a coordination-row lock, a database constraint, or serializable isolation with bounded retries. They would also discuss idempotency so a client retry does not consume quota twice.

Common pitfalls

Pitfall: Saying “repeatable read prevents all anomalies” is too broad. It may prevent dirty and non-repeatable reads while still permitting write skew, depending on the database; name the engine and identify the invariant being protected.

Pitfall: Listing dirty read, phantom read, and serializability definitions without describing an interleaving sounds memorized. Show two transactions, state what each reads, and identify the incorrect final state or guarantee.

Pitfall: Treating MVCC as “readers never block writers” ignores locks, predicate conflicts, schema changes, garbage collection, and serialization failures. Explain the common fast path, then mention the cases that still block or abort.

Connections

An interviewer may pivot to deadlock detection, optimistic concurrency control, database indexing and lock scope, or distributed transaction boundaries. They may also connect isolation to idempotency, retry safety, replication lag, and consistency models such as linearizability.

Further reading

• “Serializable Snapshot Isolation in PostgreSQL” — explains how Postgres detects dangerous structures without traditional blocking for every read.

• Designing Data-Intensive Applications, Martin Kleppmann — clear treatment of isolation anomalies, MVCC, serializability, and distributed consistency.

• A Critique of ANSI SQL Isolation Levels, Berenson et al. — formalizes why isolation-level names alone are insufficient.

Practice questions

Focus area — You selected concurrency, and mutexes, condition variables, semaphores, atomics, and deadlock/livelock/starvation were marked shaky.

What's being tested

This topic tests whether you can reason precisely about concurrency, choose an appropriate synchronization primitive, and explain the correctness and performance consequences. An interviewer is probing beyond “put a mutex around it”: can you identify the shared invariant, define the critical section, account for memory visibility, and prevent races without serializing the entire system? For OpenAI-scale services, these skills matter because high-throughput request handling, schedulers, caches, queues, and resource managers all combine parallelism with failure-sensitive shared state.

Core knowledge

• A data race occurs when two threads access the same memory concurrently, at least one access is a write, and there is no established happens-before relationship. A race can produce undefined behavior in C++, not merely a stale value.

• A mutex provides mutual exclusion and typically ownership: one thread locks, performs a short critical section, then unlocks. Prefer scoped guards such as C++ `std::lock_guard` or `std::unique_lock` so exceptions and early returns cannot leak the lock.

• A semaphore represents permits rather than ownership. A counting semaphore is appropriate for limiting concurrent access to a pool of size $N$; a binary semaphore is not automatically equivalent to a mutex because ownership and misuse detection differ.

• Use condition variables when a thread must wait for a state predicate, such as “queue is nonempty.” Always wait in a loop—`cv.wait(lock, predicate)`—because wakeups can be spurious and another consumer may observe the state first.

• Atomics are ideal for independent counters, flags, and lock-free state transitions, but atomic individual fields do not make a multi-field invariant atomic. Choose memory ordering deliberately: relaxed provides atomicity, while acquire/release establishes visibility across threads.

• A deadlock requires four Coffman conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait. Break any one—for example, impose a global lock order to eliminate circular wait—or use timeouts, cancellation, or preemption where appropriate.

• Lock ordering assigns a total or partial order to locks; every code path acquires them in ascending order. If code may need locks `A` and `B`, consistently acquire `A` before `B`, including error paths and callbacks.

• Avoid calling unknown code while holding a lock: logging, user callbacks, allocation, network I/O, and waiting on futures can re-enter the component or acquire locks in an undocumented order. Keep critical sections small, but do not split them so far that invariants become temporarily observable.

• Reader-writer locks can improve read-heavy workloads but may starve writers, incur upgrade complexity, and perform worse than a mutex under contention. Measure contention and workload distribution rather than assuming parallel reads are beneficial.

• A livelock occurs when threads remain active but make no progress, often due to repeated retries or symmetric backoff. Starvation occurs when one thread waits indefinitely while others progress; fairness guarantees, queueing, or bounded retries address it differently from deadlock prevention.

• For producer-consumer structures, protect both the queue and its predicate under the same mutex: enqueue, update state, and notify while synchronized. A notification is not a stored event, so notifying before the waiter begins waiting is safe only when the predicate is maintained correctly.

• Deadlock detection can use a wait-for graph: vertices are threads or transactions, and an edge $T_i \rightarrow T_j$ means $T_i$ waits for a resource held by $T_j$. A cycle indicates deadlock; production systems may instead use lock-order instrumentation, watchdogs, thread dumps, or database deadlock detectors.

Worked example

No concrete interview question was supplied, so consider the representative prompt: “Design a thread-safe bounded blocking queue.” In the first 30 seconds, clarify whether multiple producers and consumers are supported, whether `put` and `take` block or time out, what shutdown means, and whether FIFO fairness is required. I would organize the answer around the queue invariant and capacity, synchronization and memory visibility, blocking predicates, and shutdown/error behavior. A standard design uses one mutex, `not_empty` and `not_full` condition variables, and predicates `size > 0` and `size < capacity`. Producers acquire the mutex, wait in a loop for space, append, unlock, and notify consumers; consumers symmetrically wait for an item, remove one, unlock, and notify producers. I would explicitly choose `notify_one` for ordinary throughput, while noting that shutdown may require `notify_all` so every waiter can observe the terminal state. The key tradeoff is one mutex for simplicity and a clear invariant versus separate locks for higher concurrency and substantially greater correctness risk. I would close by saying that, with more time, I would discuss cancellation, bounded wait time, fairness, metrics for queue depth and wait duration, and stress testing under forced thread interleavings.

A second angle

The same reasoning applies to a thread-safe cache, but the dominant constraint changes from blocking coordination to read/write contention and eviction consistency. I would clarify whether stale reads are acceptable, whether values are expensive to compute, and whether eviction must be exact under concurrency. A mutex may be sufficient for a small cache, while sharding by hash can reduce contention; each shard then needs a clearly documented lock scope. If cache misses compute values while holding a lock, unrelated requests can stall or recursive computation can deadlock, so single-flight coordination or compute-outside-lock patterns deserve explicit discussion.

Common pitfalls

Pitfall: Saying “use an atomic counter” for a compound invariant such as `size` plus queue contents. The counter may be atomic while the enqueue/dequeue relationship remains racy; identify the complete state that must change together.

Pitfall: Listing mutexes, semaphores, and condition variables without stating the predicate and ownership model. A stronger answer explains who owns each resource, what condition a waiter checks, and which operation changes that condition.

Pitfall: Claiming that lock ordering “prevents all concurrency bugs.” It prevents a class of circular-wait deadlocks, but not races, livelocks, starvation, forgotten unlocks, use-after-free, or deadlocks caused by hidden locks and callbacks.

Connections

An interviewer may pivot to lock-free algorithms, memory models, and linearizability, asking where an atomic compare-and-swap fits. Other natural connections include distributed locks, database transaction deadlocks, actor/message-passing designs, and observability through contention metrics, thread dumps, and scheduler traces.

Further reading

• Operating Systems: Three Easy Pieces, chapters on Concurrency — clear treatment of locks, condition variables, semaphores, and common concurrency failures.

• C++ Concurrency in Action, Anthony Williams — practical coverage of C++ memory ordering, locking patterns, and thread-safe design.

• [Java Concurrency in Practice, Brian Goetz et al.] — foundational discussion of happens-before relationships, safe publication, and composing concurrent components.

Focus area — Matches your stream/networking focus: byte framing, ordering, persistent logs, corruption handling, and robust deserialization.

What's being tested

Demonstrates designing reversible, delimiter-free binary serialization and a crash-consistent persistent key-value store: encoding arbitrary bytes/Unicode, managing offsets/indexes, and safe disk writes. Interviewers probe correctness across edge cases, complexity reasoning, and simple durability guarantees.

Patterns & templates

• Length-prefix encoding: store a fixed-width (e.g., 4- or 8-byte) big-endian length before bytes; decode by reading length then exact payload, O(n) serialize/deserialize.

• Varint / zigzag for compact integer lengths: saves space for small values; implement decode loop carefully to avoid infinite loops.

• Append-only log + in-memory index: append records to file, keep HashMap<key, offset> for O(1) get; rebuild index by scanning on startup.

• Per-record checksum (e.g., CRC32) after payload to detect partial writes or corruption before using a record.

• Atomic replace pattern: write to temp file, fsync data and metadata, then rename to swap files atomically on POSIX.

• Compaction/GC: background pass copies live entries to new file, then atomic swap; avoid holding long-lived locks during compaction.

• Edge-size handling: support empty keys/values and very large blobs by streaming IO and limiting in-memory buffers.

Common pitfalls

Pitfall: Using a byte delimiter (e.g., \0) fails for arbitrary binary data — always prefer length-prefix or escape-free encodings.

Pitfall: Forgetting to fsync metadata (fsync on directory after rename on some platforms) breaks durability guarantees on crash.

Pitfall: Rebuilding index by naive memory structures without bounds can OOM on millions of keys — consider sharding, sparse indexes, or on-disk B-tree.

Practice these

the practice cards below cover the canonical variants — solve all of them and time yourself

Practice questions

Focus area — You selected transactions/snapshots, and related MVCC/snapshot isolation concepts were marked new.

What's being tested

These problems test building a mutable directed graph that supports versioning and efficient snapshotting for point-in-time queries alongside live mutations. Interviewers probe data structures (per-edge logs, hash maps, balanced trees), algorithmic complexity for queries and updates, and memory/time tradeoffs when producing recommendations from historical graph state.

Patterns & templates

• Per-edge event lists: store adds/removes as timestamped ops in sorted arrays; use binary search for membership at version V, O(log m) per edge lookup.

• Immutable snapshots via copy-on-write: keep a root pointer to shared structures so snapshot creation is O(1) and mutations copy only changed nodes, amortized efficient for sparse updates.

• Sparse version index / change logs: maintain Map<version, root> or per-node change lists to replay until V; snapshot creation O(1), point-in-time rebuild cost depends on log length.

• In-memory adjacency map: Map<node, Map<neighbor, List<(ts, op)>>> gives O(1) node access; watch memory for high-degree vertices and prefer compressed neighbor lists.

• Ordered containers for fast range queries: use TreeMap/skiplist or arrays + bisect to find prefix/suffix of events in O(log n)+O(k) to scan k events.

• Recommendations via mutual intersections: iterate the smaller neighbor list and hash-count candidates, use a size-k heap for top-k, cost ~O(sum small_deg + m log k).

• Compaction/checkpointing: checkpoint full adjacency at intervals and drop old deltas to bound read/replay cost; tune checkpoint frequency to update rate.

Common pitfalls

Pitfall: Treating unfollow as instantaneous deletion without a timestamp makes point-in-time queries ambiguous and yields wrong historical membership.

Pitfall: Assuming snapshot = deep copy; naive copies are O(N) and blow up memory — prefer structural sharing or periodic checkpoint+delta strategies.

Pitfall: Building recommendations by intersecting all neighbors (all-pairs) — this can be O(n^2) on heavy nodes; always iterate the smaller set or use sampling.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions

Onsite — 19 min

System Design

Focus area — Directly overlaps your packets-out-of-order note: late data, duplicates, reconciliation, retries, stale status, and safety policies.

What's being tested

Candidates must show they can design a resilient, event-time-aware telemetry system for intermittently connected devices: define clear APIs, choose stateful streaming semantics, reconcile late or duplicate events, and ensure safe command dispatch with idempotency and auditing. Interviewers probe distributed-state choices, event-time vs processing-time reasoning, tradeoffs between latency and correctness, and concrete failure modes (clock drift, network partitions, device reboots).

Core knowledge

• Event time vs processing time: event time is the timestamp generated by the device; processing time is when the server sees it. Correct historical metrics require event-time semantics and handling of out-of-order arrivals.

• Watermarks & allowed lateness: a watermark = max_seen_event_time − lateness_bound (L). Use watermarks to emit windows; keep state for an extra L to accept late arrivals and trigger retractions if needed.

• Windowing and retention math: if average ingress = R events/sec and allowed lateness = L seconds, expected late-state memory ≈ R * L * average_event_size. Quantify to choose memory vs eviction policies.

• Idempotency & deduplication: require clients to include monotonic event IDs or (device_id, sequence, device_time); store recent IDs in compacted store (e.g. `RocksDB` or `Postgres`) to dedupe, with TTL based on allowed lateness.

• Append-only event store + compacted view: persist raw events immutably (for reprocessing/backfill). Maintain a compacted, materialized view for fast reads; rebuild via replay when late events arrive or schema changes.

• Exactly-once vs at-least-once: prefer at-least-once ingestion with application-level idempotency; exactly-once across distributed components is expensive (2PC, transactions) and often unnecessary for telemetry.

• Command dispatch semantics: commands need idempotency keys, sequence numbers, and ack semantics (ACK, NACK, UNKNOWN). Use optimistic command TTL and device-side de-dup logic; track per-device last-applied command version.

• Safety & auditability: for safety-critical control, include immutable audit logs of commands and telemetry, digital signatures or HMACs on device messages, and operator-facing explainability for retracted metrics.

• Reconciliation & backfills: build scheduled reconciliation jobs to scan raw events, re-evaluate aggregates, and write deltas or retractions into the materialized view; optimize with incremental computation.

• Stateful stream processing options: `Flink`/`Beam`/`Spark Structured Streaming` offer built-in event-time windows and state with checkpoints; local embedded state (e.g., `RocksDB`) plus checkpointing simplifies recovery.

• Clock drift and trust model: never blindly trust device clocks; allow device-side monotonic counters or server-assigned ingestion timestamps plus device clocks for ordering. Define behavior when device time differs by >X minutes.

• Operational SLOs & metrics: monitor `p99` ingestion latency, fraction of late events, dedupe rate, reconciliation lag, and command success/failure rates; these guide tuning of lateness bounds and retention.

Tip: require devices to include both a device-generated timestamp and a sequence number; server uses sequence for ordering and device timestamp for event-time semantics and audits.

Worked example — Design an IoT Logging Platform with Late-Arriving Metrics

Start by clarifying SLAs: acceptable reporting latency, maximum tolerable correction window (allowed lateness L), and scale (devices, events/sec). Organize the design around three pillars: (1) ingestion and durable raw storage (append-only topic + object store or `Postgres`/S3), (2) event-time stream processing that uses watermarks and maintains materialized aggregates with a lateness-bound L, and (3) reconciliation/backfill that replays raw events to correct aggregates and emits retractions or deltas. Define concrete APIs: client PUT includes (device_id, seq, device_ts, payload, signature) and server returns (ingest_id, server_ts). Flag the main tradeoff: larger L increases correctness but requires more state and delays final metrics; choose L from device connectivity patterns (e.g., 1 hour vs 24 hours). Also describe client behavior on network loss (buffer to disk with exponential backoff) and server dedupe using (device_id, seq) plus TTL. Close by noting next steps: implement end-to-end tests with simulated late arrivals, and if time permits add adaptive watermarks (advance faster for stable devices).

A second angle — Design Command Dispatch and Telemetry Reconciliation for Unreliable Devices

Here the same event-time and reconciliation concepts apply, but the system must treat commands as first-class, safety-critical state. Ask whether commands must be guaranteed delivered, executed exactly once, or only best-effort. Build a command ledger (append-only) with per-command idempotency keys and per-device sequence numbers; dispatch through a broker that persists until device ack. Use event-time telemetry to reconcile whether commands had the intended effect—telemetry events should reference the command id. For retries, cap attempts and escalate to human operators if no ack within a time budget. Explicitly surface the tradeoff: strict guarantees (exactly-once execution) require device-side transactional semantics and fencing tokens; most systems accept at-least-once execution plus idempotent handlers and compensating actions.

Common pitfalls

Pitfall: Treating processing-time as equivalent to event-time. Relying on ingestion timestamps produces incorrect historical metrics and incorrect command/telemetry order when devices are offline or clocks drift.

Pitfall: Not specifying client-side guarantees early. Failing to ask whether devices can persist state, include sequence numbers, or sign messages leads to brittle server designs that can't dedupe or verify authenticity.

Pitfall: Over-engineering exactly-once across the entire stack. Proposing distributed two-phase commits or synchronous cross-service transactions wastes time; prefer immutable logs + idempotency and selective transactional boundaries.

Connections

Interviewers may pivot to stream-processing internals (checkpointing, state backends), distributed consensus for leader election/fencing (e.g., `ZooKeeper`/`etcd`), or data-engineering concerns like efficient compaction and schema evolution for the raw event store.

Further reading

• [“Designing Data-Intensive Applications” — Martin Kleppmann] — chapters on logs, stream processing, and reprocessing explain append-only stores and event-time concepts.

• Apache Flink: Event Time & Watermarks (blog/documentation) — practical details on watermarks, lateness, and state management.

Practice questions

Worth reviewing for APIs, indexes, and mutation semantics, but less urgent than your shaky caching and transaction isolation addenda.

What's being tested

These prompts test translating SQL-like operations into efficient in-memory algorithms: data modeling, indexing, query execution (projection/filter/sort), and complexity reasoning. Interviewers probe choices of data structure (storage layout, indexes), algorithmic cost, and simple API/edge-case handling under memory constraints.

Patterns & templates

• std::unordered_map / hash table for point lookups — O(1) average, O(n) worst; good for exact-key get/put workloads.

• Sorted array or std::map (tree) for range queries — O(log n + k) to locate start, then sequential scan for k results.

• Columnar projection: read only needed columns to reduce memory bandwidth and cache misses; ideal when few columns are selected.

• Predicate pushdown: apply filters early to shrink working set before expensive operations like sort or join.

• Bitmap / bitset indexes for low-cardinality filters — fast boolean intersection, memory-efficient for millions of rows.

• Secondary index tradeoff: faster reads vs extra write + memory; build only on frequently filtered columns.

• Eviction/LRU for bounded-memory tests — maintain a recency queue and reclaim full rows or columns as configured.

• Stable sort / tie-breaker: use std::stable_sort when deterministic ordering (multi-key) matters; sorting costs O(n log n).

Common pitfalls

Pitfall: Counting only average-case hash complexity — interviewers will ask about worst-case and adversarial input; mention fallback (tree/hash with rehashing).

Pitfall: Ignoring memory for indexes — adding multiple secondary indexes can double/triple memory; quantify approximate per-row overhead.

Pitfall: Designing only for single-threaded access — at least mention concurrency/atomicity and simple locks or copy-on-write for reads.

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions