## Google Interview Question

Software Engineers**Country:**United States

**Interview Type:**In-Person

O(N^2) time, O(N^2) memory

```
int playOrbGame(vector<vector<bool>>& orbs)
{
if (orbs.empty() || orbs[0].empty())
{
return 0;
}
auto N = orbs.size();
auto M = orbs[0].size();
vector<vector<int>> orb_column_sums(N, vector<int>(M,0));
for(size_t i = N - 2; i + 1 > 0; --i)
{
for(size_t j = 0; j < M; ++j)
{
orb_column_sums[i][j] = orbs[i+1][j] ? orb_column_sums[i+1][j] + 1 : orb_column_sums[i+1][j];
}
}
int orbs_left = 0;
for(size_t i = 0; i < N; ++i)
{
int min_column_orbs = max(M,N) + 1;
int column_to_keep_orb = -1;
for (size_t j = 0; j < M; ++j)
{
if (!orbs[i][j])
{
continue;
}
if (orb_column_sums[i][j] < min_column_orbs)
{
min_column_orbs = orb_column_sums[i][j];
column_to_keep_orb = j;
}
}
if (column_to_keep_orb != -1)
{
++orbs_left;
for(size_t k = i + 1; k < N; ++k)
{
orbs[k][column_to_keep_orb] = false;
}
for(size_t l = 0; l < M; ++l)
{
if (l != column_to_keep_orb)
{
orbs[i][l] = false;
}
}
}
}
return orbs_left;
}
```

just to see all the zeros that are connected will be in a single component.

So from a connected component of Zeros we only require one zero from that component.

So the answers it the no of connected component.

Can be done in O(N^2) time to add everything in union find by path compression.

0(N^2) space

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for ONE-ON-ONE private lessons by FB, Google and Uber engineers!

SYSTEM DESIGN

ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms, Clean Coding),

latest interview questions sorted by companies,

mock interviews.

Get hired from G, U, FB, Amazon, LinkedIn, Yahoo and other top-tier companies after weeks of training.

Email us aonecoding@gmail.com with any questions. Thanks!

- aonecoding4 November 28, 2018