Google Software Engineer Interview Prep Guide

Your biggest focus is system design from first principles: sharding, replication, transactions, rate limiting, caching, offline sync, observability, and delivery semantics all show low self-ratings or shaky/new concept ratings. Coding also needs heavy coverage because you self-rated 1/5 and selected graphs, intervals, arrays, union-find, parsing-adjacent strings, grids, and scheduling-style problems with no solved-question signals yet. There are no strong solved/high-rating areas to keep truly brief, so behavioral stays at normal review while most coding and system design concepts get emphasized. For Google, this plan highlights search/autocomplete, cache invalidation, SRE-style observability, quota enforcement, and distributed consistency as the company-specific angles. With 1–3 months, budget most weekly study time to system design foundations and coding pattern drills, then reserve recurring lighter sessions for behavioral project stories.

Technical Screen — 78 min

Coding & Algorithms

• Core Array, String, Hash Map, Sliding Window, and Binary Search Patterns (Focus) — covered in depth under Online Assessment below.

• BFS/DFS Graph and Tree Traversal and Shortest Paths (Focus) — covered in depth under Onsite below.

• Trie and Prefix Indexing (Focus) — covered in depth under Onsite below.

• Heaps, Streaming Median, and Top-K Selection (Focus) — covered in depth under Onsite below.

System Design

• Secure Distributed Storage, Messaging, and Consistency (Focus) — covered in depth under Onsite below.

• Idempotency, Deduplication, and Delivery Semantics (Focus) — covered in depth under Onsite below.

• Google-Scale Search Indexing and Autocomplete System Design (Focus) — covered in depth under Onsite below.

• Google-Scale Caching and Cache Invalidation (Focus) — covered in depth under Onsite below.

Software Engineering Fundamentals

• Reliability, Observability, and Incident Diagnostics (Focus) — covered in depth under Onsite below.

• Concurrency, Scheduling, and State Machines (Focus) — covered in depth under Onsite below.

Onsite — 78 min

Coding & Algorithms

• Core Array, String, Hash Map, Sliding Window, and Binary Search Patterns (Focus) — covered in depth under Online Assessment below.

Focus area — You selected graph algorithms, grid traversal, union-find, and dynamic connectivity; no solved graph signals yet.

What's being tested

Candidates must demonstrate correct use of BFS and DFS for traversal, reachability, and component counting, plus shortest-path techniques (unweighted BFS, Dijkstra) under constraints. Interviewers probe algorithmic tradeoffs (time/space), correctness with blocked/forbidden nodes, and iterative vs recursive implementations to avoid stack overflow.

Patterns & templates

• BFS for shortest paths in unweighted graphs — use deque queue, mark visited on enqueue, time O(V+E), space O(V).

• DFS (recursive or explicit stack) for connectivity and nested structures; prefer iterative stack to avoid recursion depth issues.

• Dijkstra with heapq for weighted shortest paths; complexity O((V+E) log V); store distances and parents for path reconstruction.

• Multi-criteria shortest path: encode tuple cost (danger_count, steps) and use lexicographic comparison in priority queue or use 0-1 BFS for binary costs.

• Remove/ignore blocked nodes by pre-marking in set or deleting adjacency entries before traversal.

• Connected clusters (geometric): build adjacency by threshold distance squared to avoid sqrt, deduplicate coordinates with a set, then BFS/DFS for components.

• Deleting in a binary search tree: handle leaf, single-child, two-children cases — replace with inorder successor (min in right subtree) and adjust pointers.

Common pitfalls

Pitfall: Marking visited only on pop instead of on enqueue causes duplicate enqueues and exponential blowup on dense graphs.

Pitfall: Using sqrt for many distance checks costs CPU and risks floating error — compare squared distances instead.

Pitfall: Recursing on deeply nested lists/trees without converting to an iterative stack risks stack overflow on large inputs.

Practice these

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

Practice questions

Focus area — You selected text indexing and fuzzy matching; Google autocomplete-style problems need precise prefix data-structure trade-offs.

What's being tested

Tests construction and use of a Trie (prefix tree) for efficient prefix indexing, exact-word lookup, and longest-prefix matching. Interviewers probe correctness (terminal vs. prefix), per-node metadata for fast top-K or frequency-aware queries, and time/space complexity tradeoffs.

Patterns & templates

• insert / search — traverse nodes per character, create child nodes as needed; O(L) time, O(1) extra space beyond nodes, where L is word length.

• Terminal flag vs. prefix — store is_end boolean and optionally an exact-word payload to distinguish words from mere prefixes.

• Per-node metadata — keep count, freq, or topK list at nodes to answer aggregate queries in O(L + K) time. Update these during insert/delete.

• Children representation — use hash map for variable alphabet or fixed array for small alphabets; memory ~O(total_chars) nodes × child-pointer-size.

• Lazy deletion — clear is_end and decrement metadata; prune nodes only when safe to avoid expensive recursive deletes.

• Longest-match replacement — greedy scan: advance as long as matching child exists and track last is_end; overall O(N + M) for text size N and average match M per start.

