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

The "absolute sum" of an array is defined as the absolute value or the modulus of the sum of its elements. For example, the array [4,-5,-6) has an absolute sum of while the array [5,-4] has an absolute sum of 1. Let us define the "beauty" of an array as the minimum of the absolute sums of all its subarray. A "subarray" is defined as a non-empty sequence of consecutive elements of the array. An array is "beautiful" If It has a beauty greater than zero. For example, the array [-4,5,7] is beautiful with a positive beauty of 1, as its non-empty subarrays [-4], [5], [7), [-4,5]. [5,7], [-4,5,7] have absolute sums of 4, 5, 7, 1, 12 and 8 respectively On the other hand, the array [-1,1,3] is not beautiful as has a beauty of O because of its subarray (-1,1].

 

Given an arr of length n, find its number of subarrays which are beautiful.

 

n<=10^5

Answer 2

Somewhat similar: https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/

Answer 3

#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
#define int long long int

int fun(vector<int> &arr)
{
   int n = arr.size();
   unordered_map<int, int> mpp(0);

   int ans = 0;
   int sum = 0;
   mpp.insert({0, 1});
   for (auto num : arr)
   {
       sum += num;
       if (mpp.find(sum) != mpp.end())
       {
           ans += mpp[sum];
           mpp[sum] = mpp[sum] + 1;
       }
       else
           mpp[sum]++;
   }
   int total = (n * (n + 1)) / 2;
   return (total - ans);
}
signed main()
{


   int n, i ;

   cin >> n;

   vector<int> a(n, 0);

   for (i = 0; i < n; i++)
       cin >> a[i];

   cout << fun(a);
}

Answer 4

I'm not sure if your answer would be correct if you try to count the length of the subarrays that sum to 0. Their intervals may have overlap. Its probable that you count [-1, -1] twice as a beautiful subarray with input being [2, -1, -1, 2].
I think a dp solution can be applied here. let dp[i] be the number of beautiful subarrays considering only first i numbers of the subarray. Then dp[i] will be sum of dp[i-1] and the number of beautiful subarrays that end in i-th number. To count the the number of beautiful subarrays that end in arr[i] we only need to know maximum l such that there is a zero sum subarray [l, r](note thatl<i). So knowing this(it can be done with pre-computing prefixsum and using hashmap) the number of beautiful arrays that end with arr[i] would be i-l-1 plus 1 if the arr[i] is not zero itself(when the subarray only includes i-th element). It will be an O(n) solution.


UPDATE: I hope it works :)))


from collections import defaultdict


def find_number_of_beautiful_subarrays(arr):
    dp = [0 for _ in range(len(arr) + 1)]

    prefix_sum = 0  # keep prefix sum as we are iterating through numbers
    latest_index_of_sum = defaultdict(lambda: -2)  # map prefix_sum to latest index it occurred as we iterate
    latest_index_of_sum[0] = -1  # sum of none of our numbers is 0
    latest_zero_sum_index = -1  # maximum index such that there is a zero subarray starting from there

    for i in range(len(arr)):
        prefix_sum += arr[i]
        if latest_index_of_sum[prefix_sum] != -2:
            latest_zero_sum_index = max(latest_zero_sum_index, latest_index_of_sum[prefix_sum] + 1)
            latest_index_of_sum[prefix_sum] = i
        dp[i + 1] = dp[i] + max((i - latest_zero_sum_index - 1), 0) + int(arr[i] != 0)
    return dp[-1]