Amazon Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
We can avoid the repeated work done is the recursion by storing the Fibonacci numbers calculated so far.
This is a dynamic programming approach
#include<stdio.h>
int fib(int n)
{
/* Declare an array to store fibonacci numbers. */
int f[n+1];
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}
//Recursion
public int fibonacci(int n)
{
if(n<=1) return 1;
int n=fibonacci(n-1)+fibonacci(n-2);
return n;
}
//Itterative code
public int fibo(int n)
{int a=1,b=1;
for(int i=2;i<=n;i++)
{
int c =a+b;
b=a;
a=c;
}
return c;
}
In your recursive code the if condition should be {if(n==0) return 0; if(n==1) return 1;}
Your code will allow fibonacci to be calculated for any number lesser than 1 (-2, -5, etc.)
/**
* Recursive O(n) method to calculate Fibonacci numbers
* @pre n >= 1
* @param fibCurrent The current Fibonacci number
* @param fibPrevious The previous Fibonacci number
* @param n The count of Fibonacci numbers left to calculate
* @return The value of the Fibonacci number calculated so far
*/
private static int fibo(int fibCurrent, int fibPrevious, int n) {
if (n == 1) {
return fibCurrent;
} else {
return fibo(fibCurrent + fibPrevious, fibCurrent, n - 1);
}
}
/**
* Wrapper method for calculating Fibonacci numbers
* @pre n >= 1
* @param n The position of the desired Fibonacci number
* @return The value of the nth Fibonacci number
*/
public static int fibonacciStart(int n) {
if (n <= 0)
{
throw new IllegalArgumentException();
}
return fibo(1, 0, n);
}
public static int fibonacciIterative(int n)
{
int a = 1;
int b = 1;
int c = 0;
for (int i = 2; i < n; i++) //i < n, not i <= n
{
c = a+b;
b = a;
a = c;
}
return c;
}
I think it would be better if you used dynamic programming for the recursive version. This kind of question is the kind of question where I believe they look at this optimization thingy, as the problem is otherwise quite simple:
int[] fib = new int[n];
int fibonacci(int i){
if(i==0) return 0;
if(i==1) return 1;
if(fib[i]!=0) return fib[i]; //you have to do this assuming you have all ints=0;
//otherwise cache the result and replace the '0' with a fib value
fib[i]= fibonacci(i-1) + fibonacci(i-2);
return fib[i];
}
Surprisingly no one wrote the test cases which is an important part of this question. Algorithm is commonly available everywhere.
- Adit May 23, 2014Test cases:
n=-1
n=0
n=1
n=2
n=max int
Check for memory available and check if recursive solution is acceptable
What happens when the system runs out of memory
Check for performance on the designated device. Do we need dynamic programming because it is super slow?