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 Netflix.

What role is this question designed for?

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

Implement ordering and undo executor | Netflix Coding Question

Implement ordering and undo executor

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

The interview included two coding tasks: 1. **Dependency ordering**: Given a set of tasks and their dependency relationships, return a valid execution order so that every task appears after all of its prerequisites. If no valid order exists because of a cycle, report that the schedule is impossible. 2. **Command executor with undo**: Design and implement a simple command executor that supports: - `execute(command)`: runs a command and records enough information to undo it later. - `undo()`: reverts the most recently executed command that has not yet been undone. Assume commands may modify shared application state. Discuss the interface you would use for commands, what data structure you would use to support undo, and how you would handle edge cases such as calling `undo()` when no command has been executed.

Quick Answer: This question evaluates graph algorithm skills (topological ordering and cycle detection) and software design competencies related to command interfaces, undo semantics, and shared-state management.

Part 1: Lexicographically Smallest Topological Ordering

You are given `n` tasks labeled from `0` to `n - 1` and a list of dependency pairs `edges`, where each pair `[u, v]` means task `u` must be completed before task `v`. Return a valid ordering of all tasks. If multiple valid orderings exist, return the lexicographically smallest one. If it is impossible to complete all tasks because the dependency graph contains a cycle, return an empty list.

Constraints

0 <= n <= 100000
0 <= len(edges) <= 200000
Each task label is an integer in the range [0, n - 1]
All dependency pairs are distinct

Examples

Input: (4, [[0, 1], [0, 2], [1, 3], [2, 3]])

Expected Output: [0, 1, 2, 3]

Explanation: Task 0 must come first. Then both 1 and 2 are available, so choose 1 before 2 for lexicographically smallest order.

Input: (5, [[0, 2], [1, 2], [3, 4]])

Expected Output: [0, 1, 2, 3, 4]

Explanation: This graph has two disconnected components. Choosing the smallest available task each time gives the required lexicographically smallest order.

Input: (3, [[0, 1], [1, 2], [2, 0]])

Expected Output: []

Explanation: The graph contains a cycle, so no topological ordering exists.

Input: (0, [])

Expected Output: []

Explanation: Edge case: there are no tasks, so the ordering is empty.

Input: (1, [])

Expected Output: [0]

Explanation: A single task with no dependencies is already a valid ordering.

Hints

Kahn's algorithm uses indegree counts to repeatedly choose nodes that currently have no unmet prerequisites.
To guarantee the lexicographically smallest valid order, use a min-heap instead of a normal queue.

Part 2: Text Command Executor With Undo

Implement a simple command executor for text editing. The editor starts with an empty string and processes operations in order. Supported operations are: - `('append', s)`: append string `s` to the end - `('delete', k)`: delete the last `k` characters; if `k` is larger than the current length, delete everything - `('undo',)`: undo the most recent `append` or `delete` operation that has not already been undone; if there is nothing to undo, do nothing Return the final text after processing all operations.

Constraints

0 <= len(operations) <= 100000
The total number of characters across all appended strings is at most 200000
0 <= k <= 200000 for delete operations
Only the three supported command types will appear

Examples

Input: [('append', 'abc'), ('append', 'de'), ('delete', 3)]

Expected Output: 'ab'

Explanation: After appending 'abc' and 'de', the text is 'abcde'. Deleting the last 3 characters leaves 'ab'.

Input: [('append', 'hello'), ('delete', 2), ('append', 'y'), ('undo',), ('undo',)]

Expected Output: 'hello'

Explanation: The first undo removes the appended 'y'. The second undo restores the two deleted characters.

Input: [('undo',), ('append', 'a'), ('undo',), ('undo',)]

Expected Output: ''

Explanation: Undo on empty history does nothing. After appending 'a', one undo removes it, and the final undo still does nothing.

Input: [('append', 'abc'), ('delete', 5), ('undo',)]

Expected Output: 'abc'

Explanation: Deleting more characters than exist clears the text. Undo restores the deleted content.

Input: []

Expected Output: ''

Explanation: Edge case: no operations means the text stays empty.

Hints

Undo should reverse the most recent still-active command, so a stack is a natural fit.
For each executed command, store just enough information to reverse it later instead of storing the whole text every time.

Quick Overview

This question evaluates graph algorithm skills (topological ordering and cycle detection) and software design competencies related to command interfaces, undo semantics, and shared-state management.