Question

Google | Interview experiences (Phone Screening) with Solutions | SDE | 2022 | Set-58

Answer 1

Technical Phone Screen Interview (45~60 minutes)

My original scheduled phone interview didn't happen due to the interviewer's availability. I rescheduled it for the next week, giving me a bit more time to solve more leetcode problems. This time I focused more on graph questions and I guess this saved me!

The interviewer was from Fitbit (that’s when I knew it was acquired by Google) and he went straight into the problem and gave the problem statement which if I remember correctly went like this:

We have several WiFi routers placed at various (x,y) coordinates in a given 2D plane. All the routers have a signal range of 10 units and each router has a unique name. If a router receives a message, it will broadcast it to all reachable routers within its range and shut itself down almost instantly.For simplicity, assume you are already provided with an implementation of the distance(Router a, Router b) method.Given a list of routers, a source router, and a target router, return true if the source router can broadcast a message to the target router.

Router { 
  string name; 
  int x,y; 
}bool isReachable(Router source, Router target, List<Router> routers) {
}

The actual problem statement was vague which I think is deliberately done to make sure I ask all the necessary clarifying questions before I start writing the code. I managed to ask a couple of questions and the interviewer provided a simple testcase which I’ve plotted below for better visualization:

2D plane with wifi routers

From the above router locations :

• A -> B is reachable
• A -> C is reachable
• A -> D is not reachable.

Fortunately, I’d solved an almost similar question in leetcode before:

https://leetcode.com/problems/detonate-the-maximum-bombs/

Answer 2

From the start, I knew this could be modeled as a graph problem. I started communicating my thought process and told him what an edge between two routers means, how a broadcast message would flow through the graph etc. Once I was sure that its a graph problem, I tried to see which traversal would work best in this case: BFS or DFS. I had a bitter experience with my previous Amazon SDE-III interview where I made a wrong choice of traversal and got into a rabbit hole, so this time I made sure to think properly before I chose one. I felt BFS works best for this case and got buy-in from the interviewer before I started to write the code. I took a few minutes of silence to think about how I was going to structure the code and the interviewer intervened checking with me if I was stuck. Without much delay, I decided to just write whatever came to my mind -> a Queue, a visited Set, a check for an edge, etc etc. I felt it was better to write something out rather than visualizing the perfect code in my head.

I managed to write a decent readable code and then the interviewer asked me to dry run against the test cases. While doing so, I found some minor bugs and fixed those immediately without any hints from the interviewer. The interviewer was pretty happy with my code and it was only 30 minutes into the interview. He immediately threw in follow-up questions with a new set of requirements as given below:

Follow up: Refactor the code to handle the case where a router will only broadcast to the nearest reachable routers that are at the minimum distance and not to all reachable routers.

2D plane with wifi routers

IIRC, A -> C is unreachable with the new requirements.

Since time was too less, I managed to quickly write a function to get the list of routers from a given router that sits at the minimum distance. I had skipped some silly details in the code since the interviewer was concerned about the data structures I was using for this computation. He was also interested to see how I plug this function into my existing code. While refactoring the code, the interview document became unreachable and the interviewer confirmed that there is some internal technical issue. So I just verbally explained my plan and the interviewer was ok.

I tried to rewrite whatever I could remember and jotted it down here:

 

public class RouterBroadcasts {
	private static class Router {
	String name;
	int x, y;
	public Router(String name, int x, int y) {
	this.name = name;
	this.x = x;
	this.y = y;
	}
	public boolean equals(Object o) {
	Router router = (Router) o;
	return x == router.x && y == router.y && name.equals(router.name);
	}
	}
	private double distance(Router a, Router b) {
	return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	}
	private boolean isInRange(Router router, Router otherRouter) {
	return distance(router, otherRouter) <= 10.0;
	}
	public boolean isReachable(Router start, Router target, List<Router> allRouters) {
	Queue<Router> bfsQ = new LinkedList<>();
	Set<String> shutdownRouters = new HashSet<>();
	bfsQ.add(start);
	while (!bfsQ.isEmpty()) {
	Router broadcastRouter = bfsQ.remove();
	if (broadcastRouter.equals(target)) return true;
	if (shutdownRouters.contains(broadcastRouter.name)) continue;
	List<Router> routersInRange = allRouters.stream()
	.filter(nextRouter -> !nextRouter.equals(broadcastRouter)
	&& !shutdownRouters.contains(nextRouter.name)
	&& isInRange(broadcastRouter, nextRouter))
	.collect(Collectors.toList());
	//bfsQ.addAll(routersInRange); // first version
	bfsQ.addAll(nearestRouters(broadcastRouter, routersInRange)); // follow-up version
	shutdownRouters.add(broadcastRouter.name);
	}
	return false;
	}
	private List<Router> nearestRouters(Router source, List<Router> routersInRange) {
	double minDistance = Double.MAX_VALUE;
	HashMap<Double, List<Router>> routersByDistance = new HashMap<>();
	for (Router router : routersInRange) {
	double dist = distance(source, router);
	minDistance = Math.min(dist, minDistance);
	routersByDistance.putIfAbsent(dist, new LinkedList<>());
	routersByDistance.computeIfPresent(dist, (d, routers) -> {
	routers.add(router);
	return routers;
	});
	}
	return routersByDistance.getOrDefault(minDistance, new LinkedList<>());
	}
	public static void main(String[] args) {
	// initial version testcases
	RouterBroadcasts rbc = new RouterBroadcasts();
	Router A = new Router("A", 0, 0);
	Router B = new Router("B", 0, 8);
	Router C = new Router("C", 0, 17);
	Router D = new Router("D", 11, 0);
	System.out.println(rbc.isReachable(A, B, Arrays.asList(A, B, C, D))); //true
	System.out.println(rbc.isReachable(A, C, Arrays.asList(A, B, C, D))); //true
	System.out.println(rbc.isReachable(A, D, Arrays.asList(A, B, C, D))); //false
	// follow-up version testcases
	Router E = new Router("E", 4, 0);
	Router F = new Router("F", 0, 4);
	Router H = new Router("H", 6, 8);
	System.out.println(rbc.isReachable(A, C, Arrays.asList(A, B, C, E, F))); //true
	System.out.println(rbc.isReachable(A, C, Arrays.asList(A, B, C, E, F, H))); //false
	}
	}

 

Results

The results came out positive within a few hours in my email and the recruiter asked me to schedule a call for a briefing on the next steps which happened the next day. The recruiter gave a detailed review of the interviewer’s feedback and it really boosted my confidence. As of now, I’ll be waiting for the team matching process to be complete, and told me to expect some delays.

I felt the screening interview wasn’t as hard as I thought and I think the interviewers are a bit lenient during screening rounds. I believe the upcoming onsite rounds are likely to be harder. Since Google interviews are targeting the best software engineers out there, grinding medium/hard leetcode questions is probably the only way out to meet their bar.