Uber | OA Coding Questions and Solutions | Set - 16 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

Images Of Ques

 

Answer 2

Updated my solution here. My previous O(n) solution requires the use of BigInteger, which will not be doable for many languages.


First thing, we observe that
k=1: [1, 2, 3, 4, 5] = 1C0, 2C1, 3C2, 4C3, 5C4
k=2: [1, 3, 6, 10, 15] = 2C0, 3C1, 4C2, 5C3, 6C4
k=3: [1, 4, 10, 20, 35] = 3C0, 4C1, 5C2, 6C3, 7C4


Did you see that pattern?
Our goal is to calculate the sum of (x+k)Cx where 0 <= x <= n-1

• What is nCr? nCr = n!/r!/(n-r)!

so we can just write this O(n+k) solution with the help of mod inverse.


   private static long solveSmart(int[] A, int k){
        ++k;
        int n = A.length;
        long[] inv = new long[n+k];
        long[] invf= new long[n+k];
        long[] fact= new long[n+k];
        fact[0]=fact[1]=inv[1]=invf[1]=invf[0]=1;
        for (int i = 2 ; i < n+k; i++){
            inv[i]=M-M/i*inv[M%i]%M;
            invf[i]=invf[i-1]*inv[i]%M;
            fact[i]=fact[i-1]*i%M;
        }
        long ans = 0;
        for (int i = 0; i < n; i++){
            ans = (ans + fact[i+k]*invf[i]%M*invf[k]%M)%M;
        }
        return ans;
    }



Here is the benchmark


n = 53607, k = 71789
smart O(n+k): total time taken = 14 ms
naive O(n*k): total time taken = 23524 ms

n = 91366, k = 93929
smart O(n+k): total time taken = 10 ms
naive O(n*k): total time taken = 52764 ms

n = 95464, k = 71555
smart O(n+k): total time taken = 9 ms
naive O(n*k): total time taken = 42117 ms

n = 72726, k = 70765
smart O(n+k): total time taken = 7 ms
naive O(n*k): total time taken = 31727 ms

n = 28557, k = 2818
smart O(n+k): total time taken = 2 ms
naive O(n*k): total time taken = 500 ms

n = 67848, k = 21444
smart O(n+k): total time taken = 4 ms
naive O(n*k): total time taken = 8964 ms

n = 29180, k = 13944
smart O(n+k): total time taken = 4 ms
naive O(n*k): total time taken = 2518 ms

n = 51710, k = 1471
smart O(n+k): total time taken = 2 ms
naive O(n*k): total time taken = 472 ms

n = 78535, k = 9045
smart O(n+k): total time taken = 5 ms
naive O(n*k): total time taken = 4388 ms

n = 49957, k = 29166
smart O(n+k): total time taken = 3 ms
naive O(n*k): total time taken = 8963 ms



And here is the naive O(nk) code:


    private static long solveNaive(int[] A, int k){
        int n = A.length;
        long ans = 0;
        for (int i = 0; i < k; i++){
            for (int j = 0, sum=0; j < n; j++){
                sum = (sum + A[j])%M;
                A[j]=sum;
            }
        }
        for (int i = 0; i < n; i++){
            ans = (ans + A[i])%M;
        }
        return ans;
    }



Lastly, here is the test code:


   static int M = (int)1e9+7;
    public static void main(String[] args){
        Random random = new Random();
        for (int i = 0; i < 10; i++){
            int n = random.nextInt(100000)+1;
            int k = random.nextInt(100000);
            int[] arr = IntStream.rangeClosed(1, n).toArray();
            long a = System.currentTimeMillis();
            long smart = solveSmart(arr, k);
            long b = System.currentTimeMillis();
            long naive = solveNaive(arr, k);
            long c = System.currentTimeMillis();
            System.out.printf("n = %d, k = %d\n", n, k);
            System.out.printf("smart O(n+k): total time taken = %d ms\n", b-a);
            System.out.printf("naive O(n*k): total time taken = %d ms\n", c-b);
            System.out.println();
            if (smart != naive){
                throw new IllegalStateException("WHATTTTTTT");
            }
        }
    }



