Asim’s Blog

January 3, 2011

Interview with Amazon

Filed under: Personal — Tags: , , , — asimmunawar @ 12:34 pm

I applied for a mid-career job at Amazon Japan. My interview went fine but I was not selected for some reason. The interview lasts for 45 minutes and they ask three simple but conceptual programming problems. Then they have around 10 minutes time for any questions that you might want to ask them. Here are the solutions of the problems that were asked during the interview:

1. Fibonacci Numbers:

Write a code that can returns nth member of  Fibonacci series. For those who don’t know, Fibonacci series start with 1 ,1 and next member is calculated by taking the sum of previous two members in the series. So it goes like: 1,1,2,3,5,8,13,21,34,55,….

Solution:

It a very easy problem and can be solved by recursion or simple looping. Given below are both the functions:

Recursive approach:

int fib(int n)
{
	if(n <=2)
		return 1;
	else
		return fib(n-1)+fib(n-2);
}

Looping:

int fib(int n)
{
	int i=0;
	int x=1,y=1,z;

	for(i=0;i<n-2;i++){
		z = x+y;
		x=y;
		y=z;
	}
	return z;
}

2. Random Numbers Generator

Given a function ” rand5()” that returns random integers from 1 to 5 with uniform probability. We have to make a function “rand7()” that produces integers between 1-7 with uniform probability.

Solution:

This was a very interesting question. I was confused in the beginning but then I sorted out the solution. The interviewer didn’t ask for the code, he asked me to explain my strategy for the solution. My solution to this problem would be as follows:

1. Convert rand5() to rand4(). rand4() will return integers 1-4 with uniform probability. rand4() is simply a rand5() function that ignores the value 5.

int rand4()
{
	do{
		r=rand5();
	}while(r==5);
	return r;
}

We need 3 bits to represent numbers from 1 to 7. Therefore, we will call rand4() function three times. If we get 1 or 2 we change it to “0” and if we get 3 or 4 we change it to “1”. In this way we will get three bits required to create the random numbers from 1 to 7. However, three bits can represent 8 integers from 0 to 7. We will simple ignore the case when we get 0,0,0. In this way we can get a uniform distribution of integers from 1-7.

3. Class Design:

Design a class for public garage system.

Solution:

This problem can have infinite solutions depending on the requirements of the customer. However, a garage class can look something like:

class Garage
{
//attributes
private:
   int numberOfGarages;
   float maxHeight;
   float maxWidth;
   float pricePerHour;
   ...
//methods
public:
   int carEnter();
   int carExit();
   int garageClose();
   ...
}

Create a free website or blog at WordPress.com.