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

- Anonymous April 24, 2014 | Flag Reply
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?

- Adit May 23, 2014 | Flag Reply
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;
}

- Danish Shaikh February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 13, 2014 | Flag
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;

- Raj February 15, 2014 | Flag
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;
    }

- Anonymous February 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi, what does WAP stand for? Thanks

- cockroach February 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

write a program?

- Anonymous February 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

cool

- cockroach February 13, 2014 | Flag Reply
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];
	}

- Vulkum February 15, 2014 | Flag Reply
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 ..?

- Arun April 23, 2014 | 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