Backend developer intern

Ninja has been given two sorted integer arrays/lists ‘ARR1’ and ‘ARR2’ of size ‘M’ and ‘N’. Ninja has to merge these sorted arrays/lists into ‘ARR1’ as one sorted array. You may have to assume that ‘ARR1’ has a size equal to ‘M’ + ‘N’ such that ‘ARR1’ has enough space to add all the elements of ‘ARR2’ in ‘ARR1’.

For example:

‘ARR1’ = [3 6 9 0 0]
‘ARR2’ = [4 10]
After merging the ‘ARR1’ and ‘ARR2’ in ‘ARR1’. 
‘ARR1’ = [3 4 6 9 10]

You are given an array ‘arr’ of size ‘N’. Your task is to find the sub-array in ‘arr’ where the difference between the maximum and minimum element of the sub-array is greater than the number of elements in the sub-array. You have to return an array consisting of start and end indices of the sub-array. If sub-array does not exists, then return [-1, -1].

Note:

The array is 1-indexed.

For example

You are given, ‘arr’ = [4, 3, 0, 2], here the sub-array [4, 3, 0] is the sub-array where the difference between the minimum and the maximum elements in the sub-array is 4 - 0 = 4, which is greater than the length. Hence the answer is [1, 3]. Thus, the answer is ‘YES’.

Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.

Example :

Merge Sort Algorithm -

Merge sort is a Divide and Conquer based Algorithm. It divides the input array into two-parts, until the size of the input array is not ‘1’. In the return part, it will merge two sorted arrays a return a whole merged sorted array.

The above illustrates shows how merge sort works.

Note :

It is compulsory to use the ‘Merge Sort’ algorithm.