Collaborative Editor

Frequency: Reported

At the core of Notion's product is a collaborative editor: when multiple users edit the same document simultaneously, the server must correctly integrate each user's changes, even when they arrive out of order.

Build a simplified version of this system: a CollaborativeEditor class that applies insert and delete operations on a shared string, handling concurrent edits from clients that may be working against older versions of the document.

Apply these operations while maintaining versioned history where clients may submit edits based on older states of the document. For this problem, assume there are no overlapping regions that could create conflicts between operations.

Operations

typescript

type Insert = { type: "insert"; position: number; text: string }
type Delete = { type: "delete"; position: number; length: number }

type Operation = Insert | Delete

Implement these four methods within CollaborativeEditor:

typescript

/**
 * Inserts `text` at the given position.
 */
private insert(position: number, text: string): void

/**
 * Deletes `length` characters starting at position.
 */
private delete(position: number, length: number): void

/**
 * Given that opA has already been applied to the document, return an
 * adjusted version of opB adjusted so it preserves its original intent.
 */
private transform(opA: Operation, opB: Operation): Operation

/**
 * Applies a client operation, transforming it if needed to account for
 * changes since the client's version.
 */
accept(op: Operation, clientVersion: number): void

Example

typescript

const editor = new CollaborativeEditor("Hello world")
editor.getCurrentContent() // "Hello world"
editor.getVersion() // 0

editor.accept({ type: "insert", position: 5, text: "!" }, clientVersion: 0)
editor.getCurrentContent() // "Hello! world"
editor.getVersion() // 1

editor.accept({ type: "delete", position: 6, length: 5 }, clientVersion: 0)
editor.getCurrentContent() // "Hello!"
editor.getVersion() // 2

The original prompt said that the class contained starter code, but that starter class was not included in the retained screenshot.

Supplied Python answer

The following answer was supplied with the prompt. It is preserved without correction.

python

from dataclasses import dataclass


@dataclass
class Insert:
    position: int
    text: str
    type: str = "insert"


@dataclass
class Delete:
    position: int
    length: int
    type: str = "delete"


Operation = Insert | Delete


class CollaborativeEditor:
    def __init__(self, initial: str = ""):
        self.content: str = initial
        self.history: list[Operation] = []
        self.version: int = 0

    def get_current_content(self) -> str:
        return self.content

    def get_latest_version(self) -> int:
        return self.version

    def insert(self, position: int, text: str) -> None:
        """
        Inserts text at the given position.
        """
        self.content = self.content[:position] + text + self.content[position:]
        self.version += 1

    def delete(self, position: int, length: int) -> None:
        """
        Deletes length characters starting at position.
        """
        self.content = self.content[:position] + self.content[position + length:]
        self.version += 1

    def transform(self, op_a: Operation, op_b: Operation) -> Operation:
        """
        Given that op_a has already been applied to the document, return an
        adjusted version of op_b so it preserves its original intent.
        """
        if isinstance(op_a, Insert):
            insert_length = len(op_a.text)

            # if op_a inserted before our op_b position, shift op_b right
            if op_b.position > op_a.position:
                op_b.position += insert_length

        else:
            # if op_a deleted before our op_b position, shift op_b left
            if op_b.position > op_a.position:
                op_b.position -= op_a.length

        return op_b

    def accept(self, op: Operation, client_version: int) -> None:
        """
        Applies a client operation, transforming it if needed to account for
        changes since the client's version.
        """
        current_operation = op

        for version in range(client_version, len(self.history)):
            current_operation = self.transform(
                self.history[version],
                current_operation,
            )

        if isinstance(current_operation, Insert):
            self.insert(current_operation.position, current_operation.text)
        else:
            self.delete(current_operation.position, current_operation.length)

        self.history.append(current_operation)


def assert_equal(actual: str, expected: str) -> None:
    if actual == expected:
        print(f"✅ {actual}")
    else:
        print(f"❌ expected: {expected}, actual: {actual}")


editor = CollaborativeEditor("Hello world")
assert_equal(editor.get_current_content(), "Hello world")
assert editor.get_latest_version() == 0

editor.accept(Insert(position=5, text="!"), client_version=0)
assert_equal(editor.get_current_content(), "Hello! world")
assert editor.get_latest_version() == 1

editor.accept(Delete(position=6, length=5), client_version=0)
assert_equal(editor.get_current_content(), "Hello!")
assert editor.get_latest_version() == 2