Entering edit mode

*Topics: Graphs, Hashmaps*

**Interview Rounds**

There were 2 technical interview rounds of 45 min each, No HR round was there.

*Round 1*

The interviewer directly started out with the question, without any introduction. She first asked me to code the brute force solution, since we need to count the ordered pairs, I suggested the O(n^2) time complexity naive approach, and then she asked me to code it in the doc.

I suggested the optimised solution using a hint.

Time Complexity - O(n)

She also asked me to write the test cases.

*Questions Interviewer asked* -

- Why did I choose Hashmaps?
- Why do Hashmaps have O(1) complexity in finding an element?

*The question I asked -*

Since the interviewer didn’t start with an introduction, I asked about the introduction and in which teams she was working.

*Round 2*

The interviewer started with an Introduction and after that, he put the question on the doc.

Click here to Practice

Submit Problem to OJ

Some clarification I asked for -

- What if there would be no circles or the list of circles is empty?
- List of circles will have only one circle?

I solved the question using DFS. He also asked me for 3-4 follow-ups and asked me how I would approach them. He didn’t ask me to write code for the follow-ups.

The question I asked -

- I asked him about the team in which he was working.
- Any research publications he has done in the past?

**Verdict** - Selected

**Tips and Takeaways -**

- Communication is very important, think loudly, and interviewers are there to guide you.
- You should be well-versed in the Data Structures that you are using. In my first interview, the interviewer asked me 2-3 questions about Hashmaps.
- Last but not the least, have faith in yourself.

*All the best!*

Entering edit mode

**Overview**

You are given a list of bombs. The range of a bomb is defined as the area where its effect can be felt. This area is in the shape of a circle with the center as the location of the bomb.

The bombs are represented by a 0-indexed 2D integer array of bombs where bombs[i] = [xi, yi, ri]. xi and yi denote the X-coordinate and Y-coordinate of the location of the ith bomb, whereas ri denotes the radius of its range.

You may choose to detonate a single bomb. When a bomb is detonated, it will detonate all bombs that lie in its range. These bombs will further detonate the bombs that lie in their ranges.

Given the list of bombs, return the maximum number of bombs that can be detonated if you are allowed to detonate only one bomb.

**Solution**

- The problem can be reduced to a graph problem.
- Let's represent each bomb as node of the graph.
- Let's draw a directed edge from one bomb to another bomb if it can detonate the other bomb.
- Now we will do dfs from each of the node(bomb) and see how many other nodes can be visited. Let's denote this number as cur_vis.
- The answer would be maximum of (answer, cur_vis).

**Code**

```
ll n = bombs.size();
for (ll i = 0; i < n; i++)
{
for (ll j = 0; j < n; j++)
{
if (i != j)
{
ll x1 = bombs[i][0];
ll y1 = bombs[j][0];
ll x2 = bombs[i][1];
ll y2 = bombs[j][1];
ll d = (x1 - y1) * (x1 - y1) + (x2 - y2) * (x2 - y2);
if ((ll)bombs[i][2] >= sqrt(d))
{
adj[i].push_back(j);
}
}
}
}
ll ans = 1;
for (ll i = 0; i < n; i++)
{
mem0(vis);
dfs(i, -1);
ll cnt = 0;
for (ll j = 0; j < n; j++)
if (vis[j])
cnt++;
ans = max(ans, cnt);
}
return ans;
```

Loading Similar Posts