• Collect/top-K traversal — DFS from prefix node, early-stop with maintained heap for K best; complexity O(nodes_in_subtrie + K log K).

Common pitfalls

Pitfall: Treating every node with children as a word—forgetting to check is_end leads to false positives for exact search.

Pitfall: Failing to update per-node topK on deletes/updates, causing stale suggestions.

Pitfall: Assuming constant alphabet; using fixed arrays for large Unicode input wastes memory.

Practice these

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

Practice questions

Focus area — Not specifically flagged, but coding self-rating is 1/5 and top-K or streaming patterns are common Google screen material.

What's being tested

These problems test efficient use of heaps/priority queues and streaming order-statistics to maintain small summaries of large inputs (medians, k-th, top-k). Interviewers probe algorithmic reductions (k-way merge, two-heap median), complexity tradeoffs, and robust handling of duplicates and ties.

Patterns & templates

• Two-heap median: keep a max-heap for lower half and min-heap for upper half; rebalance sizes to differ ≤1; O(log n) per insert.

• Min-heap size-k for top-k: push items, pop when size > k; overall O(n log k) time, O(k) space.

• Max-heap via inversion: if only min-heap available (e.g., heapq), insert negated keys to simulate a max-heap.

• K-way merge for k smallest pairs: push initial pairs (i,0), pop smallest, then push (i,j+1); avoid duplicate exploration with indices.

• Frequency + heap for top-k words: count with hashmap, then maintain min-heap of (freq, word) with tie-break deterministic ordering, O(n + m log k).

• Lazy deletions for streams: mark removed elements in a hashmap and lazily pop stale heap entries to handle deletions efficiently.

Common pitfalls

Pitfall: Forgetting to rebalance the two heaps correctly — median becomes incorrect by one position after several inserts.

Pitfall: Using full sort instead of size-k heap when k << n, causing unnecessary O(n log n) work.

Pitfall: Not encoding tie-breakers in heap keys (e.g., (freq, word)), producing non-deterministic or wrong ordering.

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

Practice questions

System Design

Focus area — System design self-rating is 1/5; selected sharding, replication, transactions, rate limits, APIs, data modeling, and quotas all map here.

What's being tested

Candidates must show practical mastery of designing scalable, durable, and consistent distributed storage and messaging systems: partitioning, replication/consensus, durability vs latency tradeoffs, client-facing APIs, and multi-tenant operational concerns. Interviewers probe whether you can frame correctness constraints (ordering, delivery semantics, isolation), pick appropriate algorithms (consensus, MVCC, CAS), and justify tradeoffs for availability, performance, and cost in realistic failure modes. They also expect concrete engineering choices — data models, garbage collection, metadata placement, and how to observe and recover systems.

Core knowledge

• Partitioning (sharding): split data by key to scale throughput; choose consistent hashing or range partitioning depending on hot-key risk; each partition should be independently replicated and rebalanced.

• Replication & consensus: use leader-follower (e.g., Kafka) for high-throughput append logs or quorum consensus (RAFT, Paxos) for strong consistency; quorum = $\lfloor n/2\rfloor+1$ for n replicas.

• Durability & storage tiers: persist writes to WAL/append-only segments on local SSD, then tier cold objects to object stores (S3); segment sizes commonly 100MB–1GB for efficient compaction and recovery.

• Delivery semantics: clearly separate at-least-once, at-most-once, exactly-once; exactly-once typically requires idempotency + transactional writes (two-phase commit or idempotent producer with sequence numbers).

• Ordering & offsets: order guarantees usually per-partition; store consumer offsets in a durable, low-latency store (etcd/Zookeeper/internal offsets topic); allow manual/automatic offset management for replay.

• Deduplication & content-addressable storage: map content to hash-based IDs (e.g., SHA-256) for dedup; use reference counts or reachability GC; avoid counting race conditions with atomic CAS or distributed transactions.

• Large-payload handling: keep metadata in the log/queue and store large blobs in object store; pass pointers in messages to avoid broker memory spikes.

• Retention & compaction: support time/size-based retention and log compaction for latest-key semantics; compaction is CPU and IO heavy — plan background compaction windows and backpressure.

• Transactions & isolation: distributed transactions use coordinated commit (2PC) or transactional log with multi-writer epochs; prefer application-level idempotency or single-partition transactions to avoid cross-partition 2PC complexity.

• Authentication, authorization, encryption: require mutual TLS (mTLS) at the transport, RBAC for tenant isolation, and encryption-at-rest for sensitive blobs; keep token lifetimes short and log access-control decisions for audit.

• Monitoring & SLOs: instrument p99/p95 latency, throughput, tail-recovery time, replication lag, and GC pauses; SLOs drive choices: e.g., synchronous replication increases p99 but improves durability.

• Failure & recovery playbooks: design for fast leader failover, replica catch-up, and safe truncation; ensure metadata (topic list, partition assignment) is itself replicated and versioned.

Worked example — Design distributed message queue service

