## 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 5 vote

f(1) = 1
f(2) = 2
f(3) = 4
f(4) = 8
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4), n > 4
In matrix form:
f(n) 1 1 1 1 f(n-1)
f(n-1) 1 0 0 0 f(n-2)
f(n-2) = 0 1 0 0 * f(n-3)
f(n-3) 0 0 1 0 f(n-4)
while matrix multiplication could be done with O(logN).

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

I really like your idea. Here's the C++ implementation:

int tower(int n)
{
if (n <= 0)
return 0;

switch (n) {
case 1:     return 1;
case 2:     return 2;
case 3:     return 4;
case 4:     return 8;
default:    break;
}

n -= 4;

queue<int> Q;
Q.push(1);
Q.push(2);
Q.push(4);
Q.push(8);

int f = 1 + 2 + 4 + 8;
while (--n) {
Q.push(f);
f = 2 * f -  Q.front();
Q.pop();
}

return f;

}

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

In the expression f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4), how do we make sure that there are no overlapping sets between f(n-1) branch and f(n-2) branch and other branches. I think we will have overlapping sets. Just consider this scenario
In f(n-1), we have already selected a disk of height 1, now we select one disk of height 2 and all the remaining disks of height 1. We will effectively have one disk of height 2 and n-2 disks of height 1.
And in f(n-2), we have already selected a disk of height 2, and for remaining n-2 height we can select n-2 disks of height 1, so again we will end up with one disk of height 2 and n-2 disks of height 1.

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

I like your approach.

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

Could someone please explain the logic behind uuuouou's approach?

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

Study fibonacci series.

Naive approach is straight recursion -> exponential runtime.
Improve this with DP down to linear.

But every DP solution also has a matrix multiplication method which is below linear (usually not expected in interview because you can't really code it conveniently in the languages we use in interviews).

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

I think I know what Fibonacci series is -- usually there is no "logic" behind the Fibonacci series, we are given what the series is and expected to code that using DP.

What I was asking is how someone might come up with the equation
f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4), n > 4

I know how to prove the equation -- I was curious about the thought process of coming up with that equation.

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

Do you know coin change problem ? The version where you have to return total number of ways to make change for some cost n.

Assume the coins are 1, 2, 3, 4.

It becomes this problem.

number of ways to make change for N is
= number of ways to use $1 and make change for remaining N-1 OR number of ways to use$2 and make change for remaining N-2

...

etc.

Now you get recursive, then you use DP as optimization.

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

Aha!

So the number of ways we can construct a tower of height n (let's call it f(n)) is the sum of different ways we can construct a tower of height NOT using a particular brick of height h \in {1,2,3,4}: f(n) = \sum_{i=1}^{4} f(n-i).

Thanks!

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.