Google L4 Interview Experience | DSA Round 1

The interview started with a graph problem and progressed through multiple follow-ups, each adding a new constraint. The focus was on problem-solving, optimization, and handling edge cases under time pressure.

Base Question: Find a Valid Root

Given a connected, acyclic graph where each node has at most three neighbours, find a node that can serve as the root of a valid binary tree.

I solved and coded the solution, including time and space complexity analysis, within around 15 minutes.

Follow-up 1: Alternating Node Colours

Each node was now either black or white. The colours had to alternate at every depth of the rooted tree.

I found a valid approach, implemented it, and discussed its complexity within another 15 minutes.

Follow-up 2: Disconnected Graph

The graph could now contain multiple disconnected components.

After clarifying the requirements, I solved the problem and discussed the complexity within approximately 10 minutes.

Follow-up 3: Three-Colour Pattern

The nodes could now be red, white, or black, and the colours across successive depths had to follow the repeating pattern R => W => B => R => W => B .... The root could be any colour.

I initially proposed a brute-force approach: try each node as the root and run BFS or DFS to check whether the colouring pattern was valid. The interviewer wanted a more optimized solution.

With only around seven minutes remaining, I tried reasoning about parity and distances between nodes at the same depth, but couldn't derive the optimization during the interview. The interviewer didn't provide hints, and the round ended after 45 minutes.

After the interview, I revisited the problem, explored additional cases, and eventually derived an O(n) solution. Unfortunately, I reached it too late to demonstrate it during the round.

My Takeaways

• Practise graph problems involving BFS, DFS, tree rooting, and graph colouring.

• For follow-up questions, identify what changes in the constraints and reuse insights from the earlier solutions.

• When a brute-force solution isn't sufficient, look for shared information that can be precomputed rather than repeating a traversal from every node.

• Manage time carefully, especially when a follow-up introduces a substantially harder optimization problem.

The final follow-up was challenging to solve within the limited time, and I felt the discussion could have been more collaborative. I wasn't sure whether I'd clear the round, but reviewing the problem afterward helped me understand the optimization I had missed.