First 30s framing: ask about expected throughput, latency SLOs, message size distribution, ordering guarantees (global vs per-topic-partition), retention semantics, multi-tenancy, and exactly-once needs. Declare assumptions: per-partition ordering is OK, message sizes small (<1MB), throughput 100k msgs/sec per topic.

Skeleton pillars to present:

1. API model: Publish(topic, key, payload) and Subscribe(topic, partition) with consumer-group semantics and offset commit API.
2. Partitioning & routing: consistent hashing on key → partition to provide per-key ordering and balance.
3. Durability & persistence: append-only segmented logs on local disks, immediate fsync for durability when required, async replication.
4. Replication & failover: leader-follower per partition with RAFT-style majority for critical topics and configurable replication factor for others.
5. Consumer offset & delivery semantics: offsets stored durably; support at-least-once by default, exactly-once via idempotent producers + transactional commit for consumer offsets.

One concrete tradeoff: synchronous replication guarantees durability but increases end-to-end latency; offer topic-level policy to choose sync vs async replication. For large payloads, use pointers to external object store to prevent broker memory/IO explosion.

How to close: summarize SLOs and deployment assumptions, mention operational concerns (compaction windows, monitoring), and say "if I had more time I'd design the metadata service, simulate leader failover scenarios, and sketch client retry/backoff and quota enforcement."

A second angle — Design distributed transactions protocol

The same fundamentals (consensus, durable logs, coordination) apply but constraints shift: cross-shard atomicity demands a coordination protocol. For small-scale, prefer single-partition transactions to avoid distributed commit. For cross-partition, present coordinator-based 2PC built on a replicated log plus leader election; reduce blocking using optimistic concurrency control or cohort-prepared leasing and use timeouts and idempotent commit records to recover. Call out costly failure modes: coordinator crash leaves prepared state requiring careful GC. Tradeoffs: 2PC gives atomicity but sacrifices availability; consider sagas for looser consistency with compensating actions.

Common pitfalls

Pitfall: Designing for global total ordering by default. Total ordering across all keys kills scalability; prefer per-partition ordering and explain why the app actually needs global order.

Pitfall: Ignoring metadata scalability. Storing topic/partition metadata in a single node becomes a bottleneck; design metadata as a small replicated service and quantify limits (metadata ops/sec, number of partitions).

Pitfall: Over-promising exactly-once without implementation detail. Saying "we support exactly-once" without explaining idempotent producers, sequence numbers, and atomic offset commits will lose credibility; show the mechanism (transactional writes + offset commit).

Connections

Interviewers may pivot to adjacent topics like stream processing (stateful processing and time semantics), object storage design (cold-storage lifecycle and GC), or multi-region replication (geo-consistency models and conflict resolution). Be ready to discuss monitoring/playbooks and cost tradeoffs (e.g., hot-spot mitigation vs replication cost).

Further reading

• [Designing Data-Intensive Applications, Martin Kleppmann] — deep treatment of logs, replication, consensus, and transactions.

• The Kafka Papers & Confluent Blog — practical patterns for log-based messaging, partitioning, and storage tradeoffs.

Practice questions

Focus area — You marked delivery semantics, retries, offline sync, and conflict handling shaky or new; reliability needs extra space.

What's being tested

Candidates must demonstrate practical mastery of idempotency, deduplication, and delivery semantics in distributed systems: how to prevent duplicate effects, how to detect and discard duplicate events, and how to reason about at-most-once / at-least-once / exactly-once tradeoffs. Interviewers look for clear scoping questions, pragmatic designs that tolerate partial failures, measurable bounds (memory, latency), and concrete choices for sequencing, finality, and late-arriving data.

Core knowledge

• Delivery semantics: know definitions and tradeoffs: at-most-once (no retries), at-least-once (retries, duplicates possible), exactly-once (strongest, expensive). Exactly-once often implemented via idempotent handlers plus dedupe, or via transactional sinks (2PC) — cost vs complexity tradeoff.

• Idempotency key: a unique client- or producer-supplied token (e.g., request UUID) persisted for TTL to make handlers safe to retry; store it with outcome (success/failure) to return same result for replays.

• Deduplication window and state: dedupe requires state mapping (key -> processed-timestamp/outcome). In-memory maps handle ~1–10M keys per node; beyond that use sharded persistent store (Postgres, Redis, Cassandra) with TTLs or compaction to bound growth.

• Hash vs explicit id: do not dedupe by payload hash alone unless content-addressable semantics are intended — hash collisions and semantically-equivalent-but-distinct events can mislead. Prefer monotonic sequence numbers or explicit event IDs.

• Ordering vs partitioning: deterministic ordering requires a partition key and sequence numbers per partition. Global ordering across partitions implies single leader or global sequencer (scales poorly). Use Kafka partitions for per-key order guarantees.

• Event time vs processing time: for windows and finality, use event time with watermarks and allowed-lateness; processing-time-only designs mis-handle late arrivals leading to retractions/updates.

• Late arrivals & finality: define “final” (e.g., watermark + allowed lateness). Use tombstones or compensating events rather than trying to retroactively reorder already-acknowledged delivers.

