Interview Question
Country: United States
Interview Type: In-Person
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.
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;
}
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.
- 316brc March 12, 2015