## Google Interview Question for SDE1s

• 0

Country: United States

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

E.g.
0, 1, 1,
0, 1, 1,
0, 0, 0,
--- Flip(0, 1)
1, 0, 0,
0, 0, 1,
0, 1, 0,
--- Flip(1, 1)
1, 1, 0,
1, 1, 0,
0, 0, 0,
--- Flip(2, 1)
1, 0, 0,
1, 0, 0,
1, 1, 1,
--- Flip(2, 0)
0, 0, 0,
0, 0, 0,
0, 0, 0,

Brute force:

``````#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

void Flip(vector<vector<bool>> &m, int r, int c)
{
for (int i = 0; i < m.size(); ++i) {
m[i][c] = !m[i][c];
}
for (int i = 0; i < m[r].size(); ++i) {
m[r][i] = !m[r][i];
}
m[r][c] = !m[r][c];
}

bool Zeroable(vector<vector<bool>> &m, unordered_set<string> &seen)
{
if (!m.empty() &&
!m[0].empty())
{
int zeros = 0;
string key;
for (auto &r : m) {
for (bool val : r) {
if (val == false) {
++zeros;
}
key += val;
}
}
if (zeros == m.size() * m[0].size()) {
return true;
}
if (seen.find(key) != seen.end()) {
return false;
}
seen.insert(key);
for (int r = 0; r < m.size(); ++r) {
for (int c = 0; c < m[r].size(); ++c) {
Flip(m, r, c);
if (Zeroable(m, seen)) {
return true;
}
Flip(m, r, c);
}
}
}
return false;
}

void Print(vector<vector<bool>> const &m)
{
for (auto &r : m) {
for (bool val : r) {
cout << val << ", ";
}
cout << "\n";
}
cout << "---\n";
}

int main()
{
srand(time(NULL));

int n = 3;
int m = 4;

while (true) {
vector<vector<bool>> matrix(m, vector<bool>(n));
for (int r = 0; r < matrix.size(); ++r) {
for (int c = 0; c < matrix[r].size(); ++c) {
matrix[r][c] = rand() % 2;
}
}
auto orig = matrix;
unordered_set<string> seen;
if (Zeroable(matrix, seen)) {
Print(orig);
}
}
}``````

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

For square matrix n.

For n,m matrix, where n<m, then n+1.

Draw a matrix of 0s, and iterate it on its diagonal- regardless of the matrix shape, and you will figure it out why.

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

does the field I click flip as well? The problem statement sais it's flipped twice = it's not flipped.

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

the only way I can think of is to start from a matrix of 0s
and click several random points
but I dont see clear patterns.

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

If x+y-1 is odd you can make any pattern with row/column flips.
Else
If the exor of all cells is 0 then this is a valid pattern
However if it is 1 then you cannot make that pattern
Label all cells in the grid with capital letters
ABC
DEF

Let the lower case letter be true if it was the center of a flip
a= true
111
100

Write the equation for each cell
A = a exor b exor c exor d
B = a exor b exor c exor e
C…

Exor all capital letters
Simplify
z exor z -> 0
0 exor z -> z

When you flip a row / column you change x+y-1 cells
If(x+y-1) is even then the exor of all bits will = 0
If(x+y-1) is odd then exor of A….. = exor a…. so that does not matter

If someone can write a better explanation please do. It took me a long time to figure this out and I want to move on. It seems like a induction proof would be good for this.

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

Generally not possible.
Only possible if size of matrix is either 1x n or n x 1 or 1 x 1,
And all values of matrix are same.

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.