• Probabilistic dedupe: Bloom filters or approximate set caches reduce memory but have false positives; acceptable when occasional dropped duplicate is tolerable. Always quantify false positive rate: $p \approx (1 - e^{-kn/m})^k$.

• Concurrency and uniqueness: for “one claim per user” use a unique DB constraint (e.g., unique(user_id, deal_id)) or atomic INSERT IF NOT EXISTS / UPSERT with conditional WHERE for optimistic concurrency. Relying solely on application-level locks is risky under failures.

• State compaction & GC: persist dedupe keys with TTL; implement compaction via background jobs or log compaction (e.g., Kafka log compaction), and garbage-collect stale state once finality is reached.

• Exactly-once streaming: frameworks like Flink/Kafka Streams implement “exactly-once” by combining checkpointed operator state with transactional sinks; but they trade latency for consistent snapshots and increased operational complexity.

• Dead-letter queues and poison messages: on repeated retries, move problematic messages to a DLQ and record diagnostic context; do not block foreground processing on a few stuck events.

• Instrumentation & SLAs: measure duplicate-rate, delivery-latency, p99 retry amplification, dedupe store size. Set TTLs and window sizes based on expected throughput and acceptable memory (e.g., TTL = expected max delivery delay + margin).

Worked example: Design a Personalized Weekly Deals Service

First 30s framing: ask traffic volume, deal claim semantics (one claim per user-deal), latency requirements for personalization, expected sources and correction patterns, and whether eventual corrections are acceptable. Skeleton pillars: (1) ingestion + deduplication for multi-source feeds, (2) active-window selection and ranking with stable pagination, (3) claim-handling with idempotency and concurrency controls, (4) expiration/garbage collection and metrics. For ingestion dedupe, accept canonical event ID or compute stable event key; persist dedupe keys in a sharded Redis with TTL equal to correction window. For claim handling, prefer a unique DB constraint on (user_id, deal_id) and perform INSERT with explicit idempotency key; if synchronous confirmation is needed, combine with conditional update (WHERE status IS NULL) to avoid races. One tradeoff to call out: synchronous strong consistency for claims (simple correctness) vs higher availability and throughput using async processing plus compensation (complexity in refunds/rollbacks). Close: “If I had more time I’d prototype DB schema, quantify dedupe cache sizing for peak QPS, and sketch metrics and backfill/repair paths.”

A second angle: Design at-least-once notification delivery

Same primitives apply but constraints differ: delivery is per-recipient, often low-latency and retry-heavy. Use idempotency keys per notification per device and store outcome per (recipient, notif_id). Implement exponential backoff and a DLQ for persistent failures. Ordering is often relaxed — prefer per-recipient FIFO queues if recipient order matters, otherwise parallelize. For push (APNs/FCM) vs email/SMS, dedupe window and retry strategy change; for push, de-duplicating identical payloads can reduce cost, while for email dedupe must avoid sending multiple emails. For scaling, partition per recipient and shard dedupe state; for extremely high fanout, offload idempotency checks to the client where possible (e.g., include message-id and client dedupe) to reduce server state.

Common pitfalls

Pitfall: Treating payload-equality as a correct dedupe key. Payloads may be semantically different or reordered; dedupe must use an authoritative ID or sequence, not just content hash.

Pitfall: Proposing “exactly-once” as an off-the-shelf property without explaining costs. Exactly-once requires transactional sinks or coordinated checkpoints; the practical alternative is idempotent processing plus dedupe.

Pitfall: Not bounding dedupe state. Failing to set TTLs or compaction leads to unbounded memory growth; always quantify expected keys and choose LRU/Bloom or persistent sharding with GC.

Connections

Interviewers may pivot to stream processing (e.g., Flink state backends, checkpointing), event sourcing and log compaction strategies (Kafka), or database concurrency controls (unique constraints, serializable isolation) to probe deeper consistency tradeoffs.

Further reading

• Designing Data-Intensive Applications — Martin Kleppmann — excellent chapters on messaging, deduplication, and consistency tradeoffs.

• Exactly-once delivery semantics in Kafka Streams — Confluent blog — practical explanation of transactional producers and sink semantics.

Practice questions

Focus area — Added for Google-scale search/autocomplete: your indexing, tokenization, freshness, ranking, and typo-tolerance ratings are new or shaky.

What's being tested

Interviewers are probing the candidate’s ability to design a low-latency, high-throughput search indexing and autocomplete service at scale: data structures for prefix/substring lookup, ingestion/update propagation, sharding/replication, caching, and operational tradeoffs (consistency, latency, cost). They want concrete capacity calculations, clear separation between read-path and write-path, and reasoning about failure modes and latency budgets relevant to a production backend engineer.

Core knowledge

• Prefix vs full-text: prefix search (autocomplete) favors tries / radix trees / FSTs for O(length) lookup; inverted index supports full-text and substring queries with posting lists and term normalization.

• Finite State Transducers (FSTs): compact, sorted-string keyed structure that maps prefixes to posting lists or suggestion IDs; memory-efficient for large vocabularies via shared suffixes and node compression.

