Education : Tier 1 CSE
YOE: 3
Current Company : MNC
cp stats:
lc ~2450 rated
cf ~1850 rated
Pasted Q at 5 mins:
Base Question - (10 mins)
Given a connected acyclic graph with every node having at most 3 neighbours, find a valid node which forms a binary tree.
Solved+coded+tc/sc discussion in 10 mins
Follow up 1 - (10 mins)
Now every node is either Black or White , at every depth in the tree colors should be alternating. Find a valid node.
Solved+coded+tc/sc discussion in 10 mins
Follow up 2 - (10 mins)
Now graph can be disconnected.
Clarified requirements and then
Solved+coded+tc/sc discussion in 10 mins
Follow up 3 - (10 mins)
Now every node is either Red , Black or White. Find a valid root node ,
only allowed sequence of depths is RWBRWB.... Root can be of any color.
Told brute force by selecting each node and doing bfs/dfs. He was not satisfied and asked me to optimize further.
3 mins gone.
Now barely 7 mins were left. I tried some parity or distance between same depth stuff but it didnt work, he didn't give any hints. For optimization I was trying to use dfs+parity to precompute some info but it wasn't helping much to identify a valid root.
Finally he said 45 mins over wasn't much satisfied, said bye bye and left.
After the Interview I segregated few cases and eventually derived an O(n) solution proving only 1 unique root is possible but its too late now :(
Bad experience, 10 mins for last follow up is not justified as it was pretty difficult. Also why did they ask 3 follow ups.
Interviewer wasn't communicating properly or even trying to help.
Got reject in this round, further rounds got cancelled.
Horrible experience , will never Interview with Google again.
They expect you to either know solution beforehand or solve it within 10 minutes.


