## Uber Interview Question for SDE1s

Country: India

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

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 ];
}``````

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

Actually it's A005178 from oeis.org.
The formula is
F(0) = 1, F(1) = 1, F(2) = 5, F(3) = 11 and
F(n) = F(n-1) + 5F(n-2) + F(n-3) - F(n-4) for n>3.
In particular, F(4) is 36, not 33.

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

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

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

no, it is incorrect.
for n = 2 it gives 10, but it should be 5.
Also, for n = 3 it gives 17, but it should be 11.
(where n is that from 4*n).

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

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;``````

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

return F

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

it does not work.
for n = 2 it gives 4, but it should be 5.
Also, for n = 3 it gives 8, but it should be 11.
(where n is that from 4*n).

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

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

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

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

No, it is something different.
By empirical way I discovered the following first answers:
n = 1, answer = 1.
n = 2, answer = 5.
n = 3, answer = 11.
n = 4, answer = 33.
So, what rule could it be?

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

``````/* 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
{
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;
}
}``````

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

for @kanon
looks like, you are wrong.
Here I draw all the 33 variants for F(4). Look.
If I missed something, please, let me know.

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

This is the same problem as problem code 'GNY07H' on SPOJ.

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

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.

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

this is a Fibonacci sequence task,
the answer is 34 if n = 4.
For the other values of n, we should take the respective value from Fibonacci sequence.

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

some correction: we take Fibonacci sequence as base, but we cannot use it as is, we should use some coefficient.
Below I provide the solution.

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.