Amazon OA

Round 1

Questions: Q1. Given an array of size n with integers in it. And given two numbers a and b, find the minimum possible score of ELIGIBLE sub-arrays of the given array. i) The score of a sub-array is calculated as the number of distinct elements within that sub-array
ii) A sub-array is eligible if it contains at least 1 occurrence of a and b each.

vector<int> arr, int n, int a, int b;

int ans = n+1;
unordered_map<int, int> mp;
int i=0;
for(int j=0;j<n;j++){
  mp[arr[j]]++;
  if(mp[a] > 0 && mp[b] > 0)
    ans = min(ans, (int)mp.size());
  
  while(mp[a]>0 && mp[b]>0){
    ans = min(ans, (int)mp.size());
    mp[arr[i]]--;
    if(mp[arr[i]] == 0)
      mp.erase(arr[i]);
    i++;
  }
}
cout<<ans<<endl;

15/15 test cases passed.

Round 2

Questions: Q2. There are multiple delivery centers and delivery warehouses all over the world! The world is represented by a number line from -10^9 to 10^9. There are n delivery centers, with the i-th one at location center[i]. A location x is called a suitable location for a warehouse if it is possible to bring all the products to that point by traveling a distance of no more than d.

At any one time, products can be brought from one delivery center and placed at point x. Given the positions of n delivery centers, calculate the number of suitable locations in the world. That is, calculate the number of points x on the number line (-10^9 ≤ x ≤ 10^9) where the travel distance required to bring all the products to that point is less than or equal to d.

Note: The distance between point x and center[i] is |x - center[i]|, their absolute difference.

bool cal(vector<int> arr, int d, int x){
    int sum = 0;
    for(int i:arr){
        sum+=abs(x-i);
    }
    return sum<=d;
}

vector<int> arr, int n, int d;
int l1 = -1e9, h1 = arr[n-1]-d;
int minx = h1;
while(l1<=h1){
    int m = (l1+h1)/2;
    if(cal(arr, d, m)){
        minx = m;
        h1=m-1;
    }else{
        l1 = m+1;
    } 
}
l1=arr[0]+d, h1=1e9;
int maxx = l1;
while(l1<=h1){
    int m = (l1+h1)/2;
    if(cal(arr, d, m)){
        maxx = m;
        l1=m+1;
    }else{
        h1 = m-1;
    } 
}

if(maxx<minx)return 0;
return (maxx-minx+1);

Only 12/15 test cases passed.