Question: Google 2023 Summer Internship Interview Experience
4
Entering edit mode

## Google 2023 Summer Internship Interview Experience

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.

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

Round 2

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

Some clarification I asked for -

1. What if there would be no circles or the list of circles is empty?
2. 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.

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

Verdict - Selected

Tips and Takeaways -

1. Communication is very important, think loudly, and interviewers are there to guide you.
2. 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.
3. Last but not the least, have faith in yourself.

All the best!

1
Entering edit mode

## Round 2 Question 1

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.

Code

``````ll n = bombs.size();
for (ll i = 0; i &lt; n; i++)
{
for (ll j = 0; j &lt; 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] &gt;= sqrt(d))
{
}
}
}
}
ll ans = 1;
for (ll i = 0; i &lt; n; i++)
{
mem0(vis);
dfs(i, -1);
ll cnt = 0;
for (ll j = 0; j &lt; n; j++)
if (vis[j])
cnt++;

ans = max(ans, cnt);
}
return ans;
``````