## Google Interview Question for SDE-2s

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

+ with 3x3 grid, we got 9 spots. Each can be black/white ( 1/0) , making total 2^9 = 512 states
+ Just do BFS with a Queue and keep track of visited states.
+ Increment steps at every BFS iteration and when reaching destination ( all 0s ) return steps.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

int getMinFlips(int grid, int flips[9], int i)
{
if (grid == 0b111111111) return 0;
if (i == 9) return -1;

int ret;
ret = getMinFlips(grid ^ flips[i], flips, i + 1);
if (ret > -1) {
return ret + 1;
}
return getMinFlips(grid, flips, i + 1);
}
int getMinFlips(int grid)
{
int flips[] = {
0b110100000,
0b111010000,
0b011001000,
0b100110100,
0b010111010,
0b001011001,
0b000100110,
0b000010111,
};
return getMinFlips(grid, flips, 0);
}
int main()
{
cout << getMinFlips(0b101000101) << endl;
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel like this can be solved with Dynamic programming. If you store all 2^9 combinations in a table, you can start with the one given and start visiting the other potential positions until you hit the all white configeration. This should only take O(2^9). Alternatively this can be thought of as Djkstra's algorithm.

Comment hidden because of low score. Click to expand.
0

bfs would be ok!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple BFS with bitmask will work here. Let 1 represents black and 0 represents white.
We need to reach the state (0,0,0) all white from given state (x,y,z).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.