Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
#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[0].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[0].size(); j++) {
a[i][j] = TEMP_WALL;
}
}
//entry and exist cells
a[0][0] = MAZE_PATH;
a[a.size()-1][a[0].size()-1] = MAZE_PATH;
i = j = 0;
for(;;) {
CellCoordinates cells[4];
// 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[0].size()-1) ||
(i == a.size()-1 && j == a[0].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[0].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[4];
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[0].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[0].size(); j++) {
if (a[i][j] == TEMP_WALL) {
a[i][j] = MAZE_WALL;
}
}
}
}
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?
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.
- marinalepi March 06, 2015