• Compressed trie / Patricia trie: reduces node count by coalescing single-child chains; useful when many long keys share long common paths to save RAM and cache lines.

• Index size estimate: approximate nodes ≈ sum(lengths of unique strings). If V=100M strings, average length L=8, nodes≈800M; with node storage S≈16–40 bytes, RAM ~12–32 GB per 100M keys (use compression & disk-backed stores beyond that).

• Serving storage choices: in-memory Redis/custom FST for ultra-low-latency hot prefixes; SSD-backed LevelDB/RocksDB/Bigtable for large cold indices. Hybrid caches reduce cost.

• Sharding & routing: shard by hashed prefix range, by first N characters, or by high-frequency prefixes; use consistent hashing + routing layer (small proxy or gRPC-based) to map queries to shards.

• Replication & consistency: replicate shards for availability; choose eventual consistency for suggestions if fresh results are not strictly required, or synchronous replication for strong consistency at higher latency/cost.

• Update propagation: batch rebuilds (cheap, simpler), near-real-time streaming updates (using a change-log + log compaction), or hybrid: immediate hot-prefix update + periodic reindex. Tradeoff: freshness vs serve complexity.

• Latency & capacity math: dimension by QPS and average processing time: required servers ≈ QPS * latency_per_request / acceptable_cpu_latency; aim for interactive p50 < 20ms and p99 < 100ms end-to-end.

• Typo tolerance: implement edit-distance-aware suggestions using BK-trees, k-gram indexes, or precomputed fuzzy variants; runtime cost grows quickly with edit radius — prefer shallow correction or client-side heuristics for high QPS.

• Ranking & personalization (service level): separate the candidate generation (fast, structural) from re-ranking (slower, feature-rich). Keep re-rank cheap or optional for first-page suggestions to meet latency budgets.

• Caching strategies: multi-layer cache: CDN/browser → edge autocomplete cache → shard-local in-memory cache (LRU) → backing store. Use bloom filters to reject misses and reduce disk IOPS.

• Observability & SLAs: instrument QPS, p50/p99 latency, index lag (time from source update to visible), error rates, cache hit ratio, and per-prefix hotness; set SLOs (e.g., 99.9% availability, p99 < 100ms).

Worked example — "Design an autocomplete service supporting 10k QPS and real-time updates"

First 30s: clarify constraints — target latency (p50/p99), suggestion depth (top-5), dataset size (unique queries and total vocabulary), update rate (writes/s), and freshness SLA. Skeleton: (1) choose candidate-generation DS (compressed FST or radix trie) stored in-memory for hot prefixes and SSD-backed for full index; (2) sharding scheme by prefix ranges to distribute QPS; (3) update pipeline: source change-log → streaming processor → per-shard incremental update + periodic full compaction; (4) caching/proxy layer to absorb peaks and return cold results quickly. Key tradeoff: real-time updates vs memory/CPU — maintain a small in-memory delta buffer for new entries (fast) and merge into main FST asynchronously to avoid full rebuilds. If I had more time, I’d sketch the RPC protocol (gRPC + protobuf), backpressure behavior for bursts, and a migration plan for rolling index compactions with zero downtime.

A second angle — "Add typo-tolerance and personalization while keeping p99 < 150ms"

Same core separation (candidate gen vs re-rank) but constraints shift: fuzzy matching increases candidate explosion. Practical choices: restrict fuzzy corrections to top-k frequent prefixes using a bloom-filter-guarded fuzzy index or precompute common 1-edit variants for hot keys to keep lookup O(1) for those. Personalization should happen in the re-rank stage with a light-weight feature set cached per user to avoid remote calls; heavy ML rerankers run asynchronously for offline metrics. Emphasize budgets: cap candidate set size and re-ranker time, and fall back to structural, non-personalized suggestions when profile data is missing or late.

Common pitfalls

Pitfall: Designing a single monolithic in-memory index and assuming it scales linearly — this ignores memory limits, GC pauses, and shard hotness. Prefer sharding, compressed structures, and hybrid memory/disk approaches.

Pitfall: Trying to support arbitrary fuzzy edits at query time for all prefixes — the candidate explosion kills latency and CPU. Instead, precompute common variants for hot prefixes and use bloom filters or k-gram indexes for cold ones.

Pitfall: Overfocusing on perfect freshness — synchronous updates for every write will drastically raise cost and latency; interviewers prefer articulated tradeoffs (delta buffers, TTLs, or eventual consistency) and a rollback/backpressure plan.

Connections

Interviewers may pivot to adjacent topics: ranking pipelines (how candidates are scored and reranked), streaming ingestion (change-data-capture and exactly-once semantics), or capacity & cost optimization (autoscaling policies and multi-tier storage). Be prepared to tie your design decisions to these areas without diving into ML model internals.

Further reading

• The Anatomy of a Large-Scale Hypertextual Web Search Engine (Brin & Page) — classic framing of indexing and ranking tradeoffs.

• Bigtable: A Distributed Storage System for Structured Data (Chang et al.) — useful for thinking about backend storage choices for large indexes.

