Question

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

Answer 1

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?

Answer 2

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 3

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 4

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;
}