Implement Collaborative Document Editing

Problem

You are building a collaborative text editor where multiple users can simultaneously edit the same document. Your task is to implement the core operation processing system that applies a sequence of editing operations (insertions and deletions) to a document state.

Each operation includes:

• The user who performed it
• The position in the document where the operation occurs
• The operation type (insert or delete)
• Additional data (text to insert or number of characters to delete)

When operations are performed concurrently by different users, their position indices refer to the document state before other concurrent operations are applied. Your system must handle operational transformation to ensure all operations are applied correctly and produce a consistent final document state.

Requirements

1. Implement a function that takes an initial document state and a list of operations
2. Process operations in the order they appear in the list
3. Handle both "insert" and "delete" operation types
4. Apply operational transformation: when processing an operation, adjust its position based on previously processed operations that occurred at earlier positions
5. Return the final document state after all operations are applied
6. Maintain document consistency across all concurrent edits

Constraints

• Document length: 0 ≤ length ≤ 10,000 characters
• Number of operations: 1 ≤ operations ≤ 1,000
• Operation positions are valid for the original document state (0 ≤ pos ≤ document length)
• Delete operations will not exceed document boundaries
• All operations are well-formed with required fields
• Time complexity: O(n × m) where n is number of operations and m is document length
• Space complexity: O(m) for document storage

Examples

Example 1:

Input: document_state = "" operations = [\{"user": "alice", "pos": 0, "type": "insert", "text": "Hello"\}] Output: "Hello" Explanation: Alice inserts "Hello" into an empty document at position 0.

Example 2:

Input: document_state = "Hello" operations = [\{"user": "bob", "pos": 5, "type": "insert", "text": " World"\}] Output: "Hello World" Explanation: Bob appends " World" after the existing "Hello" text.

Example 3:

Input: document_state = "document" operations = [ \{"user": "alice", "pos": 0, "type": "insert", "text": "My "\}, \{"user": "bob", "pos": 8, "type": "insert", "text": " file"\} ] Output: "My document file" Explanation: Alice inserts "My " at position 0. Bob's operation targets position 8 in the original document, which after Alice's insertion becomes position 11, resulting in "My document file".

Example 4:

Input: document_state = "The quick fox" operations = [ \{"user": "bob", "pos": 10, "type": "insert", "text": "brown "\}, \{"user": "alice", "pos": 4, "type": "delete", "length": 6\} ] Output: "The brown fox" Explanation: Bob inserts "brown " at position 10. Alice deletes 6 characters starting at position 4 ("quick "). The operations are transformed to maintain consistency.

Hint 1: Operational Transformation Basics When processing operations sequentially, each operation's position refers to the original document state. As you apply operations, you need to track how earlier operations affect the positions of later operations.

For example, if Operation A inserts 5 characters at position 2, and Operation B wants to insert at position 10, after applying A, B's effective position becomes 15 (10 + 5).

Hint 2: Tracking Position Deltas Maintain a running offset that tracks how much the document has grown or shrunk. As you process each operation:

• For insertions: add the length of inserted text to positions that come after
• For deletions: subtract the deleted length from positions that come after
• Only adjust positions that are greater than or equal to the current operation's position

Hint 3: String Manipulation Strategy Python strings are immutable, so use string slicing to construct the new document state:

• For insertion at position pos: doc[:pos] + text + doc[pos:]
• For deletion starting at position pos with length length: doc[:pos] + doc[pos+length:]

Track the cumulative position adjustment separately from applying the actual operation.

Full Solution `` Solution Explanation:

The solution implements operational transformation for collaborative editing:

1. Sequential Processing: We process operations one at a time in the order they appear, maintaining the current document state.

2. Position Adjustment: We track a position_offset that represents the cumulative effect of all previously processed operations. This offset is added to each operation's original position to get its adjusted position in the current document.

3. Insert Operations:

   • Insert text at the adjusted position using string slicing
   • Increase the position offset by the length of inserted text
   • This ensures subsequent operations that target positions after this insertion are correctly adjusted

4. Delete Operations:

   • Remove characters from the adjusted position using string slicing
   • Decrease the position offset by the number of deleted characters
   • This ensures subsequent operations account for the removed text

5. Consistency: By maintaining a running offset and applying operations sequentially, we ensure all operations are correctly transformed and the final document state is consistent.

Time Complexity: O(n × m) where n is the number of operations and m is the average document length. Each operation requires string slicing which is O(m).

Space Complexity: O(m) for storing the document state. In Python, strings are immutable, so each modification creates a new string, but only one document state is kept at a time.

This approach handles concurrent edits by treating operations as if they were applied to the original document state, then transforming their positions based on the order of application. This is a simplified version of Operational Transformation (OT), which is used in real collaborative editors like Google Docs.

def apply_operations(document_state, operations):
    """
    Apply a sequence of collaborative editing operations to a document.
    
    Args:
        document_state: Initial document content as a string
        operations: List of operation dictionaries with keys:
            - user: username performing the operation
            - pos: position in document
            - type: "insert" or "delete"
            - text: text to insert (for insert operations)
            - length: number of characters to delete (for delete operations)
    
    Returns:
        Final document state as a string
    """
    # Current document state
    current_doc = document_state
    
    # Track position adjustments for operational transformation
    # This maps original positions to adjusted positions
    position_offset = 0
    
    for op in operations:
        # Get the original position from the operation
        original_pos = op["pos"]
        
        # Calculate the adjusted position based on previous operations
        # Operations at earlier positions have already been applied
        adjusted_pos = original_pos + position_offset
        
        if op["type"] == "insert":
            # Insert text at the adjusted position
            text_to_insert = op["text"]
            current_doc = current_doc[:adjusted_pos] + text_to_insert + current_doc[adjusted_pos:]
            
            # Update position offset for subsequent operations
            # All positions after this insertion need to shift right
            position_offset += len(text_to_insert)
            
        elif op["type"] == "delete":
            # Delete characters starting at the adjusted position
            length_to_delete = op["length"]
            end_pos = adjusted_pos + length_to_delete
            current_doc = current_doc[:adjusted_pos] + current_doc[end_pos:]
            
            # Update position offset for subsequent operations
            # All positions after this deletion need to shift left
            position_offset -= length_to_delete
    
    return current_doc