## 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?

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.

```
static private long GetNumberOfCombinations( int n ) {
if ( n <= 0 ) return 0;
long[] seq = { 1, 5, 11 }; // initial items of the sequence, they cannot be calculated, they are obtained empirically.
if ( n < seq.Length + 1 ) {
return seq[ n - 1 ];
}
for ( int i = seq.Length; i < n; i++ ) {
var res = seq[ 2 ] + 4 * seq[ 1 ] + 2 * seq[ 0 ];
seq[ 0 ] = seq[ 1 ];
seq[ 1 ] = seq[ 2 ];
seq[ 2 ] = res;
}
return seq[ 2 ];
}
```

```
/* 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.

I think it is 3N + 4(N-1) = 7*N-4

- siva.sai.2020 November 17, 2015