HackerRank Coding Interview 1. Subsegment Sort

Time to complete — 29 minutes

Question Type = Medium

Asked in = Microsoft, Uber, Lyft, Bloomberg, Morgan Stanley, Apple, and Google.

Skills: arrays, sorting, dynamic programming, prefix array

Insights — It should be read very carefully read and you must ask questions in between.

Question —

An array of n integers, arr[n] can be partitioned into any number of contiguous subsegments. Every element must present in exactly 1 partition.

After partitioning, and without changing the order of partitions, sort each partition in non-descending order. Concatenate the sorted partitions and compare the resulting array to the original array, sorted non-descending. If the two match, the set of partitions is valid.

Find the maximum number of contiguous subsegments in which the array arr can be partitioned such that the set of partitions is valid.

Example

n = 6

arr = [2, 5, 1, 9, 7, 6]

1. The array can be divided into 2 contiguous subsegments:

Subsegments -> [2, 5, 1], [9, 7, 6]

Sorted subsegments -> [1, 2, 5], [6, 7, 9]

Final array -> [1, 2, 5, 6, 7, 9]

As the final arr is sorted, 2 is a possible answer.