Decreasing Subsequence Partitions Google OA 2022

Decreasing Subsequence Partitions Google OA 2023

by

Decreasing Subsequence Partitions Google OA 2023 Solution

Given an int array nums of length n. Split it into strictly decreasing subsequences. Output the min number of subsequences you can get by splitting.

Example 1:

Input: [5, 2, 4, 3, 1, 6]
Output: 3
Explanation:
You can split this array into: [5, 2, 1], [4, 3], [6]. And there are 3 subsequences you get.
Or you can split it into [5, 4, 3], [2, 1], [6]. Also 3 subsequences.
But [5, 4, 3, 2, 1], [6] is not legal because [5, 4, 3, 2, 1] is not a subsuquence of the original array.

Example 2:

Input: [2, 9, 12, 13, 4, 7, 6, 5, 10]
Output: 4
Explanation: [2], [9, 4], [12, 10], [13, 7, 6, 5]

Example 3:

Input: [1, 1, 1]
Output: 3
Explanation: Because of the strictly descending order you have to split it into 3 subsequences: [1], [1], [1]

SOLUTION

Program: Decreasing Subsequence Partitions Solution in C++

Greedy Approach

In this approach, we will prepare an array ‘tmp ’ as tmp[i] will state that whether any element can be inserted after ARR[i] or not. We will also maintain ‘ANS’ to store the number of subsequences. For each element, we will try also values left to that element and greedily pick the element whose value is just less than ARR[i]. If no such element is found, we will create a new subsequence and increase the value of ‘ANS’ by 1. 

Algorithm:

  • Declare an array ‘tmp’ to store whether we can add any element next to ARR[i] or not.
  • Declare a variable ‘ANS’ to store the number of subsequences.
  • For each index ‘i’ in range 0 to ‘N-1’,do the following:
    • Set tmp[i] as 1.
  • For each index ‘i’ in range 0 to ‘N-1’, do the following:
    • Set ‘INDEX’ as -1.
    • For each index ‘j’ in range 0 to ‘i-1’,do the following:
      • If ‘tmp[j]’ == 1 and ‘ARR[j]’ > ‘ARR[i]’:
        • If ‘INDEX’ == -1
          • Set ‘INDEX’ as ‘j’.
        • Else, if difference of ‘ARR[i]’ and ‘ARR[j]’ is less than ‘ARR[i]’ and ‘ARR[INDEX]’:
          • Set ‘INDEX’ as ‘j’.
    • If ‘INDEX’ == -1 ,no suitable element found. We will put ‘ARR[i]’ into a new subsequence:
      • Set ‘ANS’ as ‘ANS +1’.
    • Else
      • Set ‘tmp[INDEX]’ as 0.
  • Return ‘ANS’.
#include<bits/stdc++.h>
int decreasingSubsequences(int n, vector<int> &arr)
{
    vector<int> dp;
    for(int i=0;i<n;i++)
    {
        if(dp.size()==0)
            dp.push_back(arr[i]);
        else
        {
            int index = upper_bound(dp.begin(),dp.end(),arr[i])-dp.begin();
            if(index==dp.size())
                dp.push_back(arr[i]);
            else
                dp[index] = arr[i];
        }
    }
    return dp.size();
}

credit: srejanbera

Below is another approach by srejanbera using Binary Search for Decreasing Subsequence Partitions.

Greedy Approach using Binary search

In this approach, we will prepare an array ‘SUBSEQUENCES’ to store the last element of each subsequence, and for each element, we will greedily pick the best subsequence using binary search over the ‘SUBSEQUENCES’ array. At last, we will return the size of the ‘SUBSEQUENCES’ array.

Algorithm:

  • Declare a function binarySearch(VAL, ARR) that will return the index of the element in ‘ARR’ whose value is just greater than ‘VAL’.
    • Set ‘ANS’ as the length of ‘ARR’.
    • Set ‘L’ as 0.
    • Set ‘R’ as the length of ‘ARR -1’.
    • While ‘L’ is than or equal to ‘R’, do the following:
      • Set ‘MID’ as (‘L’+’R’) / 2.
      • If ‘ARR[MID]’ is greater than ‘VAL’ :
        • Set ‘ANS’ as ‘MID’
        • Set ‘R’ as ‘MID-1’.
      • Else:
        • Set ‘L’ as ‘MID+1’.
    • Return ‘ANS’
  • Declare a dynamic array ‘SUBSEQUENCES’.
  • For each index ‘i’ in range 0 to ‘N-1’,do the following:
    • Set ‘INDEX’ as binarySearch(ARR,ARR[i]).
    • If ‘INDEX’ is equal to the size of ‘SUBSEQUENCES’, it denotes that ‘ARR[i]’ does not fit in any subsequence, So we will make a new subsequence.
      • Insert ‘ARR[i]’ into ‘SUBSEQUENCES’.
    • Else:
      • We will add this element to ‘SUBSEQUENCES[INDEX]’ and set the last element of ‘SUBSEQUENCES[INDEX]’ as ‘ARR[i]’.
  • Return size of ‘SEQUENCES’ array.

