## Interview Question

Country: United States
Interview Type: In-Person

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

The move* methods return a boolean indicating whether the person is moving inside the boundaries.
You can reach the top left corner and then start moving spirally towards the center.

``````#include <stdio.h>
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

typedef bool boolean;

struct Person
{
virtual boolean moveUp() = 0;
virtual boolean moveDown() = 0;
virtual boolean moveRight() = 0;
virtual boolean moveLeft() = 0;
virtual boolean found() = 0;
};

void findApple(Person *p)
{
//goto top left corner
while(p->moveLeft())
{
if(p->found())
return;
}

while(p->moveUp())
{
if(p->found())
return;
}

int Steps = 0;
bool CanMove = true;

while(CanMove)
{
while(p->moveRight())
{
if(p->found())
return;
}
for(int i = 0; i < Steps; ++i)
p->moveLeft();

while(p->moveDown())
{
if(p->found())
return;
}
for(int i = 0; i < Steps; ++i)
p->moveUp();

while(p->moveLeft())
{
if(p->found())
return;
}
for(int i = 0; i < Steps; ++i)
p->moveRight();

while(p->moveUp())
{
if(p->found())
return;
}
for(int i = 0; i < Steps; ++i)
p->moveDown();

Steps++;

//try to step on an inner track
if(!p->moveDown() || !p->moveDown())
{
//the spiral ended here
CanMove = false;
break;
}

p->moveUp();

if(!p->moveRight())
CanMove = false;

if(p->found())
return;

//check if it was the last cell
if(!p->moveRight() || !p->moveRight())
{
//the spiral ended here
CanMove = false;
break;
}

p->moveLeft();
p->moveLeft();

}

}

class PersonImpl : public Person
{
//Create a grid of 15x10
//+2 for marking the boundaries
#define Width 17
#define Height 12

int Cells[Height][Width];

int m_CurrentPosX;
int m_CurrentPosY;
public:
boolean moveUp()
{
if(m_CurrentPosY == 0)
return false;
if(Cells[m_CurrentPosY - 1][m_CurrentPosX] == -1)
return false;
m_CurrentPosY--;
//	printf("Moved Up x=%d y=%d \n", m_CurrentPosX, m_CurrentPosY);
Steps++;
return true;
}
boolean moveDown()
{
if(m_CurrentPosY == Height - 1)
return false;
if(Cells[m_CurrentPosY + 1][m_CurrentPosX] == -1)
return false;
m_CurrentPosY++;
//	printf("Moved Down x=%d y=%d \n", m_CurrentPosX, m_CurrentPosY);
Steps++;
return true;
}

boolean moveLeft()
{
if(m_CurrentPosX == 0)
return false;
if(Cells[m_CurrentPosY][m_CurrentPosX - 1] == -1)
return false;
m_CurrentPosX--;
//	printf("Moved Left x=%d y=%d \n", m_CurrentPosX, m_CurrentPosY);
Steps++;
return true;
}

boolean moveRight()
{
if(m_CurrentPosX == Width - 1)
return false;
if(Cells[m_CurrentPosY][m_CurrentPosX + 1] == -1)
return false;
m_CurrentPosX++;
//	printf("Moved Right x=%d y=%d \n", m_CurrentPosX, m_CurrentPosY);
Steps++;
return true;
}

boolean found()
{
if(Cells[m_CurrentPosY][m_CurrentPosX] == 1)
{
printf("Found apple at x=%d y=%d in %d steps", m_CurrentPosX, m_CurrentPosY, Steps);
return true;
}
return false;
}

PersonImpl()
{
//initialize the grid.
for(int y = 0; y < Height; ++y)
{
for(int x = 0; x < Width; ++x)
{
if(y == 0 || x == 0 || y == Height - 1 || x == Width - 1)
Cells[y][x] = -1; //boundary line
else
Cells[y][x] = 0; //normal cell
}
}

int AppleX = ( rand()%(Width - 2) ) + 1;
int AppleY = ( rand()%(Height - 2) ) + 1;

Cells[AppleY][AppleX] = 1; //apple's cell
printf("Apple is at x=%d y=%d \n", AppleX, AppleY);

do
{
m_CurrentPosX = ( rand()%(Width - 2) ) + 1;
m_CurrentPosY = ( rand()%(Height - 2) ) + 1;
} while (m_CurrentPosX == AppleX && m_CurrentPosY == AppleY);

printf("Person's initial pos x=%d y=%d \n", m_CurrentPosX, m_CurrentPosY);

Reset();
}

void Reset() { Steps = 0; }
private:

int Steps;
};

int main() {
// your code goes here
srand((unsigned int)time(NULL));

PersonImpl p;

findApple(&p);

return 0;
}``````

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

Since you don't know the exact location of the apple, then only option is to 'sweep' the whole grid until you eventually find it, trying to minimize the number of revisited cells.

1. Find 'boundaries' for Grid:

Try to build a "rectangle" on bottom-right area and sweep it
1a. keep going down while you find a boundary.
after reaching end mark length from your initial spot, new limit D.

1b. keep going right while you find a boundary.
after reaching end mark length from your D as new spot R.

1c. Now you have a rectangle base on your known boundaries from your original spot.

1d. sweep inside of rectangle getting your way back to your initial position.

After sweeping bottom-right do the same process to sweep upper-right, then upper-left and finally bottom-left.

on any of these if you find apple stop.

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

Well ... looks likes the question says the boundaries are unknown and also we do not have methods to find if we have reached the edge of the grid, which means for all practical purposes we can assume the grid to be infinite.

Now lets look at how the person can reach the apple. The only way I can think of is if he starts moving by covering the immediate cells around him and then go to the next immediate cells. Since this is an rectangular grid it makes sense to cover all the cells around the cell the person is in, then move to the outer cells forming another square and so on spiraling out until he gets the apple, that is a TRUE is returned for the found( ) method for each move.

so if,
R = moveRight( )
L = moveLeft( )
U = moveUp( )
D = moveDown( )
and F = found( )

To search for the immediate cells that form the first square should look like something like this,
R D LL UU RR
Then moving on to the next outer square
R DDD LLLL UUUU RRRR
then the next outer square
R DDDDD LLLLLL UUUUUU RRRRRR
so on ...

So the program would look something like

``````while(!found())
{
int d = 1; // initializing the number of down movements to 1
int lur = 2; /// initializing the number of left up and right movements to 2

moveRight(); // Moving to the outer square
if(found())
break;
for(int i=0; i<d ;i+=) // moving along the right edge of the square
{
moveDown();
if(found())
break;
}
if(found())
break;
for(int i=0; i<lur ;i+=) // moving along the bottom edge of the square
{
moveLeft();
if(found())
break;
}
if(found())
break;
for(int i=0; i<lur ;i+=)
{
moveUp();  // moving along the left edge of the square
if(found())
break;
}
if(found())
break;
for(int i=0; i<lur ;i+=)
{
moveDown();  // moving along the top edge of the square
if(found())
break;
}
if(found())
break;

d += 2;
lur += 2;
}``````

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

Start from the cell where it isin.
Right() and top().
Complete one cycle, repeat until it finds .

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.