• Designing Data-Intensive Applications (Kleppmann) — chapters on replication, partitioning, and log-based change propagation are directly applicable.

Practice questions

Focus area — Added because all cache strategy, TTL, stampede, eviction, and invalidation concepts were rated shaky.

What's being tested

Interviewers are checking your ability to design and reason about a low-latency, large-scale caching layer and its cache invalidation semantics: how you trade freshness, availability, and cost at Google scale. They want concrete choices (cache topology, invalidation protocol, eviction and sharding), quantitative tradeoffs (hit-rate vs origin-load), and engineering tactics for correctness under concurrency and failures. Demonstrate clear assumptions, failure-mode handling, and measurable SLAs (latency, stale-window, origin QPS).

Core knowledge

• Caching patterns: know cache-aside, read-through, write-through, and write-back semantics, their origin-write amplification, and when each simplifies consistency or reduces origin load.

• TTL vs explicit invalidation: TTL provides bounded staleness; explicit invalidation (versioning/publish) gives precise freshness but requires coordination and network fanout.

• Multi-tier caches: differentiate edge/CDN (CDN), regional caches, and in-process caches (memcache, Redis, local LRU); understand s-t tradeoffs between propagation latency and hit-rate.

• Cache hit-rate math: hit-rate H affects effective latency $L_{eff} = H·L_{cache} + (1−H)·L_{origin}$ and origin QPS = $(1−H)·request\_rate$. Estimate required cache size from access distribution (Zipf/90-10).

• Eviction policies: LRU/LFU trade memory and recency; approximate LFU (TinyLFU) works at high throughput; admission policies (probabilistic) prevent pollution from large one-off scans.

• Sharding & consistent hashing: use consistent hashing to minimize re-shuffles when nodes join/leave; replicate hot keys for read-scaling but handle write fan-out/atomicity.

• Cache stampede: mitigate with request coalescing/singleflight, mutex-per-key, or early recomputation; consider jittered TTLs to avoid synchronized expiry.

• Invalidation protocols: push (fan-out via Pub/Sub) vs pull (clients check version); combine with versioned keys (key:v) so invalidation is an atomic key-swap.

• Atomicity & races: enforce write ordering using monotonic version numbers, compare-and-swap, or single-writer sharding; avoid lost-invalidates by sequencing invalidation after origin commit.

• Failure modes: network partitions can split-brain caches; prefer tolerant designs (serve stale with TTL+revalidate) over dropping to origin if availability SLA dominates.

• Stale-while-revalidate and soft TTL: serve slightly stale data while background refresh reduces tail latency and origin spikes, with quantified stale windows.

• Instrumentation & metrics: measure cache_hit_rate, origin_qps, stale_serves, p99_latency, and invalidation lag (time between origin commit and cache freshness).

Tip: wrap metric targets into SLOs (e.g., <50ms p95, stale-serve <1%) to drive tradeoffs.

Worked example

Design a caching strategy for a user-profile service where updates are rare but reads are high. First 30s: clarify SLAs — acceptable staleness (seconds vs minutes), read QPS, update QPS, and whether strong consistency is required for reads immediately after a write. Skeleton of answer: (1) choose topology: edge CDN for avatars + regional Redis for profile JSON; (2) population: cache-aside for reads, with write path performing origin commit then invalidation; (3) invalidation: publish a user-specific invalidation via Pub/Sub to regional caches and bump a versioned key (user:123:v42); (4) mitigate stampede: use singleflight on miss and jittered TTLs. Tradeoff to flag: eager push invalidation reduces staleness but costs O(number_of_caches) messages; versus TTLs cause bounded staleness but simpler. Close by saying you’d add metrics (invalidation lag histogram), run load tests to size Redis clusters, and, if more time, discuss replication strategy and failure-injection tests.

A second angle

Now assume the same service must support multi-region active-active writes with global user IDs and low write latency. Here the invalidation problem becomes global coherence: choose a single-writer-per-user routing to keep invalidation local, or use optimistic concurrency with monotonic timestamps and allow temporary divergent reads resolved by last-write-wins. Use versioned keys with global version vector / Lamport timestamps for monotonicity. Instead of pushing invalidations to every region synchronously, send an origin-of-truth write and then publish lightweight version-updates; regions compare versions and lazily pull authoritative data on mismatch. Emphasize the tradeoff: stronger cross-region freshness increases write latency and coupling; eventual consistency simplifies latency at the cost of temporary stale reads.

Common pitfalls

Pitfall: Designing for perfect freshness by synchronously invalidating every cache before acknowledging a write. This yields high write latency and brittle availability; interviewers prefer bounded staleness or async invalidation with well-measured windows.

Pitfall: Ignoring cache stampede and scaling only by adding memory. Large TTLs plus no coalescing causes sudden origin thundering when popular keys expire; propose singleflight, mutex per-key, or background refresh to prevent spikes.

Pitfall: Using naive key deletion across many shards without idempotency or ordering. If invalidation messages are lost or reordered, clients may read stale data; prefer versioned keys or sequence numbers and design idempotent invalidation handlers.

