Reorder a String by Alternating Its Left and Right Ends
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Reorder a String by Alternating Its Left and Right Ends
Given a string `text`, construct a new string by taking characters in this order:
1. first character,
2. last character,
3. second character,
4. second-to-last character,
5. and so on until every character has been used exactly once.
Return the reordered string.
## Function Signature
```python
def alternate_ends(text: str) -> str:
...
```
## Constraints
- `0 <= len(text) <= 1_000_000`
- `text` contains printable ASCII characters, so every supported language agrees on character boundaries.
- Preserve each character exactly; do not trim or normalize the input.
## Examples
```text
Input: text = "abcde"
Output: "aebdc"
```
```text
Input: text = "abcd"
Output: "adbc"
```
```text
Input: text = ""
Output: ""
```
Quick Answer: Reorder a string by alternately taking the next character from its left and right ends until every character appears exactly once. This string-processing problem tests index boundaries, odd and even lengths, empty input, exact preservation of spaces and symbols, and linear construction at large scale.
Implement `alternate_ends(text) -> reordered`.
Given a string `text`, build a new string by walking inward from both ends at
the same time, taking one character from the left end and then one character
from the right end:
1. the first character,
2. the last character,
3. the second character,
4. the second-to-last character,
and so on until **every character has been used exactly once**. Return the
reordered string.
### Output semantics
- The result always starts from the **left** end: index `0` is emitted first,
then index `n - 1`, then index `1`, then index `n - 2`, and so on.
- The result is a permutation of `text` and therefore always has exactly
`len(text)` characters.
- When `len(text)` is **odd**, the two cursors eventually land on the same
middle index. That middle character is emitted **once** -- never twice, and
never dropped. `"abcde"` has middle character `'c'`, and the answer
`"aebdc"` contains exactly one `'c'`.
- When `len(text)` is **even** the two cursors pass each other without ever
meeting, so every step emits two characters.
- The empty string maps to the empty string.
- Characters are copied verbatim. Spaces, digits and punctuation are ordinary
characters: nothing is trimmed, case-folded, deduplicated or normalized.
- The output is fully determined by the input, so every correct implementation
returns byte-identical results.
### Examples
Example 1:
```text
text = "abcde"
reordered = "aebdc"
```
Indices are taken in the order `0, 4, 1, 3, 2`, giving `a`, `e`, `b`, `d`, `c`.
Index `2` is the middle of an odd-length string and appears exactly once.
Example 2:
```text
text = "abcd"
reordered = "adbc"
```
Indices are taken in the order `0, 3, 1, 2`, giving `a`, `d`, `b`, `c`. The
length is even, so there is no middle character to special-case.
Example 3:
```text
text = ""
reordered = ""
```
### Performance target
Aim for `O(n)` time and `O(n)` space for the returned string, where
`n = len(text)`. Appending to an immutable string inside the loop, or
repeatedly slicing/erasing the front of the input, is quadratic and will not
finish the largest case.
Constraints
- 0 <= len(text) <= 1_000_000
- text contains printable ASCII characters (character codes 32 through 126 inclusive, ' ' through '~'), so every supported language agrees on character boundaries
- Preserve each character exactly; do not trim or normalize the input
- The returned string is a permutation of text and has exactly len(text) characters
- Every index, length and offset is at most 1_000_000, which is far below 2^31 - 1, so int in Java and int in C++ are sufficient everywhere; no 64-bit type is required and there is no numeric result that can overflow
Examples
Input: ('',)
Expected Output: ''
Input: ('a',)
Expected Output: 'a'
Hints
- Keep two cursors, one at the front of the string and one at the back, and move them toward each other one step at a time. Each step contributes the characters they currently point at.
- The loop should keep going while the two cursors have not crossed. Think carefully about the single step where they point at the same index -- that is the odd-length middle character, and it must be emitted only once.
- Do not build the answer with repeated string concatenation or by chopping characters off the front of the input; both are quadratic. Append into a growable buffer (a Python list, a JavaScript array, a Java StringBuilder, a C++ std::string) and join it once at the end.