Question

Microsoft | OA Coding Questions and Solutions | Set - 107 | 2022

Answer 1

void solve()
{
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        v[i].ff = arr[i];
        v[i].ss = i;
    }
    sort(all(v));
    int cnt = 1;

    vector<int> index(n);
    for (int i = 0; i < n; i++)
    {
        index[i] = v[i].ss;
    }

    int i = 0;
    priority_queue<int> pq;
    pq.push(index[i]);
    while(i < n)
    {
        if(index[i] > pq.top()) cnt++;
        pq.push(index[i]);
        i++;
    }
    cout<< cnt << "\n";
}

Answer 2

int n = arr.size();
        if(n==0)return 0;
        vector<int>maxStart(n,-1), minLast(n,-1);
        maxStart[0] = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > maxStart[i - 1]) {
                maxStart[i] = arr[i];
            } else {
                maxStart[i] = maxStart[i - 1];
            }
        }
        minLast[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] < minLast[i + 1]) {
                minLast[i] = arr[i];
            } else {
                minLast[i] = minLast[i + 1];
            }
        }
        //compare
        int cnt = 1;
        for (int i = 0; i < n-1; i++) {
            if (maxStart[i] <= minLast[i+1])cnt++;
        }

return cnt;

NOTE: this ans also works when there is duplicate elements

Answer 3

void solve() {
    // take input.
    int n;
    cin>>n;
    vector<int> v;
    vin(v, n);
    // create a new vector of pairs where pair.first = x and pair.second = index of x
    vector<pair<int,int>> v2;
    for (int i=0;i<n;i++) {
        v2.push_back({v[i], i});
    }
    sort(all(v2));

    int ans = 0;
    int cur = -1;
    for (int i=0;i<n;i++) {
        cur = max(cur, v2[i].second);
        if (cur == i) {
            ans++;
            cur = -1;
        }
    }

    cout<<ans<<endl;
}

Answer 4

/*
Now the pattern here is at an given index if the sorted array and normal array has same elements till that index, then it can be a slice. Doing this will give us max number of slices

Eg: 
A  = [2,4,1,6,5,9,7]
A` = [1,2,4,5,6,7,9]

at index 0: elements till this index dont match
at index 1: elements till this index dont match
at index 2: elements till this index match
at index 3: elements till this index dont match
at index 4: elements till this index match
at index 5: elements till this index dont match
at index 6: elements till this index match

as there are 3 matches, the max slices could be 3.
 TC: O(Nlog(N)), SC: O(N)

 

The above algorithm works even when the elements are not distinct.

 

In case of distinct elements we can do the same comparison but with max seen so far have a look at the comment by @ddivyansh18 where they explained this in-detail.
*/

 

  private static int getMaxSlices(int[] nums) {
    
    int[] sortedArray = Arrays.copyOf(nums, nums.length);
    Map<Integer, Integer> counts = new HashMap<>();
    int misMatch = 0, slices = 0;
    
    for(int i=0; i< sortedArray.length ;i++){
        
        int sortedElement = sortedArray[i];
        int normalElement = nums[i];
        
        int curCount = counts.getOrDefault(sortedElement, 0)+1;
        counts.put(sortedElement, curCount);
        
        if(curCount == 0)
            misMatch--; 
        else if(curCount == 1)
            misMatch++;
        
        int normalEleCount = counts.getOrDefault(normalElement, 0)-1;
        counts.put(normalElement, normalEleCount);// 2:-1, 4:-1, 1:1-1
        
        if(normalEleCount == 0)
            misMatch--; 
        else if(normalEleCount == -1)
            misMatch++;
        
        if(misMatch == 0)
            slices++;
    }
    
    return slices;
}

Answer 5

class Solution {
public:
int solve(vector& arr) {
int n = arr.size();
int _max[n], _min[n];
_max[0] = arr[0], _min[n - 1] = arr[n - 1];
for(int i = 1; i < n; i++)
{
_max[i] = max(_max[i - 1], arr[i]);
}
for(int i = n - 2; i >= 0; i--)
{
_min[i] = min(_min[i + 1], arr[i]);
}
int ans = 1;
for(int i = 0; i < n - 1; i++)
{
ans += (_max[i] <= _min[i + 1]);
}
return ans;
}
};

Answer 6

nlogn sort solution: Get the sorted positions array, and we slice when the highest num we've seen == i. This works since if highest num we've seen==i, we would have seen i-1 smaller nums.

 

public int maxSlices(int[] a) {
 int n = a.length;
 List<Integer> pos = new ArrayList<>();
 for(int i=0; i<n; i++)
  pos.add(i);
 Collections.sort(pos, (x,y)->a[x]-a[y]);
 int max = 0, ans = 0;
 for(int i=0; i<n; i++) {
  max = Math.max(pos.get(i), max);
  if(max==i) ans++;
 }
 return ans;
}

Answer 7

public int getslicesarr(int[] arr) {
    int n = arr.length;
    int[] minOfRight = new int[n];
    minOfRight[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        minOfRight[i] = Math.min(minOfRight[i + 1], arr[i]);
    }
    int res = 0;
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < n - 1; i++) {
        max = Math.max(max,arr[i]);
        if (max <= minOfRight[i + 1]) res++;
    }
    return res + 1;
}

Answer 8

Here is my logic, copy and sort the copied array, now compare sorted array and original array, wherever the max is same continue the slice otherwise if max is not same create a new slice.
Note that Max A is simple prefix max of A upto that index.
Ex1. A=[2,4,1,6,5,9,7] (given array)
Max A=[2,4,4,6,6,9,9] (max of prefix of unsorted A upto index i)
Sort A=[1,2,4,5,6,7,9] (sorted A)

At index 0, max of unsorted A is not same as sorted A, so we create a new segment, [2]
At index 1, same as above, so segment is [2,4]
At index 2, max of unsorted A is same as sorted A (4), include that element and end the segment [1,2,4]
At index 3, max of unsorted A is not same as sorted A, so segment is [6]
At index 4, max of unsorted A is same as sorted A (6), include that element and end the segment [6,5]
... and so on

Answer 9

Given integer array A[] with distinct elements. Find max number of slices in which array can be divided, so that if all slices are combined, we get a complete sorted array. Each slice need to be sorted individually, and then these sorted slices should be combined.
Ex1. A=[2,4,1,6,5,9,7]. Ret val = 3. slices[2,4,1], [6,5], [9,7]
Ex2. A=[4,3,2,6,1]. Ret val =1. Array cannot be sliced.
Ex3. A=[2,1,6,4,3,7] Ret val =3. slices [2,1], [6,4,3],[7]

 

What logic can be used here to slice the arrays?