## Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

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

There is a much better approach using fibonnacci matrices, you can compute the nth fibonnacci in O(log(n)) time, use cache also, for future requests.

Here is the complete C# code:

``````using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;

namespace BigFibonacci
{
class Program
{
public class Matrix_2x2 {
public BigInteger[][] M = null;

public Matrix_2x2(BigInteger[][] m)
{
if(m.Length != 2 || m.Length != 2) {
new Exception ("The matrix asigned should be of 2x2");
}

M = m;
}

public static Matrix_2x2 operator * (Matrix_2x2 matA, Matrix_2x2 matB)
{
var C = new BigInteger[];
var A = matA.M;
var B = matB.M;

for (int i = 0; i < 2; i++)
{
C[i] = new BigInteger;
for (int j = 0; j < 2; j++)
{
C[i][j] = 0;
for (int k = 0; k < 2; k++)
{
C[i][j] += A[i][k] * B[k][j];
}
}
}

return new Matrix_2x2(C);
}

}

public static readonly Matrix_2x2 Fib1 =
new Matrix_2x2(new[] {
new []{ new BigInteger(0), new BigInteger(1)},
new[]{new BigInteger(1), new BigInteger(1)}
}),
Fib0 =
new Matrix_2x2(new[] {
new []{ new BigInteger(0), new BigInteger(0)},
new[]{new BigInteger(0), new BigInteger(1)}
});

Matrix_2x2[] cache = new Matrix_2x2;

public Matrix_2x2 Fibonacci(int n)
{
if (n == 0)
{
return Fib0;
}

if(n == 1) {
return Fib1;
}

if(cache[n] != null){
return cache[n];
}

var fibHalf = Fibonacci(n / 2);
cache[n] = (n % 2 == 0) ? fibHalf * fibHalf : fibHalf * Fibonacci(n / 2 + 1);
return cache[n];
}

static void Main(string[] args)
{
var p = new Program();

var fib = p.Fibonacci(1000);
Console.WriteLine(fib.M);
}
}
}``````

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

Look for Compile-time recursion (C) / Template meta-programming (C++), that's what they are looking for! :-)

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

Hi,
I have read that template meta programming will work only if you know what inputs to the factorial are at compile time. However, what happens if you wanna find factorials dynamically at run - time?

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

Hi,
I have read that template meta programming will work only if you know what inputs to the factorial are at compile time. However, what happens if you wanna find factorials dynamically at run - time?

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

Not a map, a straight array can make it better, keep filling the entries, Memoization.

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

use multithreading,to compute the results in parts.

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

Hi amanKaraj you r almost there, we like JIT calculate only when needed and store .

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

Hi amanKaraj you r almost there, we do like JIT calculate only when asked for and store the result in an array.

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

precompute the result in a single term and save them then take constant time to fetch...

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

That's what I said... since the operation will be recursive, you'll be able to precompute a lot of the results.
You can store them... but what else can you do?
The interviewer made me think that my solution was incomplete

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

You are almost correct. Simple code here for Fibonacci .

``````fib(n) {
prev = 1
prev_prev = 1
for i = 2 to n do
prev = prev + prev_prev
prev_prev = prev - prev_prev
return prev
}``````

You will need to save only last two values to calculate the current value and can discard
all other values.

Reference: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, Stein

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

Since it's only 1000 at the most, we can cache all the values for maximum efficiency.

``````class Fib {

private int[] _solved;
Fib(int max) {
_solved = new int[max + 1];
_solved = 1;
_solved = 1;
for(int i = 2; i <= max; ++i) {
_solved[i] = _solved[i - 1] + _solved[i - 2];
}
}

public int fib(int term) {
return _solved[term];
}

}``````

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

Yep, you can use an array instead of a map. That solution will be blazing fast. Doesn't get much faster than that.

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

LOL! Using an int to store fib(1000).

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

may i know what the question really ask us to do?? :(

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

Maintain static variables to maintain whether an invocation of the function is the first invocation.If its the first invocation precompute the results upto 1000 (Which will take negligible delay on modern systems).After that every other invocation of function works in o(1)

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

Basic TMP question.

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

You are almost correct. Simple code here for Fibonacci here.

fib(n) {
prev = 1
prev_prev = 1
for i = 2 to n do
prev = prev + prev_prev
prev_prev = prev - prev_prev
return prev
}

You will need to save only last to values to calculate the current value and can discard
all other values.

Reference: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, Stein

Section: Dynamic programming

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

You are almost correct. Simple code here for Fibonacci .

``````fib(n) {
prev = 1
prev_prev = 1
for i = 2 to n do
prev = prev + prev_prev
prev_prev = prev - prev_prev
return prev
}``````

You will need to save only last to values to calculate the current value and can discard
all other values.

Reference: Introduction to Algorithms, 3rd Edition by Cormen, Leiserson, Rivest, Stein

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

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.