Interleave the first half of the queue with second half

The problem, simply

You get a queue (a waiting line) with an even number of items. Cut it into two halves: the first half and the second half. Rebuild the line so it goes: first item of the first half, first item of the second half, second item of the first half, second item of the second half, and so on.

You may only use the queue moves: add at the back, remove from the front, look at the front, and ask for the size. Change the queue in place.

A story to remember it

Picture it

Examples

Way 1: the simple way

Copy everything out, then copy it back in the right order.

1. Remove the first n / 2 items from the front into a list first.
2. Remove the other n / 2 items into a list second.
3. For i from 0 to n / 2 - 1: add first[i], then second[i] to the queue.

import java.util.*;

class Solution {
    public void interleave(Queue<Integer> q) {
        int n = q.size();
        if (n % 2 != 0) throw new IllegalArgumentException("queue length must be even");
        int half = n / 2;
        List<Integer> first = new ArrayList<>();
        List<Integer> second = new ArrayList<>();
        for (int i = 0; i < half; i++) first.add(q.poll());    // left pile
        for (int i = 0; i < half; i++) second.add(q.poll());   // right pile
        for (int i = 0; i < half; i++) {
            q.offer(first.get(i));       // one from the left
            q.offer(second.get(i));      // one from the right
        }
    }
}

How long it takes: every item leaves once and comes back once, O(n). Extra room: two lists that together hold all n items, O(n).

Way 2: the clever way

The second half does not need to leave the line at all. Only the first half goes to the side.

1. Move the first n / 2 items from the front of the queue into a helper queue.
2. Now the main queue holds only the second half, in order.
3. While the helper queue is not empty: move its front item to the back of the main queue, then move the main queue's front item to its own back.
4. When the helper is empty, the main queue is woven.

import java.util.*;

class Solution {
    public void interleave(Queue<Integer> q) {
        int n = q.size();
        if (n % 2 != 0) throw new IllegalArgumentException("queue length must be even");
        Queue<Integer> firstHalf = new ArrayDeque<>();
        for (int i = 0; i < n / 2; i++) {
            firstHalf.offer(q.poll());       // the left pile steps aside
        }
        while (!firstHalf.isEmpty()) {
            q.offer(firstHalf.poll());       // one from the left pile
            q.offer(q.poll());               // one from the right pile, which is still in q
        }
    }
}

How long it takes: each item moves at most twice, O(n). Extra room: the helper line holds only half the items, O(n / 2), which is still O(n) in big O words but half of Way 1.

Another way: with only a stack

A classic version of this question says: you may use one stack and nothing else. A stack turns things upside down, so we use it twice to get the first half back right side up, in the right place.

1. Push the first half onto the stack.
2. Pop it all back into the queue. The first half is now at the back, reversed.
3. Move the front half (the old second half) to the back. The reversed first half is now at the front.
4. Push the first half onto the stack again. Now its first item is on top.
5. While the stack is not empty: pop one to the back of the queue, then move one from the front of the queue to the back.

import java.util.*;

class Solution {
    public void interleave(Queue<Integer> q) {
        int n = q.size();
        if (n % 2 != 0) throw new IllegalArgumentException("queue length must be even");
        int half = n / 2;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < half; i++) stack.push(q.poll());     // 1. first half onto the stack
        while (!stack.isEmpty()) q.offer(stack.pop());           // 2. back into q, reversed
        for (int i = 0; i < half; i++) q.offer(q.poll());        // 3. second half to the back
        for (int i = 0; i < half; i++) stack.push(q.poll());     // 4. first half right side up
        while (!stack.isEmpty()) {                               // 5. weave
            q.offer(stack.pop());
            q.offer(q.poll());
        }
    }
}

This is also O(n) time and O(n / 2) extra room. It does more moves than Way 2, but it answers the "only a stack" version of the question.

Watch out for

• Reading q.size() inside a loop that changes the queue. Save n or half before you start moving items.
• In the stack version, forgetting step 3. Without it, the reversed first half is at the back and you weave the wrong items.
• Using Java's Stack and LinkedList works, but ArrayDeque is faster for both.

What interviewers ask next

• Can you do it with no extra structure at all, only the queue itself? Not with plain queue moves. A queue only rotates, and a rotation never changes who stands next to whom, so you need somewhere to hold items aside.
• Weave the second half first (5, 1, 6, 2, ...)? In Way 2, swap the two lines inside the loop: move the main queue's front first, then the helper's front.
• Interleave a linked list in place, like 1, n, 2, n - 1, ...? That is "reorder list": find the middle, reverse the second half, then weave the two lists by changing arrows. O(n) time and O(1) extra room.
• What does a perfect shuffle do to a deck after many rounds? With 8 cards, three perfect shuffles bring the deck back to the start. Quant interviewers like this puzzle.

Remember this

Grown-up words: the waiting line is a queue, moving from front to back is a rotation, the side line is an auxiliary queue, the pile is a stack, and the card trick is a perfect riffle shuffle.