Qumulo Interview Question
Member Technical StaffsCountry: United States
Interview Type: In-Person
Although DFS is the way to go, the solution can't be recursive. The reason is that the robot do not have a memory of the previous cell. Unlike a recursive function, that when exits to an upper level, and retains its previous value, the robot cannot do it. Instead, each time the robot advances to a new cell, the angles have to be pushed into a stack.
this is my solution, although I had the liberty to modify names of the robot function (without adding anything to the robot API).
class MazeWalker {
int mAngle;
std::stack<int> s;
Maze &mMaze;
public:
MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
}
void traverse(bool stopOnFlag);
private:
int left() { mAngle = (mAngle - 90) % 360; return 270; }
int forward() { mAngle = 0; return 0; }
int right() { mAngle = (mAngle + 90) % 360; return 90; }
int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
bool goLeft() {
}
};
#define MAZE_WALKER_MOVE(f) \
mMaze.turn(f); \
if (!mMaze.wall()) { \
s.push(mAngle); \
mMaze.move(); \
continue; \
}
void MazeWalker::traverse(bool stopOnFlag) {
bool stop = false;
int step = 1;
while (!stop) {
cout << "Current step: " << step++ << " ";
mMaze.printCurrentCell();
if (stopOnFlag && mMaze.isFlag())
{
cout << "Found flag: ";
mMaze.printCurrentCell();
cout << endl;
return;
}
if (mMaze.isBreadcrumb()) {
if (s.empty())
return;
int angle = s.top();
s.pop();
mMaze.turn(angle);
mMaze.move();
continue;
}
MAZE_WALKER_MOVE(left())
MAZE_WALKER_MOVE(right())
MAZE_WALKER_MOVE(right())
mMaze.putBreadcrumb();
}
};
/*
*
*/
int main(int argc, char** argv) {
Maze m(5);
m.init();
m.print();
MazeWalker mw(m);
mw.traverse(true);
return 0;
}
class MazeWalker {
int mAngle;
std::stack<int> s;
Maze &mMaze;
public:
MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
}
void traverse(bool stopOnFlag);
private:
int left() { mAngle = (mAngle - 90) % 360; return 270; }
int forward() { mAngle = 0; return 0; }
int right() { mAngle = (mAngle + 90) % 360; return 90; }
int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
bool goLeft() {
}
};
#define MAZE_WALKER_MOVE(f) \
mMaze.turn(f); \
if (!mMaze.wall()) { \
s.push(mAngle); \
mMaze.move(); \
continue; \
}
void MazeWalker::traverse(bool stopOnFlag) {
bool stop = false;
int step = 1;
while (!stop) {
cout << "Current step: " << step++ << " ";
mMaze.printCurrentCell();
if (stopOnFlag && mMaze.isFlag())
{
cout << "Found flag: ";
mMaze.printCurrentCell();
cout << endl;
return;
}
if (mMaze.isBreadcrumb()) {
if (s.empty())
return;
int angle = s.top();
s.pop();
mMaze.turn(angle);
mMaze.move();
continue;
}
MAZE_WALKER_MOVE(left())
MAZE_WALKER_MOVE(right())
MAZE_WALKER_MOVE(right())
mMaze.putBreadcrumb();
}
};
/*
*
*/
int main(int argc, char** argv) {
Maze m(5);
m.init();
m.print();
MazeWalker mw(m);
mw.traverse(true);
return 0;
}
I have solved it using non recursive DFS. The solution cannot be recursive. Unlike recursive function, where exiting the function retains its previous value, the robot cannot retain its previous value when going out of recursion. It must be told explicitly to turn in the opposite direction. So instead of recursion I used a stack for the angles of the robot.
class MazeWalker {
int mAngle;
std::stack<int> s;
Maze &mMaze;
public:
MazeWalker(Maze &maze): mAngle(0), mMaze(maze) {
}
void traverse(bool stopOnFlag);
private:
int left() { mAngle = (mAngle - 90) % 360; return 270; }
int forward() { mAngle = 0; return 0; }
int right() { mAngle = (mAngle + 90) % 360; return 90; }
int reverse(int angle) { mAngle = (360 - angle) % 360; return mAngle; }
bool goLeft() {
}
};
#define MAZE_WALKER_MOVE(f) \
mMaze.turn(f); \
if (!mMaze.wall()) { \
s.push(mAngle); \
mMaze.move(); \
continue; \
}
void MazeWalker::traverse(bool stopOnFlag) {
bool stop = false;
int step = 1;
while (!stop) {
cout << "Current step: " << step++ << " ";
mMaze.printCurrentCell();
if (stopOnFlag && mMaze.isFlag())
{
cout << "Found flag: ";
mMaze.printCurrentCell();
cout << endl;
return;
}
if (mMaze.isBreadcrumb()) {
if (s.empty())
return;
int angle = s.top();
s.pop();
mMaze.turn(angle);
mMaze.move();
continue;
}
MAZE_WALKER_MOVE(left())
MAZE_WALKER_MOVE(right())
MAZE_WALKER_MOVE(right())
mMaze.putBreadcrumb();
}
};
/*
*
*/
int main(int argc, char** argv) {
Maze m(5);
m.init();
m.print();
MazeWalker mw(m);
mw.traverse(true);
return 0;
}
- Sergei November 10, 2015