Uber Interview Question
SDE1sCountry: 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