9. Google Docs (Collaborative Editing) Advanced

A. Realistic Interview Prompt

This problem's difficulty is almost entirely conceptual, not volumetric. A single document is small (kilobytes to low megabytes of text) and has, realistically, a handful to a few dozen concurrent editors — nothing like the billion-user scale of earlier problems. The hard part is that two people can type in the same place at the same time, and every replica of the document — every open browser tab — must converge on the exact same final text, in the same order, without a human ever noticing a conflict dialog. That single requirement is what pulls in operational transformation or CRDTs, the central technical decision of this entire design.

B. Difficulty

Advanced — not because any individual component is exotic, but because the core conflict-resolution algorithm (N) is genuinely subtle to get right, and a design that "sounds reasonable" (last-write-wins, or naive full-document overwrites) silently loses user keystrokes rather than failing loudly, which is a uniquely dangerous failure mode for a writing tool.

C. What This Problem Tests

• Recognizing that concurrent edits to shared, ordered, mutable content (text) is a fundamentally different problem than concurrent writes to a single value (a counter, a seat status) — the conflict isn't "who wins," it's "how do two edits at different positions compose into one coherent document"
• Real judgment on operational transformation (OT) versus CRDTs — not just naming both, but reasoning about why Google Docs itself picked a central-server OT model over a peer-to-peer CRDT one, and when the opposite choice would be correct
• Designing for optimistic local echo — the local editor must feel instantaneous even though the "real," reconciled state is decided somewhere else a network round-trip away
• Comfort with presence/ephemeral state (cursors, "who's online") as a deliberately different data-consistency class than the document content itself
• Handling offline editing as a bounded special case of the same conflict-resolution machinery already needed for the online case, not a separate system

D. Requirements

Functional

1. Multiple users can open and edit the same document concurrently
2. Edits made by one user propagate to all other active viewers in near real time
3. Users can see other active editors' presence and live cursor/selection position
4. A user who edits while offline (or disconnected) has their edits merged in correctly once they reconnect

Non-Functional

• Convergence — every client must end up with the byte-identical document content, regardless of the order in which concurrent edits happened to arrive over the network; this is the one non-negotiable correctness property of the whole system, playing the same role overselling-prevention played in Ticketmaster
• Low-latency propagation — other users should see an edit within roughly 100-200ms under normal conditions, so collaboration feels live rather than "eventually synced"
• Instant local responsiveness — a user's own keystrokes must render immediately, never blocked on a network round-trip, regardless of how the eventual reconciliation with others' edits is resolved
• No lost updates — a legitimate edit from any user, online or reconnecting from offline, must never silently vanish because it collided with someone else's edit

Out of scope: rich formatting/embedded objects (treated as an extension of the same text-operation model), commenting/suggestion mode, access control and sharing permissions, full version-history UI.

E. Clarifying Questions

F. Assumptions

