Implement a function to reverse a string without using built-in methods.

To reverse a string without using built-in methods, the most common approaches are iteratively prepending characters to a new string or using a two-pointer technique to swap characters in an intermediate list representation. Both methods achieve O(N) time complexity.

Mechanics and Why

Iterative Prepending: This method initializes an empty result string. It then iterates through the input string, taking each character and prepending it to the result string. For example, if s = "abc", the result string progressively becomes c, then bc, then cba. This approach builds a new string and requires O(N) time and O(N) space complexity.

Two-Pointer Swap: This technique first converts the immutable input string into a mutable list of characters. Two pointers are then initialized: one at the beginning (left) and one at the end (right). Characters at these pointer positions are swapped, and the pointers move towards the center until they meet or cross. Finally, the list of characters is joined back into a string. This method is also O(N) time and O(N) space for the list conversion, but the swapping itself is an in-place operation on the list.

It's crucial to note that s[::-1] uses Python's built-in slicing functionality, which is a built-in method and thus not a valid answer to this specific prompt.

Example: Two-Pointer Swap

def reverse_string_two_pointers(s: str) -> str:
    char_list = list(s)
    left, right = 0, len(char_list) - 1
    while left < right:
        char_list[left], char_list[right] = char_list[right], char_list[left]
        left += 1
        right -= 1
    return "".join(char_list)

In the interview, also mention…

In a production data engineering context, reversing strings can be complicated by Unicode and grapheme clusters. Simply reversing bytes or even Unicode code points might break multi-byte characters or combined characters (e.g., an accented letter like é might be stored as two code points). A true "reverse" might need to understand and reverse these clusters as atomic units, which often requires specialized libraries or a deep understanding of Unicode normalization forms. This is a critical consideration when processing internationalized data in systems like Spark or databases, where incorrect handling can lead to data corruption or display issues.