## Amazon Interview Question for Web Developers

Country: United States

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

The most efficient way is iterative, only keeping the last two numbers in the sequence.

``````def getNthFibonacci(i):
prev1 = 1
prev2 = 1

if i == 1:
return prev1
if i == 2:
return prev2

for _ in range(i - 2):
current = prev1 + prev2

# Push prev2 back to prev1, and add our latest one to the
# end of the 'sequence'.
prev2 = prev1
prev1 = current

return prev1``````

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

This method still takes linear time. There are faster methods that take logarithmic time.

See geeksforgeeks .org/program-for-nth-fibonacci-number/ methods 4 and 5

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

Better still: stackoverflow .com/questions/1525521/nth-fibonacci-number-in-sublinear-time

``f(n) = floor(phi^n / sqrt(5) + 1/2)``

where phi represents the golden ratio.

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

Because it's still O(log n) but only 2 lines of code?

I don't see the benefit of implementing the matrix solution when you can just do it this way.

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

@jay: Perhaps looking at the downsides of using floating point computation will help you?

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

@jay, look at yairchu explanation on stackoverflow

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

@jay, In Python you can use tuple assignment to make this a little more concise:

``prev1, prev2 = (prev2+prev1, prev1)``

Also, there is an O(log N) solution that uses only integer arithmetic. See "Python O(logN) version. "

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

exponentiation phi^n can be computed in O(logn), so I think the approach by @jay is still sub-linear

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

long fiboo(long int n )
{
long int pre1=0,pre2=1;
if(n==1)
return 0;
if(n==1)
return 1;

for(long int i=2;i<=n;i++)
{
long int temp=pre2
pre2=pre2+pre1;
pre1=temp;
}

return pre2;
}

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

better not to use recursive method , it will take a long time !
my solution resembles the above two but it has a plus point that,, for multiple inputs at the same time u just have to print those array elements;

``````int main()
{	long int a[1000000];
long int n;
a[0]=0;
a[1]=1;
for(i=2;i<;1000000;i++)
{	a[i]=a[i-1]+a[i-2];
}
cin>>n; //the number of which fib is required;
cout<<a[n];
return 0;
}``````

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

Yes, the O(lgn) is the best answer. the matrix is [1 1 ]
[1 0]

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

Can you try the 2x2 Matrix Multiplication code of Fibonnaci Series.
Its O(Log n)

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

There is a closed form expression for the n-th Fibonacci number.

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

Just iterate! time complexity is O(n). It is as simple as this:

``````long getNthFibonacci(long i){
long n=1;
long numN=1;
long numNLess1=0;
long temp;
while (i!=n){
n++;
temp=numN+numNLess1;
numNLess1=numN;
numN=temp;
}
return numN;
}``````

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

Python O(logN) version.

This uses some recursive properties of the Fibonacci numbers to compute an individual number in logN time. It's the most efficient solution that I know of that doesn't use floats. It's all integer multiplication and addition.

``````def fib(n):
if n == 0:
return 0
return fib2(n)[1]

def fib2(n):
# returns (fib(n-1), fib(n)
if n < 5:
return tuple([0,1,1,2,3,5][n-1:n+1])
x, y = fib2(n / 2)
a = x*x + y*y
b = (2*x+y)*y
if n % 2 == 1:
a, b = (b, a+b)
return (a, b)

for i in range(20):
print fib(i)``````

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

f(nth) = floor((1+sqrt(5))/2)^n / sqrt(5) +0.5)

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

(1 1) pow n=( fibo(n+1) fibo(n) )
(1 0) ( fibo(n) fibo(n-1) )
These are 2X2 matrices. This s the most efficient way to find fibonacci nos.

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

f(nth) = floor((1+sqrt(5))/2)^n / sqrt(5) +0.5)

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

Here is the problem written in Ruby:

``````def fib(nth)
fib1 = 1
fib2 = 1
counter = 2
fibonacci = [fib1, fib2]
until counter == nth do
fibonacci << fib = fib1 + fib2
fib1=fib2
fib2=fib
counter += 1
end
fibonacci
end

print fib(4)``````

- Alex M.

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

Use DP

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.