In summary, this problem is testing you about

1. Whether you can observe the pascal nCr pattern.

2. Whether you know how to compute that efficiently in O(n) or O(n+k) with either BigInteger or ModInverse.

Answer 3

We can definitely do this in O(n)... in 5 lines, Here is how:


Like many commenters have mentioned, this has to do with pascal's triangle. That's a big giveaway on what we should do. We are supposed to compute the pascal triangle coefficient for each index in O(1).


I wish I can include photos here but I can't, so please go look up a pascal triangle photo and notice that we have to compute the number diagonal line "/" in O(1). Supposed that we start at the last index, i.e. top right point of the "/", with the coefficient 1. Now, we want to find the next point in "/" in O(1). We do know how to do that because we know mCr = (m-1)C(r - 1) + (m - 1)Cr, and we know (m - 1)Cr already. The ratio of (m-1)C(r-1) : (m-1)Cr is r : m - r. so we can totally find out what mCr is. Note that r is actually k, and m - r starts at 1 and m is incrementing by 1 each time we go down an index.


With that observation, we can write the following (incorrect - overflown) pseudo code in Java


//        for (int i = n, j = 1; i >= 1; i--){
//            ans = (int)((ans + (1L * i * m) % MOD) % MOD);
//            m += (k * m / j++);
//        }



In order to fix the overflow issue, we can make use of the BigInteger class in Java, so now it becomes:


        int n = 512, k = 2388383, MOD = (int)1e9 + 7;
        BigInteger m = BigInteger.ONE;
        BigInteger M = BigInteger.valueOf((int)1e9 + 7);
        for (int i = n, j = 1; i >= 1; i--){
            ans = (ans + i * m.mod(M).longValue()) % MOD;
            m = m.add(BigInteger.valueOf(k).multiply(m).divide(BigInteger.valueOf(j++)));
        }



Here is some benchmark:


n = 512, k = 2388383
Fast O(n): Answer is = 352833986, total time spent = 5 ms
Naive O(nk): Answer is = 352833986, total time spent = 7524 ms


n = 9833, k = 928353
Fast O(n): Answer is = 122198449, total time spent = 367 ms
Naive O(nk): Answer is = 122198449, total time spent = 55641 ms



I hope it helps and let me know if anyone has any questions. It is a very math-heavy question for sure.

Answer 4

Python O(KN) solution... If someone knows O(N) solution if it exists pls do share
n=int(input("Enter no of terms\n"))
list=[0]*n
print("Enter Elements")
for i in range(0,n):
list[i]=int(input())
k=int(input("Enter no of times operation\n"))
while(k>0):
sum=0
for i in range(1,n):
list[i]+=list[i-1]
sum+=list[i]
k-=1
print(sum+list[0])

Answer 5

This should be possible in O(n)

 

Suppose there are 4 numbers in the array. For k = 1, the first number appears 4 times in the result. For k = 2, it appears 10 times. The pattern looks like 1,4,10,20,35...
This is tetrahedral number sequence, and the kth number is given by k(k + 1)(k + 2) / 3!.
The second number in the array follows a similar pattern, 1,3,6,10.... Here the kth number is given by k(k+1)(k+2)/2!. The generalized formula is given in this wiki page https://en.wikipedia.org/wiki/Tetrahedral_number.

 

So basically start from the last number, which will add 1 times into the sum. Lets call this value X1. So X2 can be given as X1 * (k ) / 1 (See formula above). And similarly you can calculate X3, X4,... each in constant time(let's ignore multiplication complexity).

 

At the same time, calculate the result as X1 * A[n - 1] + X2 * A[n - 2] and so on, this too in constant time. A is the array here. The modulo rules can be used to make sure the answer doesn't overflow.

 

Basically, this is the question you give when you hate the candidate from the bottom of your heart.