Connections

Interviewers may pivot to distributed consensus (e.g., when you need strong global invalidation ordering), consistency models (linearizability vs eventual consistency), or capacity planning (approximating cache size from access distribution and hit-rate targets). Be ready to discuss tradeoffs that touch on replication, partitioning, and operational runbooks.

Further reading

• [Designing Data-Intensive Applications — Martin Kleppmann] — excellent chapters on caching, replication, and consistency models.

• [Redis documentation: Caching patterns] — practical patterns (cache-aside, write-through) and anti-patterns for in-memory stores.

• [RFC 7234 — HTTP Caching] — formalizes freshness, validators, and stale-while-revalidate semantics useful for CDN-edge caching.

Practice questions

Software Engineering Fundamentals

Focus area — You selected observability and rated logs, metrics, label cardinality, sampling, SLIs, and SLOs shaky.

What's being tested

Interviewers expect you to demonstrate practical reliability engineering judgment: define measurable service health, design observability that surfaces real faults, and run diagnostics that map telemetry to root causes. They want concrete tradeoffs (cost vs. coverage, signal-to-noise), familiarity with distributed consistency and replication failure modes, and an incident-driven troubleshooting approach. For a Software Engineer role, focus on designing and instrumenting the service, choosing SLI/SLO targets, reasoning about alert thresholds, and proposing safe remediation paths—not organizational or SRE team staffing.

Core knowledge

• SLI / SLO / SLA — an SLI is a measurable signal (e.g., p99 latency); an SLO is a target for that SLI over a window; an SLA is a contractual penalty tied to SLO violations and error budget consumption.

• Error budget math — error_budget = 1 − SLO (e.g., 99.9% availability → error_budget = 0.001); use rolling windows and partition by customer tier when enforcing.

• Latency percentiles — prefer p50/p95/p99 for user-impact; calculate percentiles on aggregated distributions (HDR histograms) to avoid misinterpretation from averages.

• Metrics vs logs vs traces — metrics are numeric time-series for alerting, logs for event detail and forensic search, traces for request causality; instrument with correlation IDs for cross-signal joins.

• Instrumentation primitives — use client-side and server-side timers, structured JSON logs, and distributed context propagation (trace-id, span-id); expose metrics via Prometheus-compatible endpoints or push gateways.

• Alerting strategy — prefer alerting on symptoms with automated noise-reduction (rate-limited, aggregation windows, dynamic baselines); avoid alerting on single-instance internal counters unless they imply customer impact.

• Health checks & readiness — implement separate liveness and readiness probes; readiness gates for in-flight migrations and leader elections prevent traffic to partially initialized nodes.

• Replication & consistency — know leader-based replication (e.g., Raft, etcd) and leaderless quorum models (e.g., Dynamo-style with vector clocks), and root causes like split-brain, stale reads, and write reordering.

• Diagnostics signals — correlate replication_lag, commit-index, election-count, GC pauses, CPU steal, syscall errors, and network RTT; sudden divergence patterns often point to networking or leader mis-election.

• Automated remediation patterns — safe steps: circuit breakers, traffic-shaping, progressive rollbacks (canaries), and self-healing (auto-restart) with kill-switches and manual override paths documented in runbooks.

• Cost/coverage tradeoff — high-cardinality traces and logs are expensive; use sampling, adaptive tracing, and retain raw logs for a short time while long-term aggregates and derived metrics persist.

• Post-incident hygiene — capture timeline, hypotheses tried, root cause, corrective action, and follow-ups; quantify operational impact in SLI terms and update SLOs or instrumentation gaps accordingly.

Worked example — Explain SLI/SLO/SLA and design monitoring

Frame: start by clarifying user-visible actions and tenants — "Which API calls define customer experience? Are there tiers with different availability promises?" Declare assumptions about request routing, data consistency, and acceptable windows.

Pillars: (1) choose 3–5 core SLIs (successful request rate, p99 latency, error-rate by endpoint), (2) set SLOs per user-impact and business tolerance (e.g., 99.9% p99 latency over 30 days), (3) design alerting and dashboards that map SLI breaches to runbooks and escalation, (4) define automated short-term remediation (circuit breaker) and rollback policy.

Tradeoff: explicitly discuss balancing alert sensitivity vs. noisy paging — choose a multi-tier alert scheme (actionable page for customer-impacting SLO breach; internal tickets for degradations).

Close: state how you'd validate—run chaos tests, synthetic traffic, and measure alert precision; "If I had more time, I'd add per-customer SLI aggregation and adaptive alerts using short-term anomaly detection."

A second angle — Diagnose distributed database inconsistency

This framing shifts emphasis to low-level replication telemetry: first ask which consistency model the system promises (strict serializability vs. eventual). Organize diagnostics around (1) leader health and election logs, (2) replication offsets / watermark comparisons across replicas, (3) client-side write-path tracing and idempotency keys, and (4) network partitions and clock skew metrics.

