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 n^{th} 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(); ... }

Wow this is a great resource.. I’m enjoying it.. good article

Comment by CNA Training — January 11, 2011 @ 10:12 pm

Thanks for liking the article

Comment by asimmunawar — January 12, 2011 @ 2:12 pm

I know you probably have to disagree, but if you can’t beat them, join them.

Comment by maria andros — January 25, 2011 @ 9:35 pm

Hello my friend! I wish to say that this article is awesome, nice written and include approximately all important infos. I would like to see more posts like this .

Comment by Airplane Games — June 6, 2011 @ 12:55 am