Round 1
Questions: You are given a tree with n nodes (labeled from 0 to n-1), and each node is colored with one of the letters ‘R’, ‘A’, or ‘W’. A tree is defined by having n-1 edges and no cycles. Additionally, each node has at most three neighbors.
We want to determine if there exists a node that can serve as a root such that the colors of the nodes follow one of the six possible repeating 3-color patterns level by level from that root. The six possible 3-color patterns are:
- RWA
- RAW
- WAR
- WRA
- ARW
- AWR
“Following the pattern” means that if the chosen pattern is p, then every node at depth d from the root (0-based) must have the color p[d % 3]. If there exists such a root and a pattern, return the index of that root. If multiple such roots exist, returning any one of them is fine. If no solution exists, return None.
Note:
- If the tree has only one node, any pattern starting with that node’s color will work, so that single node can be the root.
- Time complexity should be O(V), O(V^2) is considered brute force. The interviewer hinted that the tc is O(6 * V) -> O(V).
Input Format:
- edges: A list of pairs [u, v] representing the undirected edges of the tree.
- colors: A list of characters (‘R’, ‘A’, ‘W’) of length n, where colors[i] is the color of node i.
Output Format:
- Return the index of a valid root node if it exists.
- If no solution exists, return -1.
Examples:
Example 1:
n = 3 edges = [[0,1],[0,2]] colors = ['R','W','W'] Possible pattern: RWA - Depth 0: R - Depth 1: W For root=0: - Node 0 at depth 0 = 'R' matches 'R' - Nodes 1,2 at depth 1 = 'W','W' match 'W' Matches pattern RWA starting at root=0. Output: 0
Example 2:
n = 6 edges = [[0,1],[0,2],[1,3],[1,4],[2,5]] colors = ['R','A','A','W','W','W'] Pattern RAW: - Depth 0: R - Depth 1: A - Depth 2: W For root=0 with RAW: - Node 0='R', depth 0 → R ✔ - Nodes 1,2='A','A', depth 1 → A ✔ - Nodes 3,4,5='W','W','W', depth 2 → W ✔ All match perfectly. Output: 0
Example 3:
n = 3 edges = [[0,1],[1,2]] colors = ['R','R','R'] No pattern can fit a tree where all nodes have the same color and we need a 3-color repeating pattern. Output: -1
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.