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 Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at OpenAI during technical interviews.

Design an Editable Text Buffer | OpenAI Coding Question

Design an Editable Text Buffer

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The interview question was asked in three progressive stages. Design an in-memory text editor. 1. **Basic text buffer** Implement a data structure that efficiently supports: - `insert(position: int, text: str)` - `delete(start: int, end: int)` where `end` is exclusive - `get_text() -> str` 2. **Undo / redo** Extend the editor with: - `undo()` - `redo()` Requirements: - Every `insert` and `delete` operation must be undoable. - After any new edit, the redo history must be cleared. - Discuss how to make the operations efficient. 3. **Prefix-based autocomplete** Add: - `suggest(prefix: str, k: int) -> List[str]` Requirements: - Words contain only lowercase letters. - Return the top `k` words that start with `prefix`, ranked by current frequency. - Frequencies must increase when words are added and decrease when words are removed. - You may assume the autocomplete index receives whole-word additions and removals derived from editor updates.

Quick Answer: This question evaluates data structure design, mutable state management, undo/redo semantics, and prefix-based autocomplete indexing with dynamic frequency tracking.

Part 1: Basic Text Buffer

You are given a sequence of operations on an in-memory text buffer. Implement solution(operations) to process them in order. Supported operations are ('insert', position, text), ('delete', start, end) where end is exclusive, and ('get',). Return the result of every ('get',) operation in order. All positions and ranges are valid for the current text.

Constraints

0 <= len(operations) <= 5000
0 <= total number of inserted characters <= 100000
Insert positions and delete ranges are always valid for the current text
text may be an empty string

Examples

Input: [('insert', 0, 'hello'), ('get',)]

Expected Output: ['hello']

Explanation: Insert into an empty buffer, then read the full text.

Input: [('insert', 0, 'heo'), ('insert', 2, 'l'), ('insert', 3, 'l'), ('get',)]

Expected Output: ['hello']

Explanation: Two middle insertions build the word hello.

Input: [('insert', 0, 'abcdef'), ('delete', 2, 4), ('get',), ('insert', 2, 'CD'), ('get',)]

Expected Output: ['abef', 'abCDef']

Explanation: Delete removes positions 2 and 3, then a new substring is inserted at that gap.

Input: [('insert', 0, 'x'), ('delete', 0, 1), ('get',)]

Expected Output: ['']

Explanation: Deleting the only character leaves an empty buffer.

Input: []

Expected Output: []

Explanation: No operations means no output.

Hints

Python strings are immutable, so repeatedly rebuilding a string can be costly.
A mutable sequence such as a list of characters supports slice insertions and deletions cleanly.

Part 2: Text Buffer with Undo and Redo

Extend the text buffer to support undo and redo. Implement solution(operations) where operations may be ('insert', position, text), ('delete', start, end), ('undo',), ('redo',), or ('get',). Every insert and delete must be undoable. If a new edit happens after an undo, the redo history must be cleared. If undo or redo is not possible, treat it as a no-op. Return the result of every ('get',) operation in order.

Constraints

0 <= len(operations) <= 10000
0 <= total number of inserted characters <= 100000
All insert positions and delete ranges are valid for the current text
undo and redo on empty history should not raise errors

Examples

Input: [('insert', 0, 'hello'), ('undo',), ('get',), ('redo',), ('get',)]

Expected Output: ['', 'hello']

Explanation: Undo removes the insertion, and redo re-applies it.

Input: [('insert', 0, 'abcdef'), ('delete', 2, 5), ('get',), ('undo',), ('get',)]

Expected Output: ['abf', 'abcdef']

Explanation: Undo restores the deleted substring.

Input: [('insert', 0, 'abc'), ('undo',), ('insert', 0, 'z'), ('redo',), ('get',)]

Expected Output: ['z']

Explanation: A new edit after undo clears the redo stack, so redo does nothing.

Input: [('undo',), ('redo',), ('get',)]

Expected Output: ['']

Explanation: Undo and redo are no-ops when there is no history.

Hints

For each edit, store enough information to reverse it later.
Two stacks usually model undo and redo cleanly.

Part 3: Dynamic Prefix Autocomplete

Implement a dynamic autocomplete index. The function solution(operations) receives operations of three kinds: ('add', word), ('remove', word), and ('suggest', prefix, k). Words contain only lowercase letters. Adding a word increases its frequency by 1. Removing a word decreases its frequency by 1; if its frequency is already 0, ignore the operation. For each ('suggest', prefix, k), return up to k words that start with prefix, ordered by descending frequency, and then lexicographically ascending for ties. If prefix is an empty string, consider all words.

Constraints

0 <= len(operations) <= 10000
Words contain only lowercase English letters
1 <= len(word) <= 20 for add/remove operations
0 <= k <= 20
Removing a word with frequency 0 should do nothing

Examples

Input: [('add', 'apple'), ('add', 'app'), ('add', 'apple'), ('suggest', 'ap', 2)]

Expected Output: [['apple', 'app']]

Explanation: apple has frequency 2 and app has frequency 1.

Input: [('add', 'ball'), ('add', 'bat'), ('suggest', 'b', 2)]

Expected Output: [['ball', 'bat']]

Explanation: The frequencies are tied, so lexicographical order breaks the tie.

Input: [('add', 'apple'), ('add', 'apple'), ('add', 'app'), ('remove', 'apple'), ('suggest', 'ap', 2)]

Expected Output: [['app', 'apple']]

Explanation: After removal, both words have frequency 1, so app comes first lexicographically.

Input: [('remove', 'ghost'), ('add', 'dog'), ('add', 'deer'), ('add', 'dog'), ('suggest', '', 2), ('suggest', 'cat', 3)]

Expected Output: [['dog', 'deer'], []]

Explanation: Removing a missing word is ignored. Empty prefix means top words overall. Unknown prefixes return no suggestions.

Hints

A trie helps you jump directly to the subtree for a prefix.
To make results deterministic, sort matches by frequency descending and word ascending.

Quick Overview

This question evaluates data structure design, mutable state management, undo/redo semantics, and prefix-based autocomplete indexing with dynamic frequency tracking.