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

- 316brc March 12, 2015 | Flag Reply
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.

- guilhebl March 11, 2015 | Flag Reply
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;
}

- pm March 11, 2015 | Flag Reply
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 .

- bvmr@outlook.com March 30, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More