How should I practice Split and Sort Array?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google online assessment problems in FastPrep.

Is Split and Sort Array associated with Google?

FastPrep tags this as a Google coding interview or online assessment practice problem when the problem catalog has that company context.

FastPrep

Problem · Array

Split and Sort Array

● MediumGoogleOA

See Google hiring insights

You are given an array A of N integers. You can split the array into two non-empty parts, left and right, sort the elements in each part independently and join them back together.

For example, given array A = [1, 3, 2, 4], you can split it in the following three ways:

left = [1], right = [3, 2, 4]. Sorting the elements and joining the parts back together results in the array: [1, 2, 3, 4].
left = [1, 3], right = [2, 4]. Resulting sorted and rejoined array: [1, 3, 2, 4].
left = [1, 3, 2], right = [4]. Resulting sorted and rejoined array: [1, 2, 3, 4].

Your task is to find the number of ways of splitting the array into two parts such that, after sorting the two parts and rejoining them into a single array, the resulting array will be sorted in non-decreasing order. For the array shown above, the answer is 2: the first and third splits result in a sorted array.

Function Description

Write a function:

class Solution { public int solution(int[] A); }

which, given an array A of length N, returns the number of different ways of obtaining a sorted array by applying the procedure described above.

Examples

01 · Example 1

A = [1, 3, 2, 4]
return = 2

The function should return 2, as there are two ways to split the array into two parts that result in a sorted array after sorting and rejoining: • left = [1], right = [3, 2, 4] • left = [1, 3, 2], right = [4]

02 · Example 2

A = [3, 2, 10, 9]
return = 1

The function should return 1, as there is only one way to split the array into two parts that result in a sorted array after sorting and rejoining: • left = [3, 2], right = [10, 9]

03 · Example 3

A = [5, 5, 5]
return = 2

The function should return 2, as there are two ways to split the array into two parts that result in a sorted array after sorting and rejoining: • left = [5], right = [5, 5] • left = [5, 5], right = [5]

04 · Example 4

A = [3, 1, 2]
return = 0

The function should return 0, as there are no ways to split the array into two parts that would result in a sorted array after sorting and rejoining.

Constraints

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [1..1,000,000,000].