Interview Questions/Coding/Center Out Dispatch Decoder

Center Out Dispatch Decoder

Preview mode. Log in to edit, run, submit, and save progress.

Easy

Center Out Dispatch Decoder

A dispatcher stores a message using a center-out deque process. Starting with an empty deque, character i of the original message, using zero-based indexing, is appended to the right end when i is even and to the left end when i is odd. The stored message is the final deque read from left to right. Given the stored message, recover the original message. Input Format: The first line contains t, the number of test cases. Each test case contains n and the stored string. Output Format: For each test case, print the recovered original message.

Examples

Example 1

Input:

1
4
bacd

Output:

cadb

Explanation: If the original message were cadb, the deque steps would produce the stored string bacd. Therefore the recovered message is cadb.

Approach hint

Start with the simplest clear approach, explain the trade-off, then move toward the cleaner answer.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp