How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Harvey.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Harvey during technical interviews.

Implement a Cursor-Based Text Editor | Harvey Coding Question

Implement a Cursor-Based Text Editor

Company: Harvey

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement an in-memory text editor that maintains a mutable string and a cursor position between characters. The editor starts with an empty document and the cursor at position 0. Support the following operations efficiently: - `insert(text: string) -> void`: Insert `text` immediately to the left of the cursor. After insertion, the cursor should be after the inserted text. - `delete(k: int) -> int`: Delete up to `k` characters immediately to the left of the cursor. Return the number of characters actually deleted. - `move_left(k: int) -> string`: Move the cursor left by up to `k` positions. Return the last at most 10 characters to the left of the cursor after the move. - `move_right(k: int) -> string`: Move the cursor right by up to `k` positions. Return the last at most 10 characters to the left of the cursor after the move. Constraints: - The total number of operations can be large, for example up to `2 * 10^5`. - The total number of inserted characters can be large. - Optimize for time complexity; avoid rebuilding the full document on every operation. Discuss the time complexity of each operation and implement the data structure.

Quick Answer: This question evaluates understanding of data structures and algorithmic efficiency for mutable sequences and cursor manipulation, including analysis of time complexity for common editor operations under heavy workloads.

Implement an in-memory text editor with a cursor that sits between characters. The editor starts with an empty document and the cursor at position 0. You are given a list of operations to perform in order. Each operation is one of: - `('insert', text)`: insert `text` immediately to the left of the cursor. After insertion, the cursor moves to the end of the inserted text. - `('delete', k)`: delete up to `k` characters immediately to the left of the cursor and return the number of characters actually deleted. - `('move_left', k)`: move the cursor left by up to `k` positions and return the last at most 10 characters to the left of the cursor after the move. - `('move_right', k)`: move the cursor right by up to `k` positions and return the last at most 10 characters to the left of the cursor after the move. Write an efficient solution that avoids rebuilding the whole document on every operation. For this problem, return a list of results in the same order as the operations: - For `insert`, append `None`. - For `delete`, append the integer number of deleted characters. - For `move_left` and `move_right`, append the returned preview string.

Constraints

0 <= len(operations) <= 2 * 10^5
0 <= k <= 2 * 10^5 for delete and move operations
The sum of lengths of all inserted strings can be large (for example up to 2 * 10^5)
Text may be empty
Your solution should avoid rebuilding the full document after every operation

Examples

Input: ([('insert', 'hello'), ('insert', 'world'), ('move_left', 5), ('delete', 3), ('insert', 'X'), ('move_right', 10)],)

Expected Output: [None, None, 'hello', 3, None, 'heXworld']

Explanation: After inserting 'hello' and 'world', the document is 'helloworld|'. Moving left by 5 gives 'hello|world'. Deleting 3 removes 'llo', inserting 'X' makes 'heX|world', and moving right to the end gives preview 'heXworld'.

Input: ([('delete', 5), ('move_left', 1), ('insert', 'abc'), ('move_left', 10), ('move_right', 2), ('move_right', 10)],)

Expected Output: [0, '', None, '', 'ab', 'abc']

Explanation: Deleting or moving on an empty document does nothing. Moving left by more than the available characters stops at the start, and moving right by more than available stops at the end.

Input: ([('insert', 'abcdefghijklmnop'), ('move_left', 3), ('move_right', 1), ('delete', 20), ('move_left', 2)],)

Expected Output: [None, 'defghijklm', 'efghijklmn', 14, '']

Explanation: After moving left 3, there are 13 characters to the left of the cursor, so only the last 10 are returned. Moving right 1 adds one more character to the left. Deleting 20 removes all 14 available characters to the left of the cursor.

Input: ([('insert', 'abc'), ('move_left', 1), ('insert', 'XYZ'), ('move_right', 2), ('delete', 4), ('move_left', 2)],)

Expected Output: [None, 'ab', None, 'abXYZc', 4, '']

Explanation: The insertion of 'XYZ' happens in the middle of the document. Moving right by 2 only moves 1 character because only one character is to the right of the cursor.

Input: ([('insert', ''), ('insert', 'a'), ('move_left', 2), ('delete', 1), ('move_right', 5)],)

Expected Output: [None, None, '', 0, 'a']

Explanation: Inserting an empty string changes nothing. Moving left by more than available stops at the start, deleting from the start removes nothing, and moving right restores the single character.

Hints

Think about splitting the document into the characters to the left of the cursor and the characters to the right of the cursor.
If you keep two stacks, moving the cursor is just transferring characters between them, and the preview is simply the last 10 characters of the left stack.

Quick Overview

This question evaluates understanding of data structures and algorithmic efficiency for mutable sequences and cursor manipulation, including analysis of time complexity for common editor operations under heavy workloads.