Design a Collaborative Editor (LLD)

The algorithm behind Google Docs, at the level of actual code. This is the hardest LLD problem on the sheet, and interviewers know it — a clear explanation of why naive concurrent editing breaks, plus one correct transform case, already puts you ahead.

The problem, concretely

Two users edit "HELLO" simultaneously.

The cause: Bob's index 5 was computed against a document Alice has already changed. Alice inserted a character before position 5, so by the time Bob's operation arrives, the position it refers to has moved.

Operational transformation

OT fixes this by **transforming an incoming operation against the concurrent operations it did not see.**

record Operation(Type type, int position, String text, int version, String authorId) {
    enum Type { INSERT, DELETE }
}

/** Transform the incoming operation so it can be applied after the
    already-applied one, given both were generated from the same version. */
Operation transform(Operation incoming, Operation applied) {
    if (incoming.type() == INSERT && applied.type() == INSERT) {
        if (applied.position() < incoming.position()
            || (applied.position() == incoming.position()
                && applied.authorId().compareTo(incoming.authorId()) < 0)) {
            return incoming.shift(+applied.text().length());
        }
        return incoming;
    }

    if (incoming.type() == INSERT && applied.type() == DELETE) {
        if (applied.position() < incoming.position()) {
            return incoming.shift(-applied.length());
        }
        return incoming;
    }
    // DELETE/INSERT and DELETE/DELETE follow the same shape,
    // with DELETE/DELETE also needing overlap handling.
    …
}

Applied to the example: Bob's insert("Y", 5) transformed against Alice's insert("X", 0) becomes insert("Y", 6), and both documents converge on "XHELLOY".

Two things carry the correctness argument:

The tie-break. When two inserts target the same position, something must decide the

order — and it must decide the same way on every machine. Comparing author ids is deterministic and available everywhere. Without it, the two clients each put their own character first and diverge permanently.

DELETE/DELETE overlap. Two users deleting overlapping ranges must not delete the

intersection twice. Transforming produces a shorter delete covering only the part not already removed, and possibly an empty operation — so transform must be able to return a no-op.

The server loop

class DocumentSession {
    private final List<Operation> history = new ArrayList<>();
    private String content = "";
    private int version = 0;

    synchronized Operation receive(Operation incoming) {
        // Transform against every operation the client had not seen.
        Operation op = incoming;
        for (int i = incoming.version(); i < history.size(); i++) {
            op = transform(op, history.get(i));
        }
        content = op.applyTo(content);
        op = op.withVersion(++version);
        history.add(op);
        broadcastToOthers(op);
        return op;                // acknowledgement to the sender
    }
}

A single synchronised session per document gives a total order of operations, which is why the server-based design is so much simpler than the peer-to-peer one. Each client carries the version it last saw; the server transforms against everything since.

Clients apply their own edits immediately (optimistic local application) so typing is never blocked by the network, then reconcile when the acknowledgement returns. The client must therefore keep its own pending queue and transform incoming remote operations against it — the same function, run on the other side.

CRDTs: the other answer

CRDTs remove the need to transform by **giving every character a unique, totally ordered identifier**. Operations then commute — applying them in any order converges.

Instead of  insert("X", position 0)
you have    insert("X", id 4.1, between START and id 7.2)

Positions are fractional or path-based identifiers that can always be
subdivided, so a new character can always be created between any two.

record CharId(List<Integer> path, String siteId, long counter) implements Comparable<CharId> { … }

record Char(String value, CharId id, boolean deleted) { }

Deletion is a tombstone — mark, do not remove — because a concurrent insert may reference the deleted character as its neighbour. Tombstones accumulate, and garbage collecting them safely (only once every replica has seen the delete) is the classic CRDT weakness, alongside per-character metadata overhead.

Trade-off to state: OT needs a central server and subtle transform functions but keeps

the document compact. CRDTs need no coordinator and are far easier to reason about, at the cost of metadata and tombstones. Modern libraries (Yjs, Automerge) have reduced that overhead substantially, which is why CRDTs have become the default choice for new offline-first products.

Cursors and selections

Cursor positions must be transformed exactly like operations, or every collaborator's caret drifts as text is inserted above it. The difference is durability: operations are logged and must never be lost, whereas cursor updates are ephemeral and can be dropped or throttled freely.

Undo

Undo in a collaborative editor is not "revert the last operation" — the last operation may be someone else's. It must be per user: find that user's last operation, invert it, and transform the inverse against everything that has happened since. This is the Command pattern doing real work, and it is a favourite follow-up because it catches designs that only track a global history.

Patterns worth naming

• Command — operations with apply and invert; the backbone of undo and history.
• Observer — broadcasting operations to connected clients.
• Memento — periodic snapshots so the log need not be replayed from zero.
• Strategy — swapping OT for a CRDT behind one interface.

Edge cases to handle

• Two inserts at the same position — the deterministic tie-break.
• Overlapping deletes.
• An operation arriving for a version older than the last snapshot.
• A client offline for a long period, whose operations transform against thousands of others.
• Rich-text attributes (bold, links) concurrent with text edits — attribute operations need

their own transform rules.

Track this problem on the System Design sheet.