Implement topological sort and tree boundary traversal
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two separate coding tasks.
## Problem A — Order courses with prerequisites
You have `n` courses labeled `0..n-1` and a list of prerequisite pairs `prerequisites`, where each pair `[a, b]` means **to take course `a`, you must first take course `b`**.
**Task:** Return **any valid ordering** of all courses that satisfies prerequisites. If it is impossible (because of a cycle), return an **empty list**.
**Input:**
- `n` (integer)
- `prerequisites` (list of pairs)
**Output:**
- A list of length `n` representing a valid order, or `[]` if no order exists.
**Constraints (typical):**
- `1 ≤ n ≤ 10^5`
- `0 ≤ len(prerequisites) ≤ 2*10^5`
**Notes:**
- Implement the algorithm yourself (e.g., topological sort).
- Be prepared to write a few basic tests (e.g., cycle case, disconnected graph).
---
## Problem B — Boundary traversal of a (complete/balanced) binary tree
You are given the root of a binary tree. The tree is guaranteed to be **complete and balanced** (interview variant constraint), but your solution may work for any binary tree.
Define the **boundary** of the tree in **anti-clockwise** order as:
1. The **root** (once).
2. The **left boundary** (excluding leaves): from `root.left` going downward, always taking the next boundary node.
3. All **leaf nodes** from left to right.
4. The **right boundary** (excluding leaves): from `root.right` going downward, collected top-down but output **bottom-up**.
**Task:** Return a list of node values in boundary order, with **no duplicates**.
**Input:**
- `root` of a binary tree
**Output:**
- List of integers representing the boundary traversal.
**Edge cases to consider:**
- Single-node tree
- Root has only one child
- Trees where left/right boundary paths include missing children (even if the interview variant says complete)
**Complexity target:**
- Time `O(N)`, space `O(H)` (recursion) or `O(N)` worst case depending on implementation.
Quick Answer: These tasks evaluate core competencies in directed graph algorithms (topological ordering and cycle detection) and binary tree traversals (boundary identification and leaf enumeration), testing understanding of dependency modeling and traversal patterns.
Part 1: Order Courses With Prerequisites
You are given n courses labeled 0 through n - 1 and a list of prerequisite pairs. Each pair [a, b] means course b must be taken before course a. Return an ordering of all courses that satisfies every prerequisite. If no such ordering exists because the prerequisite graph contains a cycle, return an empty list. If multiple valid orderings exist, any valid ordering is acceptable; the reference solution below uses a min-heap to choose the smallest currently available course.
Constraints
- 1 <= n <= 100000
- 0 <= len(prerequisites) <= 200000
- 0 <= course, prerequisite < n for every prerequisite pair
- The graph may be disconnected
- The graph may contain cycles
Examples
Input: (1, [])
Expected Output: [0]
Explanation: A single course with no prerequisites can be taken immediately.
Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])
Expected Output: [0, 1, 2, 3]
Explanation: Course 0 must come before 1 and 2, and both 1 and 2 must come before 3.
Hints
- Track how many prerequisites each course still has using an indegree array.
- Courses with indegree 0 can be taken immediately; if you cannot process all courses, a cycle exists.
Part 2: Boundary Traversal of a Binary Tree
You are given a binary tree and must return its boundary in anti-clockwise order with no duplicate nodes. The boundary consists of: the root once, the left boundary excluding leaves, all leaves from left to right, and the right boundary excluding leaves in bottom-up order. For this coding version, the tree is provided as a standard level-order list using -1 as the missing-child sentinel. Although some interview variants guarantee the tree is complete and balanced, your solution should handle any valid binary tree shape.
Constraints
- 0 <= len(tree) <= 100000
- -1 is reserved as the missing-child sentinel
- All actual node values are non-negative integers
- The input list is a valid standard level-order encoding of a binary tree
Examples
Input: ([],)
Expected Output: []
Explanation: An empty tree has an empty boundary.
Input: ([10],)
Expected Output: [10]
Explanation: A single-node tree contains only the root.
Hints
- Do not add leaves while collecting the left or right boundary; collect all leaves in a separate pass to avoid duplicates.
- Collect the right boundary top-down into a temporary list, then reverse it before appending to the answer.