Google L3 Phone screen Problems

Round 1

Questions: 1️⃣ Binary Tree Root (No Color Constraints):
Given an undirected acyclic connected graph where each node has at most 3 edges, find a node which, when made the root, converts the graph into a binary tree.
Approach: Just return any node with degree less than 3.

2️⃣ Binary Tree with Alternating Colors:
Given an undirected connected acyclic graph where each node has at most 3 edges, and nodes are colored Black or White, find a root such that:

• The graph becomes a binary tree.
• The tree alternates in color across layers (e.g., Depth 0: White, Depth 1: Black, Depth 2: White, etc.).
  Either White or Black can be the starting color.
  Approach: First check if there is no edge with the same color on both ends and after verifying this return any node with degree less than 3.

3️⃣ Binary Tree with Fixed Color Order (R, B, W):
Given an undirected connected acyclic graph where each node has at most 3 edges, and nodes are colored Red (R), Blue (B), or White (W), find a root such that:

• The graph becomes a binary tree.
• The layers of the tree follow a fixed color sequence (e.g., RBWRBW… or BWRBWR… or WRBWRB).
  Approach:

1. Understanding Parent and Child Colors:
   • The color sequence (RBWRBW) implies that for any node with a given color, we know the required color for its parent and children:
     • If the node is Red (R), its parent must be White (W), and its children must be Blue (B).
     • If the node is Blue (B), its parent must be Red (R), and its children must be White (W).
     • If the node is White (W), its parent must be Blue (B), and its children must be Red (R).
2. Candidate Root Identification:
   • For a node to be a valid root, it should not have a neighbor with the color required for its parent (since a root node has no parent).
   • Conversely, the other neighbors of this node must align with the colors of its children.
   • A candidate root is any node that lacks a neighbor with the required parent color.
3. Uniqueness of Root:
   • If there are multiple nodes that qualify as candidate roots (i.e., more than one node without a parent color neighbor), it is impossible to construct a valid binary tree with the given color order. This is because:
     • Suppose one of these nodes is chosen as the root. The other candidate root would inevitably need a parent, but its parent wouldn’t have the required parent color, violating the color sequence constraint.
     • Therefore, there must be exactly one root with this property. If more than one candidate root exists, return -1.

Intuition Behind the Approach:

• The fixed color sequence (e.g., RBWRBW) determines strict rules for parent-child relationships based on colors.
• By observing the graph structure, a node that lacks a neighbor with its parent color is naturally suited to be the root.
• If there are multiple such nodes, a valid tree cannot be formed because the parent-child color constraints would break for at least one of them.