Valid Palindrome

1. The obvious way

   Build a cleaned copy, reverse it and compare. Works, but needs a whole extra copy of the text.

2. The key insight

   A palindrome is mirror-symmetric, so the outermost pair must match, then the next pair in, and so on. Two walkers, one at each end, stepping inward and skipping anything that is not a letter or digit, check this with no extra copy.

3. The algorithm
   1. Put one pointer at the very start and one at the very end.
   2. Move the left one right until it points at a letter or digit; move the right one left likewise.
   3. Compare the two letters ignoring case. Different? Answer False.
   4. Step both inward and repeat. When they meet, answer True.

Watch it run

matched pairs: A-A

def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        while left < right and not text[left].isalnum():
            left += 1                        # step over commas, spaces...
        while left < right and not text[right].isalnum():
            right -= 1
        if text[left].lower() != text[right].lower():
            return False
        left += 1
        right -= 1
    return True

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.