Amazon Interview Question for Software Engineer / Developers


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[0].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[2][];
                var A = matA.M;
                var B = matB.M;

                for (int i = 0; i < 2; i++)
                {
                    C[i] = new BigInteger[2];
                    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[1001];


        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[0][1]);
        }
    }
}

- chuzpa October 14, 2012 | Flag Reply
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! :-)

- mag March 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Dragon March 04, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Dragon March 04, 2012 | Flag
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.

- bytecode March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

use multithreading,to compute the results in parts.

- LK March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dr.Sai March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Dr.Sai March 02, 2012 | Flag
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...

- dabbcomputers March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

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

- silvermist March 02, 2012 | Flag
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[0] = 1;
		_solved[1] = 1;
		for(int i = 2; i <= max; ++i) {
			_solved[i] = _solved[i - 1] + _solved[i - 2];
		}
	}
	
	public int fib(int term) {
		return _solved[term];
	}
	
}

- smffap March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous August 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zaara March 03, 2012 | Flag Reply
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)

- pikachu March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Basic TMP question.

- Nandha March 06, 2012 | Flag Reply
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

- silvermist March 02, 2012 | Flag Reply
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

- silvermist March 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.


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