0 like 0 dislike
2,044 views
| 2,044 views

0 like 0 dislike

# 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/`
by Expert (30,360 points)
0 like 0 dislike

## Solution

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: