Uber | OA Coding Questions and Solutions | Set - 28 | 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

Minimum number of additions to make array sorted (worded as adding blocks to towers)

 

EX:

 

arr = [1, 4, 3, 2]
result = 4 (Add 4 to the first item)	
	
arr = [2, 3, 2, 3]
result = 4 (Add 2 to the last 2 items)

	
arr = [5, 7, 9, 4, 11]
result = 9 (add 2 to 5, add 1 to 7, 6 to 4)

Answer 2

Java code:

 

private static long solution(int[] arr)
{
    long asc = 0L, desc = 0L;
    int max = -1;
    for(int i : arr)
    {
        if(i <= max)
        {
            asc += (max-i+1);
            max++;
        }
        max = Math.max(max,i);
    }
    max = -1;
    for(int i = arr.length-1; i >= 0; i--)
    {
        if(arr[i] <= max)
        {
            desc += (max-arr[i]+1);
            max ++;
        }
        max = Math.max(max,arr[i]);
    }
    return Math.min(asc,desc);
}

Answer 3

TC : O(N), Space : O(1)

 

Approach: Find the maxima (element + index (0 based)) in forward as well as backward traversal. This maxima serves as the peak element in the final array. The sum of the final array will be maxima+(maxima-1)+(maxima-2)....+(maxima-N+1). What we require is the cost of conversion which is easily obtained by subtracting the initial sum from the final sum.

 

public class Main
{
    public static void main(String[] args)
    {
        System.out.println(solution(new int[]{1, 4, 3, 2})); // --> 4
        System.out.println(solution(new int[]{2, 3, 2, 3})); // --> 4
        System.out.println(solution(new int[]{5, 7, 9, 4, 11})); // --> 9
        System.out.println(solution(new int[]{7,2,3,6,5,4,1})); // --> 14
    }
    private static long solution(int[] ar)
    {
        long sum = 0L, asc = 0L, desc = 0L, max = 0L;
        int N = ar.length;
        
        for(int i = 0; i < N; sum += ar[i++])
            max = Math.max(max,ar[i]+i);
        desc = sum_range(max-N,max)- sum;
        
        max = 0L;
        for(int i = 0; i < N; i++)
            max = Math.max(max,ar[i]+N-i-1);
        asc = sum_range(max-N,max)- sum;
        
        return Math.min(asc,desc);
    }
    private static long sum_range(long a, long b) // Sum of numbers in range a,b
    {
        return 1L*(b*(b+1)/2 - a*(a+1)/2);
    }
}

Answer 4

TC - O(n)

SC - O(1)

arr = [int(i) for i in input().split()]

def func(arr):
    cur = 0
    max_ele = max(arr)
    max_ele_ind = arr.index(max_ele)
    j = max_ele_ind + 1
    i = max_ele_ind - 1
    v = 1
    while i >= 0:
        cur += (max_ele - arr[i] - v)
        v += 1
        i -= 1
    v = 1 
    while j < len(arr):
        cur += (max_ele - arr[j] + v)
        v += 1
        j += 1
    return cur

a1 = func(arr)
a2 = func(arr[::-1])
# print(a1, a2)
print(min(a1,a2))

Answer 5

const min_of_ additions = (nums) => {
let max = -Infinity;
let min = -Infinity;
for(let i = 0; i < nums.length; i++) {
max = Math.max(max, nums[i]);
// increase max, as the array have to be in asc order and next element should be greater than current element
max++;
}
// subtract 1 from max, as we do not have to increment value for the last element
max--;
for(let i = nums.length - 1; i >= 0; i--) {
min = Math.max(min, nums[i]);
// increase min, as the array have to be in decreasing order and prev element should be greater than current element
min++;
}
// subtract 1 from min, as we do not have to increment value for the first element
min--;
// at this point we know the first elements for both ascending and descending order
let asc = 0;
let desc = 0;
for(let i = 0; i < nums.length; i++) {
asc += max - nums[i];
max--;
desc += min - nums[i];
min--;
}
return Math.min(asc, desc)
}

Answer 6

