Sort an array in wave form
You have been given an unsorted array ‘ARR’.

Your task is to sort the array in such a way that the array looks like a wave array.

Example:

If the given sequence ‘ARR’ has ‘N’ elements then the sorted wave array looks like - ‘ARR[0] = ARR[1]’ and ‘ARR[1] = ARR[3]’ and ‘ARR[3] = ARR[5]’ and ‘ARR[5] 3 and 32 and 21 and 1

Question

Sort an array in wave form

You have been given an unsorted array ‘ARR’.

Your task is to sort the array in such a way that the array looks like a wave array.

Example:

If the given sequence ‘ARR’ has ‘N’ elements then the sorted wave array looks like - 
‘ARR[0] >= ARR[1]’ and ‘ARR[1] <= ARR[2]’
‘ARR[2] >= ARR[3]’ and ‘ARR[3] <= ARR[4]’
‘ARR[4] >= ARR[5]’ and ‘ARR[5] <= ARR[6]’  And so on.

Note:

1. ‘ARR[0]’ must be greater than or equal to ‘ARR[1]’.

2. There can be multiple arrays that look like a wave array but you have to return only one.

3. We have an internal function that will check your solution and return 'True' in case your array is one of the solutions otherwise return 'False'.

Explanation

The given array ‘ ARR = { 4, 3, 5, 2, 3, 1, 2 } ’
The below figure is a visual representation of the given ‘ARR’ and you can see we can express ‘ARR’ in a waveform array because 
4>3 and 3<5 
5>2 and 2<3
3>1 and 1<2
And it follows the condition of wave array.

subsequence

Follow up:

Try to solve this problem in linear time complexity.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains the single integer ‘N’ and ‘N’ is denoting the number elements in the given ‘ARR’.

The second line of each test case contains ‘N’ space-separated elements of ‘ARR’.

Output Format:

For each test case, print in a single line space-separated integers that represent the elements of a wave array.

Note:

You are not required to print the output explicitly, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 50
1 <= N<= 10^4
-10^9 <= ARR[i] <= 10^9

Time limit: 1 second

Accepted Answer

The task is to sort an array in a wave form, where each element is greater than or equal to its adjacent elements.

Iterate through the array and swap adjacent elements if they do not follow the wave pattern
Start from the second element and compare it with the previous element, swap if necessary
Continue this process until the end of the array
Repeat the process for the remaining elements
Return the sorted wave array

Accepted Answer

Step 1 : I explained her naive approach by sorting the linked list in O(n.log(n)) TC.,
Step 2 : interviewer asked me to optimise it.
Step 3 : After thinking sometime I told her the solution in O(n) TC, this time she seems to be happy and asked me to write the code.

Accepted Answer

Selection Based

The basic idea is that we try to make every even position to peak and every odd position to the valley.

To implement this approach we place maximum value even indices and minimum value at odd indices if indices ‘0’ basis.
Iterate a loop ‘i' which denotes the indices is odd or even
- If ‘i’ is odd then place maximum value of the array at position ‘i’, so iterate a loop ‘j’ which compare every element from ‘i’ to ‘N - 1’ if any elements are greater than the currently present element at ‘i’ then swap elements of position ‘i’ and ‘j’ and iterate for next ‘j’.
- If ‘i’ even then place minimum value of the array at position ‘i’, so iterate a loop ‘j’ which compare every element from ‘i’ to ‘N - 1’ if any element is less than currently present element at ‘i’ then swap elements of position ‘i’ and ‘j’ and iterate for next ‘j’.
Iterate for next value of ‘i’.
In the end, return ‘ARR’.

Space Complexity: O(1)Explanation:

O(1).

We are using constant space.

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the size of a given array ‘ARR’.

For each element, we iterate through the whole ‘ARR’ for finding minimum and maximum value.

Accepted Answer

Sorting Based

In this approach, we sort the given arr then swap all the adjacent elements of the array. Suppose elements after sorting ‘ARR' = { 1, 2, 3, 5, 6, 8, 10 }.Then swap all adjacent elements { 2, 1, 5, 3, 8, 6, 10 } and we see array will loop like a wave form array. Suppose sorted array is { 1, 2, 3, 5, 6, 8, 10 } . Then swap 1 and 2 now ‘ARR' = { 2, 1, 3, 5, 6, 8, 10 }’, We can say that now ‘ARR[0] >= ARR[1]’ and ‘ARR[1]< ARR[2]’, ‘ARR[1]’ will be less than 'ARR[2]’ because ‘ARR’ is sorted and elements are greater than ‘ARR[i] > ARR[1]’ at every ‘i > 1’ indices.

To implement we can use any stander sorting array that can sort elements in 0( N * log(N) ) time, for example - merge sort, heap sort, quick sort.
Sort the given array ‘ARR’.
Iterate a loop ‘i’ from ‘0’ to ‘N-1’ with jump two ‘2’
- Swap ARR[i] and ARR[i+1] , first check ARR[i+1] present in array or out of bound.
Iterate for the next value of ‘i’.
Return ‘ARR’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of a given array ‘ARR’.

We are using a sorting algorithm that takes linear extra space.

Time Complexity: O(nlogn)Explanation:

O( N * log(N) ), where ‘N’ is the size of a given array ‘ARR’.

We are using a sorting algorithm that takes ‘N * log(N)’ time.

Accepted Answer

Condition Based

In this approach we make sure at every even position ( 0, 2, 4, …. ) elements must be greater than or equal to its neighbour’s elements. Suppose we have three elements of array ‘ARR[i], ARR[i+1], ARR[i+2]’ then

Call them - ( X, Y, Z ) and ‘i’ is even

X < Y < Z then convert it into ( Y X Z )

X > Y < Z then no need to convert

X > Y > Z then convert it into ( X Z Y)

X < Y > Z then convert it into ( Y X Z ) and it can also be possible to convert it into ( Y Z X ).

By this type of conversion, we can place two elements in the right position. In the next, iteration 3 elements will be placed in the right position.

To implement this approach we iterate every even position by loop ‘I’ which iterate from ‘0’ to ‘N - 1’ with a jump of ‘2’.
Follow this simple if-else condition.
- If current element ‘ARR[i]’ is smaller than its previous element ‘ARR[i-1]’ then swap ‘ARR[i]’ and ‘ARR[i-1]’
- If current element ‘ARR[i]’ is smaller than its next element ‘ARR[i+1]’ then swap ‘ARR[i]’ and ‘ARR[i+1]’.
Iterate loop for the next value of ‘i’.
In the end, return ‘ARR’.

Space Complexity: O(1)Explanation:

O(1).

We are using constant space.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of a given array ‘ARR’.

We are iterating the whole array ‘ARR’ once.

You have been given an unsorted array ‘ARR’.

Your task is to sort the array in such a way that the array looks like a wave array.

Example:

Note:

Explanation

Follow up:

Input format:

Output Format:

Note:

Constraints:

Top Josh Technology Group Software Developer interview questions & answers

Popular interview questions of Software Developer