Now let’s see more solutions and approaches by the people used for clearing their Google Online Assessment 2022

Program: Decreasing Subsequence Partitions Solution in C++

class Solution {
public:
    int splitDecreasing(vector<int>&nums) {
        vector<int> container;
        for (int i = 0; i < nums.size(); ++i) {
            if (container.size() == 0) {
                container.push_back(nums[i]);
            } else {
                int index = upper_bound(container.begin(), container.end(), nums[i]) - container.begin();
                if (index == container.size()) {
                    container.push_back(nums[i]);
                } else {
                    container[index] = nums[i];
                }
            }
        }
        return container.size();
    }
};

Program: Decreasing Subsequence Partitions Solution in Java

public int decreasingSubSeq(int[] arr){
        int[] piles = new int[nums.length];
        int size = 0;
        for(int num : nums){
            int l = 0, r = size;
            while(l < r){
                int mid = (l+r)/2;
                if(num >= piles[mid])
                    l = mid+1;
                else 
                    r = mid;
            }
            
            piles[l] = num;
            
            if(l == size)
                size++;
        }
        
        return size;
}

Program: Decreasing Subsequence Partitions Solution in Python

Just iterate through the array and use a greedy algorithm to insert each element to the “best” subsequence.

[2, 9, 12, 13, 4, 7, 6, 5, 10] as an example:

First we process 2, just create a new sequence seq0 = [2].

Then process 9. We can not add 9 to sqe0 (otherwise seq0 is not decreasing), so we make a new sequence. seq1=[9].

For the same reason as 9, after processing 12 and 13, we have seq0=[2], seq1=[9], seq2=[12], seq3=[13]

Then we process 4. We can append 4 to the end of any of seq1, seq2, or seq3 to make it a decreasing sequence. Now we just greedily choose seq1 (because 9 is the smallest among those greater than 4). Now we have seq0=[2], seq1=[9, 4], seq2=[12], seq3=[13].

Then 7: seq0=[2], seq1=[9, 4], seq2=[12, 7], seq3=[13].

Then 6: seq0=[2], seq1=[9, 4], seq2=[12, 7, 6], seq3=[13].

Then 5: seq0=[2], seq1=[9, 4], seq2=[12, 7, 6, 5], seq3=[13].

Then 10: seq0=[2], seq1=[9, 4], seq2=[12, 7, 6, 5], seq3=[13, 10].

Now we finished our algorithm and get 4 decreasing subsequences.

from typing import List

def DecreasingSubsequences(A:List[int])->int:
    """Return a tuple: (min length, list of corresponding subsequences)"""

    from bisect import bisect

    # at last, sequences = [seq0, seq1, seq2, seq3, ...]
    # sequences is not necessary if you only want to find the min length
    sequences = []  
    
    # tails records the last elment of each subseqence. 
    # It is always sorted.
    # tails = [seq0[-1], seq1[-1], seq2[-1], ....]
    tails = []  
    
    for n in A:
        # use a binary search (O(logN)) to greedily find a position
        # we can do this because tails is always sorted
        pos = bisect(tails, n) 

        if pos == len(tails):
            tails.append(n)
            sequences.append([])
        else:
            sequences[pos].append(tails[pos])
            tails[pos] = n
    
    # you don't need the following if you only care about length. Just return len(tails)

    # append each tail to each sequence
    for i, tail in enumerate(tails):
        sequences[i].append(tail)
    
    return len(tails), sequences

Conclusion

For more Google Online Assessment 2023 Questions check out our other post on Google OA, and also we have a complete list of Amazon Online Assessment 2023 Questions and Microsoft Online Assessment 2023 Questions are all available.

Related:

Google OA 2023 Questions

Leave a Comment

eleven − 7 =