## Google Interview Question for Software Engineers

Country: United States
Interview Type: In-Person

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

``````#define LEFT 	0
#define RIGHT 	1
#define TOP 	2
#define BOTTOM	3

struct coord {
int i, j;

};

void canMove(coord &next, vector<vector<int> > a, int i, int j) {
next.i = -1;
// out of boundaries
if (i < 0 || i >= a.size() || j < 0 || j >= a.size()) {
return;
}
// not the first or last square
if ((i = 0 && j == 0) || (i == a.size()-1 && j == a.size()-1)) {
return;
}
// if that cell is already taken
if (a[i][j] == 1) {
return;
}
// can't put the wall here, neighboor
if (a[i][j] == -1) {
return;
}
next.i = i;
next.j = i;
}

int selectNextMove(array<coord, 4> next) {
int startIndex = rand() % 4;
int index = startIndex;
for (;;) {
if (next[index].i != -1) {
return index;
}
index++;
if (index == startIndex) {
break;
}
if (index == 4) {
index = 0;
}
}
}

void buildMaze(vector<vector<int> > a) {
size_t i, j;

for (i = 0; i < a.size(); i++) {
for (j = 0; j < a.size(); j++) {
a[i][j] = 0;
}
}

array<coord, 4> next;
for (;;) {
canMove(next[LEFT], a, i, j-1);
canMove(next[RIGHT], a, i, j+1);
canMove(next[TOP], a, i-1, j);
canMove(next[BOTTOM], a, i+1, j);

int nextMove = selectNextMove(next);
if (nextMove == -1) { // can't move anywhere, break
break;
}
i = next[nextMove].i;
j = next[nextMove].j;
for (int dir=0; dir<4; dir++) {
if (next[dir].i != -1 && nextMove != dir) {
a[next[dir].i][next[dir].j] = -1;
}
}
}

// cleaning
for (i = 0; i < a.size(); i++) {
for (j = 0; j < a.size(); j++) {
if (a[i][j] == -1) {
a[i][j] = 0;
}
}
}
}``````

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

Does this really make a maze? What does it look like?

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

``````#define LEFT 	0
#define RIGHT 	1
#define UP 	2
#define DOWN	3

#define TEMP_WALL -1
#define MAZE_WALL 1
#define MAZE_PATH 0

struct CellCoordinates {
size_t i;
size_t j;
void set(vector<vector<int> > a, int setI, int setJ) {
// out of boundaries
// if that cell os a path or a permanent wall
if (setI < 0 || setI >= a.size() || setJ < 0 || setJ >= a.size() ||
a[setI][setJ] != TEMP_WALL) {
this->i = -1;
this->j = -1;
} else {
this->i = setI;
this->j = setJ;
}
};
};
#define is_cell_valid(c) (c.i != -1)

int prepareCells(CellCoordinates cells[], vector<vector<int> > a, size_t startI, size_t startJ) {
// cells around the cell, set also veryfies if the path can be put through the cell
cells[LEFT].set(a, startI, startJ-1);
cells[RIGHT].set(a, startI, startJ+1);
cells[UP].set(a, startI-1, startJ);
cells[DOWN].set(a, startI+1, startJ);

// select the "main" path randomly
int startIndex = rand() % 4;
int index = startIndex;
for (;;) {
if (is_cell_valid(cells[index])) {
return index;
}
index++;
if (index == startIndex) {
return -1;
}
if (index == 4) {
index = 0;
}
}
}

// in this functions the path in the mase will be built
// first we create a maze with temporary walls;
// then we will create a random path, surraunded with permanent walls
// then we replace the permanent walls with temporary ones
bool buildMazePath(vector<vector<int> > a) {
size_t i, j;

// init maze
for (i = 0; i < a.size(); i++) {
for (j = 0; j < a.size(); j++) {
a[i][j] = TEMP_WALL;
}
}

//entry and exist cells
a = MAZE_PATH;
a[a.size()-1][a.size()-1] = MAZE_PATH;

i = j = 0;
for(;;) {
CellCoordinates cells;
// find valid (not a perm wall or a path) cells, neighbors; chose random direction
int index = prepareCells(cells, a, i, j);
if (index == -1) { // can't move anywhere
return false;
}

for (size_t k=0; k < 4; k++) {
if (k == index) {
// set path
a[cells[k].i][cells[k].j] = MAZE_PATH;
} else if (is_cell_valid(cells[k])) {
// for all other valid cells, set walls
a[cells[k].i][cells[k].j] = MAZE_WALL;
}
}
i = cells[index].i;
j = cells[index].j;
if ((i == a.size()-2 && j == a.size()-1) ||
(i == a.size()-1 && j == a.size()-2)) {
break;
} // cells neighboring the exit cell
}

// prepare for the next step - set the temp walls for all the cells that are not path
for (size_t i = 0; i < a.size(); i++) {
for (size_t j = 0; j < a.size(); j++) {
if (a[i][j] == MAZE_WALL) {
a[i][j] = TEMP_WALL;
}
}
}
// we have a matric with 0s as a path and temporary walls
return true;
}

// The rest of the matrix is filled up with no-outlet paths and permanent walls
void buildMazeRest(vector<vector<int> > a, size_t startI, size_t startJ) {
CellCoordinates cells;
int index = prepareCells(cells, a, startI, startJ);
if (index == -1) { // can't move anywhere
return;
}

// for all valid cells build "no-outlet paths"
for (size_t k=0; k < 4; k++) {
if (is_cell_valid(cells[k]) && a[cells[k].i][cells[k].j] == TEMP_WALL) {
// put a wall, randomly
if (rand() % 5 == 1) {
a[cells[k].i][cells[k].j] = MAZE_WALL;
} else {
a[cells[k].i][cells[k].j] = MAZE_PATH;
buildMazeRest(a, cells[k].i, cells[k].j);
}
}
}
}

void buildMaze(vector<vector<int> > a) {
if (a.size() < 2 || a.size() < 2) {
return;
}

assert(buildMazePath(a));
buildMazeRest(a, 0, 0);

// cleaning, set the permanent walls everywhere where there are temporaty walls left
for (size_t i = 0; i < a.size(); i++) {
for (size_t j = 0; j < a.size(); j++) {
if (a[i][j] == TEMP_WALL) {
a[i][j] = MAZE_WALL;
}
}
}
}``````

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

I believe this question is related to the Minimum Spanning Tree using Prim's algorithm for maze creation

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

What is meant by create a maze? Draw a maze with a paper and a pencil or design a program to generate a maze? If we were writing a program did they want us to generate a data structure that represents a maze? Did they want it printed to the screen?

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

The question was "create a maze". I do not agree that is a good question for 45 minutes. It requires figuring out what did the person mean - most likely s(he) had some idea in mind - one path, many paths, how many dead ends. Come to think about it, drawing the line in the 2 dimentional array from (0,Y/2) -> (X, Y/2) is a solution.

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

Anything. Come to think about it is can be a line from (0,Y/2) -> (X-1, Y/2).

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

Anything. Come to think about it - it can be a line: (0,y/2) -> (x-1, y/2). What is the maze: "a network of paths and hedges designed as a puzzle through which one has to find a way." A line is a path.

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.