Google recruiting in India has become a sh*tshow. I literally had my phone screen interview rescheduled not once, not twice but THREE times and two of the reschedules were at a last-minute notice (all of them due to some "unforeseen circumstances" at their end). And when the interview does start, the interviewer is a Chinese guy whose accent was a bit difficult to understand.
The questions asked to me in the interview were exactly the same as in this post: https://leetcode.com/discuss/post/6246228/google-l3-phone-screen-problems-by-the_a-tbek/
1️⃣ :
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
I could figure out this one in 5 minutes, coded it in another 5 minutes.
Proof of correctness: The reason choosing any node with degree less than 3 works is because since it is a tree, if we traverse from any node considering it a root with for eg. DFS, any node other than root will have atmost 3 neighbours, one is its parent, and the other 2 can be taken as its left and right child (if any). The traversal must end somewhere with a leaf node that will have a degree 1, otherwise every node as one parent and one child in traversal which means there will be an infinite number of nodes.
So to get the root, we can loop over the adjacency list and return the first node whose degree is <= 2.
For the second question:
2️⃣ :
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.
This took me some time to figure out. Initially, I suggested that we could do a BFS for every node with degree less than 3 and check if the color at a level is differnt from the colour at the previous level. But this is an solution. Then after another 5-10 minutes, I could figure this out in a different way than the approach mentioned in the linked post.
My approach: We can check the adjaceny list and check for each node if it has all neighbours of same colour, if any 2 neighbours have different colors such a tree is not possible. (The linked post has a similar but slightly better approach where we can simply check every edge to have different colored nodes). After this we can choose any node with degree less than 3 and check with another BFS traversal if the levels alternate in color. Another BFS is required as checking only neightbours of same color doesn't handle the case of for eg. this tree with two nodes: B --- B
This is an O(V + E) solution, and I thought it might not be the best but should be sufficient.
Interviewer was kinda adamant for some time and suggested me change my approach to a simpler way (the simpler solution of checking all edges, refer to the linked post) but it didn't strike me during the interview.
Coding the BFS solution took me some more time. There was a minor bug in my solution which I corrected after a hint. Then interviewer suggested some more changes to code which I thought were unnecessary. The changes he suggested were like, "why store color in a Node object, we can pass a colors array" and so on.
I could not get to the 3rd follow up question, time was almost up. (btw the interviewer mentioned at the beginning that there will be 3 questions in total, so I figured the third must be the same as in the linked post)
I received a call today that I did not qualify for the next rounds ¯\_ (ツ)_/¯