Looks like you are supposed to get to increasing or decreasing by 1, according to the given answers. So my first thoughts are, you need to scan to find the highest and which direction it's generally trending and add to elements, to get them all to the appropriate levels.

 

I'm working on a JS solution... We'll see where we end up. I'll edit this comment with it when done.

 

This is what I came up with... definitely not the best, but it seems to work with the given examples. I left in some commented code of some of the original trajectories I took.

 

function minimumAdditions(arr) {
  // const diffs = [];
  // for (let i = 1; i < arr.length; i++) {
  //   diffs[i - 1] = arr[i] - arr[i - 1];
  // }
  //
  // console.dir(diffs);
  //
  // for (let i = diffs.length - 1; i > 0; i--) {
  //
  // }
  //
  // This approach is starting to look full of bugs, but back to it

  // let max = arr.reduce((mx, val, index) => (
  //   val > mx.val ? { val, index } : mx
  // ), { val: -Infinity, index: -1 });
  //
  // console.dir(max);
  //
  // This approach is shit too

  // It looks like it would be easiest to find what the max should be
  // and which end of the array it should be on... Then work from there.

  // const left = arr[0];
  // const right = arr[arr.length - 1];
  //
  // UGH, this is shit too... let's solve the first with diffs

  const diffs = [];
  for (let i = 1; i < arr.length; i++) {
    diffs[i - 1] = arr[i] - arr[i - 1];
  }

  console.dir(diffs);

  let direction = 0;
  for (const diff of diffs) {
    direction += diff > 0 ? 1 : -1;
  }

  if (direction < 0) {
    arr.reverse();
  }

  let additions = 0;
  let prevHeight = null;
  for (let i = 0; i < arr.length; i++) {
    let height = arr[i];
    if (prevHeight !== null && height - prevHeight > 1) {
      additions += (height - 1 - prevHeight) * i;
    }

    if (prevHeight !== null && height - prevHeight < 1) {
      const newAdds = prevHeight + 1 - height;
      height += newAdds;
      additions += newAdds;
    }

    prevHeight = height;
  }

  console.log('additions:', additions);
  return additions;
}

console.log(minimumAdditions([1, 4, 3, 2]) === 4);
console.log(minimumAdditions([2, 3, 2, 3]) === 4);
console.log(minimumAdditions([5, 7, 9, 4, 11]) === 9);

Answer 7

#include<iostream>
#include<bits/stdc++.h>

using namespace std;

int main()
{
	vector<int> arr = {5, 7, 9, 4, 11};
	vector<int> forward_sum = arr;
	vector<int> backward_sum = arr;

	int f_sum = 0;
	int b_sum = 0;

	int n = arr.size();
	for(int i=0;i<n;i++)
	{
		if(i==0 or forward_sum[i]>forward_sum[i-1])
		{
			continue;
		}
		else{
			f_sum+=(forward_sum[i-1]-forward_sum[i])+1;
			forward_sum[i] = forward_sum[i-1]+1;
		}
	}
	for(int i=n-1;i>=0;i--)
	{
		if(i==n-1 or backward_sum[i+1]<backward_sum[i])
		{
			continue;
		}
		else{
			b_sum+=(backward_sum[i+1]-backward_sum[i])+1;
			backward_sum[i] = backward_sum[i+1]+1;
		}
	}
	cout << min(f_sum, b_sum) << " ";
	return 0;


}

Answer 8

I had the same question in my code signal test
This solution passed all the test cases

 

 
            long long go( vector<int>&A )
            {
               int a = A[0];
               long long res = 0 ;

               int N = A.size();
               int in  0 ;
               int mx = 0 ;

               for( int i = 0 ; i < N ; i++ )
               {
                  int d = A[i]-a;

                  if( d > mx )
                  {
                      mx = d ;
                      in = i ;
                  }
                  a++;
               }
               a = A[in] - in ;

               for( int i = 0 ; i < N ; i++ )
               {
                  int d = a - A[i] ;
                  res += d ;
                  a++;
               }
               return res ;
            }       

            long long solve( vector<int>&A )
            {
               auto B = A ;
               reverse(B.begin(),B.end());
               return min( go(A) , go(B) );
            }