Interleave The First Half Of The Queue With The Second Half

Easy

0/40

Average time to solve is 15m

Contributed by

55 upvotes

Asked in company

Problem statement

You have been given a queue of integers. You need to rearrange the elements of the queue by interleaving the elements of the first half of the queue with the second half.

Note :

The given queue will always be of even length.

For example :

If N= 10
and Q = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
then the output will be
 Q = [10, 60, 20, 70, 30, 80, 40, 90, 50, 100]

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer 'N' which denotes the size of the queue.

The second line of each test case contains elements of the queue. The line consists of values of elements of the queue separated by a single space.

Output Format:

For each test case, print the elements of the queue after interleaving the elements of the first half with the second half.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
2 <= N <= 10^3
0 <= data <= 10^4
Where ‘T’ is the number of test cases, “data” is the value of the element of the queue.

Sample Input 1:

1
10
10 20 30 40 50 60 70 80 90 100

Sample Output 1:

10 60 20 70 30 80 40 90 50 100

Sample Input 2:

1
6
10 20 30 40 50 60

Sample Output 2:

10 40 20 50 30 60

Hint 1

Use stack to interleave the elements.

Approaches (1)

Approach 1

Brute-Force

The basic idea is to use a stack to interleave the elements of the queue.

Create an empty stack.
Push the elements of the first half of the queue to stack.
Enqueue back the elements of the stack(enqueue operation in queue happens from the back/rear side)
Dequeue the elements of the first half of the queue and enqueue them back at the rear side.
Again push the first half elements into the stack.
Interleave the elements of queue and stack(alternately push the top element of the stack and front element of the queue into the queue).

Time Complexity

O(N), where ‘N’ is the size of the queue.

The queue is emptied into the stack and after that, the elements are emptied and enqueued in the same way.

Space Complexity

O(N), where ‘N’ is the size of the stack.

The reason is, an auxiliary stack of size equal to that of the stack is used in the operation of interleaving

(100% EXP penalty)

Interleave The First Half Of The Queue With The Second Half

Console