Is Palindrome Spotify Python Interview Question

Given a string , return True if it is a palindrome, otherwise return False.

A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.

Challenge: Try solving this without using extra memory. Specifically, solve it without making a copy of .

Clarifications:

• is made up of only: letters, numbers, spaces, and standard punctuation/symbols

Example #1

Input: phrase = "Taco cat."

Output: True

Explanation: Considering only alphanumeric characters and converting to lowercase, "tacocat" is a palindrome.

Example #2

Input: phrase = "I love SQL <3"

Output: False

Explanation: Considering only alphanumeric characters and converting to lowercase, "ilovesql3" is not even close.

Housekeeping

This problem is quite annoying without the right string functions!

• returns True if all the characters are alphanumeric. (i.e. A-Z, a-z, 0-9)
• returns a copy of the string with all uppercase characters converted to lowercase

Don't worry if you didn't know these off the top of your head, most interviewers won't expect you to. You will be fine if you know that these type of functions exist, as well as how to use reference docs to identify the functions you need and how to use them.

Intuition

A palindrome is the same forward and backward. So why not just make a copy of the string, reverse it, and compare each character to its counterpart in the original, one at a time? The main reason is that this takes additional memory proportional to the size of the input string.

However, we can do essentially the same thing by using two pointers - one that reads front-to-back and another that reads back-to-front. Once the pointers touch, we know that we've compared every pair of characters.

We'll also have to ignore non-alphanumeric characters, and make sure that we are case-insensitive. In the solution below, we do these things as we go; but it would also be acceptable (though slightly less efficient) to clean the input string up-front to consist of only lowercase alphanumeric characters.

Code