Amazon Interview Question for Software Engineer in Tests

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

Surprisingly no one wrote the test cases which is an important part of this question. Algorithm is commonly available everywhere.

Test 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?

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

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.)

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Iterative code is wrong, when the n is 0 or 1, you got wrong output
it should be :
c = a+b;
a = b;
b= c;

then return b;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi, what does WAP stand for? Thanks

Comment hidden because of low score. Click to expand.
0

write a program?

Comment hidden because of low score. Click to expand.
0
of 0 vote

cool

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

First example how you will instantiate same variable in same method two times ..?

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.

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.