Google Phone Screen | L3
Summary
I had a phone screen for an L3 role at Google Bangalore where I was asked a graph reachability problem involving a corrupted node. I suggested a BFS approach and coded it, but received a rejection with feedback mentioning a brute-force approach.
Full Experience
Had my Google phone screen round in april for L3 role at Google Banglore. Interviewer was from Georgia and asked a simple question.
Question:
Given entry node, corrupted node and network of nodes, for each node check if it is reachable or not. corrupted node is node where incoming is possible but outgoing is not possible.
Exaple:
entry node : 5 corrupted node : 3 network : [ [3], [2,3], [1,4], [0,1,4], [2,3,5], [4] ]Output: [False,True,True,True,True,True]
Few constriant that I cleared from Interviewer:
- entry node != corrupted node
- network will be single component connected undirected graph
Got a rejection call after few days, Feedback mentioned brute-force approch. Don't what went wrong. Would be helpful if anyone can share optimal approch for above problem.
Felt really dumb :(
Interview Questions (1)
Given entry node, corrupted node and network of nodes, for each node check if it is reachable or not. corrupted node is node where incoming is possible but outgoing is not possible.
Exaple:
entry node : 5 corrupted node : 3 network : [ [3], [2,3], [1,4], [0,1,4], [2,3,5], [4] ]Output: [False,True,True,True,True,True]
Few constriant that I cleared from Interviewer:
- entry node != corrupted node
- network will be single component connected undirected graph