Writing Application: Collaborative Document Editor with Conflict Resolution

Question

## Problem

Design a class `DocumentEditor` that simulates a collaborative writing application. Multiple users can apply edits (insertions and deletions) concurrently. Edits are timestamped; when two edits conflict at the same position, the one with the **earlier timestamp wins**. Implement the following operations:

```python
class DocumentEditor:
    def __init__(self, initial_text: str): ...
    def insert(self, user_id: str, pos: int, text: str, ts: int) -> None: ...
    def delete(self, user_id: str, pos: int, length: int, ts: int) -> None: ...
    def get_document(self) -> str: ...
    def get_history(self, user_id: str) -> list[dict]: ...
```

## Example

```
editor = DocumentEditor("Hello world")
editor.insert("alice", 5, " beautiful", ts=1)
editor.delete("bob", 6, 5, ts=2)  # tries to delete "world" (pos 6 after alice's insert)
editor.get_document()
# -> "Hello beautiful world" (alice's insert at ts=1 takes effect first)
```

## Follow-ups

1. How would you implement an undo/redo stack per user?
2. What data structure best supports efficient insert/delete by position? (Rope, gap buffer?)
3. How does your conflict resolution change if last-write-wins instead of first-write-wins?
4. How would you persist edit history to allow document reconstruction at any point in time?

Writing Application: Collaborative Document Editor with Conflict Resolution

Question Details

Full Details

Topics

More from Karat