Uber Interview Question for SDE1s


Country: India




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

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

- siva.sai.2020 November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- zr.roman November 18, 2015 | Flag
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[0];

- sameer November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

return F[1]

- sameer November 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- zr.roman November 18, 2015 | Flag
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?

- Dhruv November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

found the answer, see below

- zr.roman December 07, 2015 | Flag
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?

- zr.roman November 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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 ];
}

- zr.roman December 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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.

- kanon January 06, 2016 | Flag Reply
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
	{
		// 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;
	}
}

- tomahawk April 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- zr.roman April 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- PS May 07, 2016 | Flag Reply
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.

- Shivam Maharshi October 06, 2016 | Flag Reply
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.

- zr.roman November 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- zr.roman November 18, 2015 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More