## Uber Interview Question

SDE1s**Country:**India

F(i) = F(i + 1) + 4 * F(i + 2)

```
F[N] = 1
F[N - 1] = 4
for (i = N - 2 ; i >= 0; --i) {
F[i] = F[i + 1] + 4 * F[i + 2];
}
return F[0];
```

@zr.roman How did you figure out that the answer will be found from the fibnacci sequence?

According to your solution, the answer for 4*1 block is 3, but shouldn't it be 1?

```
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
System.out.println(new Codechef().getNoWays(29));
}
public int getNoWays(int length){
return getNoWays(length, false);
}
private Map<Integer, Integer> cache = new HashMap();
private int getNoWays(int length, boolean isLowerOccupied ){
if(cache.containsKey(length))
return cache.get(length);
if(length == 0 || length == 1){
cache.put(length, 1);
return 1;
}
int noWays = 0;
if(isLowerOccupied){
noWays = getNoWays(length-2, false);
}
else{
noWays = getNoWays(length-1, false) + getNoWays(length, true);
System.out.println("Evaluated for " + length + " - " + noWays);
cache.put(length, noWays);
}
return noWays;
}
}
```

This is how the recursive function will look like:

f(n) = f(n-2) + f(n-1) + 6;

When we cut one block of width 1, then there is only one way to fill it using 2*1 blocks. i.e two of 1*2 vertical block one above the other.

When we cut one block of width 2, then there are 5 ways to fill it using 2*1 blocks. Shown below.

a. All 2*1 blocks lying horizontally on top of each other.

b. Two 2*1 blocks lying horizontally and 2 on top of them vertically.

c. Vice Versa of above case.

d. One 2*1 block lying horizontally then 2 on top of it vertically and then another one on top of them horizontally.

e. 2*1 blocks all standing vertically.

Hence at any point we can either choose to reduce width by 1 block (1 way) or by 2 blocks (5 way) giving:

f(n) = f(n-1) + 1 + f(n-2) + 5 = f(n-1) + f(n-2) + 6.

Solve it using DP now.

looks like this is A127864 or A077917 from oeis.org

According to this reference, the formula is:

F(i) = F(i-1) + 4 * F(i-2) + 2 * F(i-3).

c# implementation.

- zr.roman December 07, 2015