Reorder a String by Alternating Its Left and Right Ends

Question

The question asks the candidate to reorder a given string by alternating characters from the left and right ends of the string.

Codemia · Accepted Answer

To solve the problem of reordering a string by alternating its left and right ends, we can utilize a two-pointer technique. We will maintain one pointer at the start of the string and another at the end, and we will construct the new string by alternating characters from these two pointers.

1. Initialize two pointers: `left` at the start (index 0) and `right` at the end (index length - 1) of the string.
2. Create an empty list to hold the reordered characters.
3. Use a loop to alternate adding characters from the `left` and `right` pointers until they meet or cross each other.
4. If the string length is odd, add the middle character after the loop.
5. Join the list into a new string and return it.

The time complexity of this algorithm is O(n), where n is the length of the string, because we are traversing the string once. The space complexity is O(n) as well, since we are storing the reordered characters in a list.

```python
def reorder_string(s):
    left, right = 0, len(s) - 1
    result = []
    while left <= right:
        if left == right:
            result.append(s[left])  # Add the middle character if odd length
        else:
            result.append(s[left])
            result.append(s[right])
        left += 1
        right -= 1
    return ''.join(result)

# Example usage:
print(reorder_string('abcdefg'))  # Output: 'agbfced'
```

Consider edge cases such as an empty string, a string with one character, or strings with special characters. Ensure that the implementation handles these cases gracefully without errors.

Reorder a String by Alternating Its Left and Right Ends

Capital One

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Capital One Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string