A strong answer argues for safe mitigation: stop accepting writes to suspect partition, promote stable replica, or perform controlled reconciliation using deterministic merge or compensation operations. Highlight tradeoffs between consistency repair cost and customer-visible rollback: sometimes serving stale reads is preferable to data loss; other times write-rollback with reconciliation is better.

Common pitfalls

Pitfall: Confusing symptom and root cause.

Many candidates jump to "scale more" when p99 spikes, whereas root causes are often latency amplification from a downstream dependency or GC pauses; always correlate traces, GC, and network metrics before capacity actions.

Pitfall: Designing alerts on internal counters.

Alerting on a single queue-length or thread-count without mapping to user-facing SLI causes pager fatigue; instead alert on user-visible degradation and attach internal counters to the dashboard for diagnostics.

Pitfall: Overengineering remediation.

Proposing fully autonomous rollback with no human-in-loop is tempting, but neglects blast-radius controls; prefer staged automation (canary, circuit-breaker, manual escalation) and explicit abort criteria.

Connections

Interviewers may pivot to capacity planning (load forecasting, autoscaling policies), security & multi-tenancy (isolation of telemetry and remediation), or deeper distributed-systems theory (consensus algorithms, clocks, and anti-entropy). Be prepared to connect monitoring decisions to deploy processes and CI/CD safeguards.

Further reading

• Site Reliability Engineering (Google SRE book) — practical guidance on SLI/SLO, incident response, and postmortems.

• Designing Data-Intensive Applications by Martin Kleppmann — solid coverage of replication, consistency models, and repair strategies.

Practice questions

Focus area — You selected concurrency, transactional integrity, distributed job scheduling, fairness, checkpoints, and locking-related concepts as shaky.

What's being tested

These problems test building and reasoning about an async primitive (like CompletableFuture) and scheduling: safe callback registration, correct completion state machine, and efficient timer/task multiplexing onto a thread-pool. Interviewers probe race-free state transitions, cancellation, ordering guarantees, and scalable timer/scheduler data structures.

Patterns & templates

• State machine with explicit states (e.g., PENDING → COMPLETING → COMPLETED/FAILED/CANCELLED) and a single CAS transition per completion to avoid races.

• Callback list appended atomically with compareAndSet and drained by the thread that wins completion, avoiding locking on hot path.

• Use volatile for result/state visibility and minimal locking; prefer lock-free for low-latency futures, fallback to short critical sections when necessary.

• Implement timers with a min-heap priority queue for correctness, or a timer wheel for large-scale (~10^6 timers) amortized O(1) ticks.

• Use ForkJoinPool / work-stealing for parallel array processing; prefer divide-and-conquer recursively to maximize locality and CPU utilization.

• Cancellation: mark state then attempt to remove scheduled tasks; for heap-based timers, use lazy deletion flags to avoid O(n) removals.

• Batch wakeups: coalesce scheduled callbacks and run them on a worker thread (execute()), avoid running user callbacks under internal locks to prevent deadlocks.

Common pitfalls

Pitfall: Failing to make state transitions atomic leads to double-completion or lost callbacks when two threads try to complete concurrently.

Pitfall: Running user callbacks while holding internal locks causes deadlocks or long GC pauses; always invoke callbacks outside locks.

Pitfall: Assuming notify() without rechecking condition — handle spurious wakeups and always loop on the predicate when using wait()/notify().

Practice these

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

Practice questions

Online Assessment — 12 min

Coding & Algorithms

Focus area — Coding self-rating is 1/5, with arrays, two-pointers, parsing, and key-value basics explicitly selected and no solved coding signals yet.

What's being tested

These problems test frequency-counting and anagram/signature reasoning for strings, efficient sliding-window checks over substrings, and membership lookups using hash maps. Interviewers probe algorithmic choices (O(n) vs O(n·k)), correct edge-case handling, and clean iteration/parsing for large inputs.

Patterns & templates

• Sliding window on contiguous substrings — O(n) two-pointer expand/contract; maintain counts and window invariants to avoid re-scanning.

• Frequency signature via fixed-size arrays or Counter — store counts as tuples or serialized keys for O(1) comparison on alphabet-limited strings.

• Hash set / map for membership — pre-hash dictionary words or signatures to get average O(1) membership tests during enumeration.

• Bitmask / digit mask for digits 0–9 — represent presence with a 10-bit int, enabling O(1) union/intersection checks across numbers.

• Two-pointer on arrays for monotonic constraints — move left/right and maintain aggregate (sum/count) for O(n) feasibility checks.

• Binary search over answer space — convert "max size" questions to monotone predicate, run O(n) check per mid for total O(n log n).

• Single-pass string parsing for snake_case→camelCase — build result in-place, handle separators and capitalization in O(n) time and O(1) extra space.

Common pitfalls

Pitfall: Comparing full count arrays per window naïvely makes algorithms O(n·k); instead update counts incrementally on pointer moves.

Pitfall: Forgetting to canonicalize signatures (order or normalized tuple) causes false negatives when checking anagram membership.

Pitfall: Not validating separators/edge cases (empty string, consecutive underscores) in parsing tasks leads to incorrect outputs or crashes.

Practice these

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

Practice questions