CareerCup

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

#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;
			}
		}
	}
}

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.

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

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.