• Confirmed: multiple concurrent editors on one document, live propagation, presence/cursors, offline-edit reconciliation.
• Assumption: plain text content (E's clarifying question 1) — the conceptually hardest and most commonly discussed version of this problem; rich formatting is noted as a structural extension, not solved from scratch.
• Assumption: a realistic concurrency level of tens of simultaneous editors per document (E's clarifying question 2) — this is a small-N, correctness-heavy problem, not a large-N throughput problem, and that shapes every subsequent decision.
• Assumption: offline editing is in scope (E's clarifying question 3) — the more interesting and complete version of the problem, and what makes Q a first-class deep dive.
• Assumption: full version-history UI is out of scope (E's clarifying question 5), though the underlying operation log (R) would trivially support it.

G. Capacity Estimation

H. Core Entities

I. API Design

WS   /v1/documents/{id}/edit             -> bidirectional stream:
                                             client sends: { op, base_revision }              (M, N)
                                             server sends: { transformed_op, new_revision }    (broadcast to all)
WS   /v1/documents/{id}/presence         -> bidirectional stream: { cursor_pos }               (P, not persisted)
GET  /v1/documents/{id}                  -> { content, revision }                              (initial load, from R)
GET  /v1/documents/{id}/history          -> [{ revision, snapshot_ref, created_at }]            (extension, out of scope per F)

Why WebSocket streams, not request/response REST calls, for the edit path: this is fundamentally a bidirectional, server-push problem — the server must proactively deliver other users' operations to a client the instant they're committed, not wait for that client to poll for them. A persistent connection per active editor is exactly the connection-management problem already solved in the Chat System design, reused directly rather than reinvented (M).

Why presence is a separate stream from edit operations: cursor positions change far more frequently than actual content edits (every mouse movement or arrow key), and are entirely disposable if a message is dropped — mixing them into the same stream as durable, must-not-be-lost content operations would force the wrong reliability guarantee onto both.

J. Basic / Naive High-Level Design (V1)

The simplest thing that satisfies the functional requirement in isolation: whenever a user edits, the client sends the entire updated document content to a server, which overwrites the stored document and pushes the full new content to every other connected client.

V1 — whole-document last-write-wins. Looks fine with one editor; silently destroys work with two.

Why this breaks immediately, not eventually: if User A and User B are both typing at the same moment, each sends their own full copy of the document reflecting only their own edit. Whichever write reaches the server second simply overwrites the first in its entirety — User A's keystrokes vanish completely, with no error, no conflict warning, and no way to recover them. Unlike Ticketmaster's overselling race, which produces a visible, loud failure (two people show up for one seat), this failure mode is silent — the product looks like it's working right up until a user notices their paragraph is gone.

K. Data Model & Store Choice

Two distinct stores for two distinct access patterns: an append-only operation log (every individual insert/delete, ordered by revision number for a given doc_id) is the actual source of truth for how the document reached its current state, while a periodic snapshot store (R) holds materialized full-document content at checkpoints so a newly-joining client (or server restart) doesn't have to replay potentially thousands of tiny operations from the beginning of the document's history.

Why the operation log is the source of truth, not the "current content" field alone: the log is exactly what operational transformation (N) needs to reconcile a client's edit against everything that's happened since that client last synced — a bare "current content" string has already discarded the ordering and positional information required to transform a late-arriving concurrent operation correctly.

Sharding/routing by doc_id: all operations for one document must be sequenced by a single authority to have a well-defined order at all (O) — this is the same principle as Ticketmaster's per-event sharding and Chat System's per-conversation routing, here applied to keep one document's entire operation stream flowing through one coordinating point.

L. End-to-End Flow — Two Users Editing Concurrently

M. Deep Dive 1 — Real-Time Sync & Transport

Requirement this addresses: the near-real-time propagation NFR (D) and the instant-local-responsiveness NFR (D) together — these pull in opposite directions and both must be satisfied at once.

Optimistic local echo: a user's own keystrokes are applied to their local in-memory document copy immediately, before any server round-trip completes — the edit is sent to the server asynchronously in the background. This is the only way to satisfy "instant" typing feel in a networked system; waiting for server acknowledgment before rendering a keystroke would make every character feel laggy.

Why a persistent WebSocket connection per active editor, not polling: polling either wastes requests when nothing changed or adds up to a full polling-interval's worth of latency to every edit's propagation — directly reusing the same connection-management reasoning already established in the Chat System design (long-lived, stateful connections held by dedicated connection servers, tracked in a shared session store for routing).

One coordinating server "owns" a given document (K, O): rather than any connected client's edit being validated against a globally-distributed source of truth, all operations for one doc_id flow through a single server instance holding that document's current state in memory — turning conflict resolution into a fast, local, single-machine operation instead of a distributed consensus problem.

N. Deep Dive 2 — Operational Transformation vs. CRDTs

Requirement this addresses: the convergence NFR (D) — the single central technical decision of this entire problem, and the one place a candidate's judgment is most directly tested.

The actual problem being solved: two users each start from the same document state (revision 5) and each submit an operation — say, User A inserts "X" at position 10, and User B (unaware of A's edit) inserts "Y" at position 10 as well. Both operations are individually valid against revision 5, but applying them naively in whatever order they happen to arrive produces two different final documents on two different clients, unless something actively reconciles them.

Why central-server OT is the right default answer here, not peer-to-peer OT or a CRDT: once M already establishes that one server owns a given document's authoritative state, that same server is perfectly positioned to be the single point of transformation — every incoming operation only ever needs to be transformed against operations the server itself already committed, in a known order, which is a far simpler problem than transforming against an unordered set of concurrent peer operations. This is the actual architecture real Google Docs uses. A CRDT becomes the more compelling choice specifically when the product requirement is genuine serverless peer-to-peer sync or truly long-lived offline-first editing with no reliable central authority — worth naming as the right answer to a different, adjacent set of requirements (Q revisits this for the bounded offline case actually required here).

O. Deep Dive 3 — Ordering & Causality

Requirement this addresses: convergence (D) depends on every client applying operations in a way that respects what each operation was actually based on — the same ordering problem named explicitly in Chat System's message-ordering deep dive, here applied to edit operations instead of chat messages.

The fix — a per-document monotonic revision number, assigned at the coordinating server (M), not by the client: exactly the same principle as Chat System's per-conversation seq_num assigned at the point of persistence — each operation carries the revision it was based on, and the server assigns the next revision only once the operation is transformed (N) and committed. Clients never need wall-clock timestamps to agree on order; the server's assigned revision sequence is the single authoritative ordering, immune to clock drift between clients.

Why this only works because one server owns the document (K): a monotonic sequence is trivial to assign correctly from a single authority, and becomes a distributed-consensus problem the moment more than one server could commit revisions for the same document concurrently — another way K and M reinforce each other rather than being independent decisions.

P. Deep Dive 4 — Presence & Live Cursors

Requirement this addresses: the presence/cursor-sharing functional requirement (D) — deliberately built as a separate, lower-guarantee data path from document content itself (I).

Why presence is ephemeral, in-memory, and never persisted: a cursor position five minutes ago is worthless information — there's no analog to the durable operation log (K) here, because there's nothing worth recovering after the fact. Presence state lives only in the coordinating server's memory (or a short-TTL cache) for as long as a user is actively connected, and simply disappears on disconnect with no cleanup job required beyond the TTL itself.

Why dropped presence updates are an acceptable trade-off but dropped edit operations are not: if a cursor-position packet is lost on the wire, the next one (arriving milliseconds later, since cursor updates are frequent) simply supersedes it with no visible impact — this is the same class of loss-tolerance as Ticketmaster's approximate seat-map display (R in that problem), applied here to presence instead of inventory counts. An edit operation, by contrast, must never be silently dropped, which is exactly why it travels over the same reliable, ordered channel that carries revision numbers (O), not the disposable presence channel.

Q. Deep Dive 5 — Offline Editing & Reconciliation

Requirement this addresses: the offline-edit functional requirement (D) — the bounded special case where the gap between "edit made" and "edit reaches the coordinating server" can be minutes or hours instead of milliseconds.

Why this reuses N's machinery rather than needing a separate merge algorithm: a client that goes offline simply keeps applying operations to its local copy and queuing them, each still recording the revision it was based on. On reconnect, the client replays its queued operations to the coordinating server exactly as if they'd each arrived slightly late — the server transforms each one against everything committed in the meantime (N), the same way it already transforms operations that arrive milliseconds apart from two simultaneously-typing users. Offline editing is not a new problem; it's the existing conflict-resolution problem with a longer, more variable delay.

Where this stresses the OT-vs-CRDT decision (N) the hardest: a very long offline period means a very large batch of concurrent history to transform against on reconnect, which is the scenario where a CRDT's "just merge, no central coordination required" property is most attractive — worth explicitly naming as the boundary condition where the trade-off in N could tip toward a CRDT if offline periods were expected to be routinely long (days, not minutes) rather than the occasional dropped-connection case assumed here (F).

R. Deep Dive 6 — Persistence & Snapshotting

Requirement this addresses: practical durability and fast document load times — not explicitly stated in D, but required to make K's operation log usable in practice rather than just in theory.

Why periodic full-document snapshots, not replaying the entire operation log on every load: a long-lived, heavily-edited document could accumulate many thousands of individual insert/delete operations over its lifetime — replaying all of them to reconstruct current content on every load would make opening an old, well-edited document progressively slower over its lifetime, which is exactly backwards. A snapshot taken periodically (e.g. every N operations, or on a time interval) captures full materialized content at that revision; loading a document means fetching the latest snapshot plus only the handful of operations committed since it.

This is the same metadata/blob-store pattern used elsewhere in this document (News Feed media, Chat System attachments, Web Crawler pages, Video Streaming files) — a compact, frequently-accessed pointer (the current revision number) alongside a larger, less-frequently-rewritten blob (the snapshot content), rather than reconstructing expensive state from scratch on every access.

S. Deep Dive 7 — Scaling to Many Documents

Requirement this addresses: G's observation that the real scale challenge is the sheer number of documents, not concurrency within any single one.

Why this is an assignment/routing problem, not a per-document throughput problem: since G established that even a "hot" document only sees low hundreds of operations per second, a single coordinating server instance can easily own many simultaneously-active documents at once — the actual scaling question is how a client's initial connection request for a given doc_id gets routed to whichever server instance currently owns (or should own) that document.

Consistent hashing of doc_id across a fleet of coordinating servers — the same technique used for shard/owner assignment in Rate Limiter and Chat System's connection routing — lets the fleet scale horizontally by adding servers, with each new server picking up ownership of a proportional slice of documents, while any single document's operations always land on the same server for as long as it stays active.

An idle document has no server holding it in memory at all: a coordinating server only needs to load a document's state (from the latest snapshot plus recent operations, R) when the first client connects to it, and can evict it from memory after a period with no active editors — keeping the vast majority of the hundreds of millions of mostly-untouched documents (G) from consuming any active-server resources at all.

T. Full Solution at Scale — Final Architecture

Everything above is the composition of M through S — no new component introduced here.

U. Design Evolution

• V1 — whole-document last-write-wins overwrite (J): silently destroys concurrent edits, with no warning.
• V2 — operation-based edits with a central per-document coordinating server: turns "who wins" into a well-defined transformation problem instead of a destructive overwrite (M).
• V3 — operational transformation on the coordinating server: the core correctness fix — concurrent operations are reconciled, not one discarded (N).
• V4 — server-assigned monotonic revision numbers: gives every client the same authoritative ordering, immune to clock drift (O).
• V5 — separate ephemeral presence channel: keeps high-frequency, disposable cursor data off the durable, must-not-lose content path (P).
• V6 — offline operation queue + replay-on-reconnect: extends the same transformation machinery to arbitrarily delayed edits, no separate merge algorithm needed (Q).
• V7 — periodic snapshots alongside the operation log: keeps document load times flat regardless of edit history length (R).
• V8 — consistent-hash-routed fleet of coordinating servers: scales to hundreds of millions of documents by only holding active ones in memory (S).

What stays stable throughout: the operation-based edit model from M — every later refinement changes how operations are transformed, ordered, or routed, never the basic shape of "an edit is a small, positioned operation, not a full-document overwrite."

V. Consistency Model

This design targets what the distributed-systems literature calls strong eventual consistency: any two replicas that have received the same set of operations converge to the identical document state, regardless of the order those operations happened to arrive in — but there is no requirement that all replicas see every operation at the exact same instant. The coordinating server (M) provides a stronger, additional guarantee on top of that baseline: a single authoritative order (via revision numbers, O) for the online, connected case, which is what OT specifically relies on. The offline case (Q) relaxes the timing further — a client's view can diverge from the server's for an arbitrarily long period — but never relaxes the eventual-convergence guarantee itself. This is a different consistency shape than Ticketmaster's hard strong-consistency requirement: there is no single "seat," no operation that must be rejected to preserve correctness — every legitimate concurrent edit is preserved and reconciled, never discarded.

W. Failure Scenarios

• Two users edit the same position simultaneously: the coordinating server's transformation step (N) reconciles both edits into a well-defined combined result — neither is silently dropped.
• A user's connection drops mid-edit: queued local operations are simply held (Q) and replayed against the current revision once the connection re-establishes.
• The coordinating server for a document crashes: a new server picks up ownership (S) and reconstructs state from the latest snapshot plus any operations already durably appended to the log (R) — no committed edit is lost, though any operation that was in-flight but not yet acknowledged may need to be resent by the client.
• A client reconnects after a very long offline period: the reconciliation step (Q) still functions correctly, just with a larger batch of history to transform against — a performance concern, not a correctness one.
• Presence data is lost or stale: harmless by design (P) — the next presence update supersedes it within moments.

X. Bottlenecks & Scaling Boundary

Y. Design Trade-Offs

Z. Common Bad Designs

• Sending the full document content on every edit and overwriting on the server. Silently destroys concurrent edits with no warning — the single most important mistake to avoid on this problem, and the one that looks correct in a single-user demo.
• Last-write-wins at the operation level without transformation. Still discards one of two legitimate concurrent edits rather than reconciling them — better than whole-document overwrite, but still fundamentally wrong for a collaborative editor.
• Using wall-clock timestamps to order operations across clients. Clock drift between clients (or servers) can misorder near-simultaneous edits — the same mistake called out in Chat System's ordering deep dive.
• Treating presence/cursor data with the same durability guarantees as document content. Wastes engineering effort persisting and reliably delivering data that's worthless moments after it's superseded.
• Blocking local keystroke rendering on a server round-trip. Defeats the entire point of optimistic local echo and makes the editor feel laggy regardless of how correct the underlying conflict resolution is.

AA. Interviewer Follow-Ups

AB. Interviewer Evaluation Rubric

• Weak candidate: proposes sending the whole document on every keystroke and overwriting server-side; no recognition that concurrent edits are a real problem at all.
• Mid-level: recognizes edits need to be operation-based rather than whole-document, and that ordering matters, but can't articulate a concrete mechanism for reconciling two truly concurrent operations.
• Senior: proactively introduces operational transformation (or a CRDT) unprompted as the mechanism for reconciling concurrent operations; designs the optimistic-local-echo flow; separates presence from content correctly.
• Staff+: reasons explicitly about why central-server OT versus peer-to-peer CRDT, tying the choice to concrete product requirements (is there a reliable central authority, how long can offline periods realistically get); designs the snapshot/operation-log split and the document-ownership routing scheme for scaling to many documents without being prompted.

AC. Interview Simulation

AD. Online Solution Comparison

AE. Interview Cheat Sheet