9 months ago

Sakshi • 40

Bhopal

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.

Questions Interviewer asked -

1. Why did I choose Hashmaps?
2. 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.

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.

The question I asked -

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!

4 months ago

Ujjwal Srivastava 320

Bengaluru

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.
• 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;