Google Interview Question
SDE-2sCountry: United States
#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;
}
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.
+ with 3x3 grid, we got 9 spots. Each can be black/white ( 1/0) , making total 2^9 = 512 states
- Code reviewer April 25, 2019+ 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.