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.

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.

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.

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.

Hints

  1. Kahn's algorithm uses indegree counts to repeatedly choose nodes that currently have no unmet prerequisites.
  2. 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'

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

Expected Output: 'hello'

Approach

The solution simulates the editor while keeping an inverse-operation stack (history) so any operation can be undone in O(its size). Data structures - text: a list of single characters (not a string), so suffix deletes and appends mutate in place instead of rebuilding an immutable string each step. - history: a stack where each entry is the inverse of an applied operation. Per-operation logic - ('append', s): push every char of s onto text, then record the inverse ('delete', len(s)) — to undo an append we delete exactly that many chars. - ('delete', k): clamp k to the current length (min(k, len(text)), matching the "delete everything if k too large" rule), snapshot the removed suffix removed, delete it, and record the inverse ('append', removed) — to undo we re-append exactly what was removed. - ('undo',): if history is empty, do nothing (covers the "nothing to undo" case). Otherwise pop the latest inverse and apply it. Crucially, applying an undo does not push a new inverse, so a sequence of undos walks back through real edits one at a time and naturally stops once history is exhausted. Why it's correct: each non-undo edit stores precisely the action that reverses it (including the clamped/snapshotted suffix), so undo restores the exact prior state. Because undo itself records nothing, repeated undos can't loop and extra undos beyond available history are no-ops. Finally ''.join(text) materializes the answer once.

Time complexity: O(T), where T is the total number of characters appended, deleted, or restored across all operations

Space complexity: O(T) — the `text` buffer plus the restored-suffix snapshots stored in `history` are both bounded by the total characters processed

Hints

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

Loading coding console...

Show the approach

Approach

This is Kahn's algorithm for topological sorting, modified with a min-heap to guarantee the lexicographically smallest valid ordering.

Build the graph. We create an adjacency list graph and an indegree array. For each edge [u, v] (meaning u must come before v), we add v to graph[u] and increment indegree[v]. So indegree[i] counts how many prerequisites task i still has.

Seed the heap. Every task with indegree == 0 has no unmet prerequisites and is eligible to go next. We put all such tasks into a min-heap. Using a heap (instead of a plain queue) is the key trick: among all currently-eligible tasks, we always emit the smallest label first, which yields the lexicographically smallest result.

Process. Repeatedly pop the smallest eligible task, append it to order, and "remove" it by decrementing the indegree of each neighbor. Whenever a neighbor's indegree drops to 0, all its prerequisites are now placed, so we push it onto the heap.

Cycle detection / correctness. If the graph has a cycle, the tasks in that cycle can never reach indegree 0, so they're never emitted. Thus len(order) < n signals a cycle, and we return []. Otherwise every task is emitted exactly once in a valid order. Greedily choosing the smallest available label at each step is provably optimal for lexicographic order, because deferring a smaller eligible label can never produce a smaller sequence. Edge cases like n == 0 naturally return [].

Time complexity:
O((n + m) log n), where m = len(edges). Each node is pushed/popped from the heap once (O(log n) each) and each edge is relaxed once.
Space complexity:
O(n + m) for the adjacency list, indegree array, and heap.