Validate BFS order queries on a tree
Company: Rubrik
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
You are given an undirected tree described by two equal-length arrays `u` and `v` (each of length `n-1`). For every index `i`, there is an undirected edge between `u[i]` and `v[i]`. The tree contains exactly `n` distinct node labels (labels are arbitrary integers).
You are also given `q` queries. Each query is an array `order` of length `n` containing each node label exactly once (a permutation).
For each query, decide whether `order` can be the output of a standard **BFS traversal** on this tree under the following rules:
- The BFS start node is `order[0]`.
- BFS uses a FIFO queue.
- When a node is dequeued, you may enqueue its **unvisited** neighbors in **any order** (i.e., neighbor iteration order is not fixed).
- The BFS output is the dequeue order.
Return a boolean for each query.
Example:
- `u = [1, 1, 4]`, `v = [3, 2, 3]` defines edges `(1,3), (1,2), (4,3)`.
- For `order = [1,2,3,4]`, the answer is `true` (one valid BFS enqueues `2` then `3` after visiting `1`).
Constraints (typical interview setting):
- `n` can be up to `2e5`.
- `q` can be large; aim for better than `O(q * n^2)`.
Quick Answer: This question evaluates understanding of BFS traversal, tree graph representation, and the ability to reason about allowable dequeue/enqueue orderings in a FIFO queue.
Given tree edges u[i]-v[i] and several full-node orders, return whether each order can be produced by BFS starting at order[0] when each node may enqueue unvisited neighbors in any order.
Constraints
- The graph is a tree for the node labels in each query
- Each query should contain each node exactly once
Examples
Input: ([1, 1, 4], [3, 2, 3], [[1, 2, 3, 4], [1, 4, 3, 2], [4, 3, 1, 2]])
Expected Output: [True, False, True]
Input: ([0, 0, 1], [1, 2, 3], [[0, 1, 2, 3], [0, 2, 1, 3], [0, 3, 1, 2]])
Expected Output: [True, True, False]
Input: ([], [], [[5], []])
Expected Output: [True, False]
Hints
- Sort each adjacency list by the proposed order, run BFS, then compare the produced order.