Interview Questions: Detecting Palindromes

This problem is almost too simple to mention, but it has actually been asked of me in an interview, so I’ll go ahead and address it.

Problem: detect if a given string is a palindrome. Be sure to ignore case, spaces, and punctuation characters.

Solution: Start by setting references to the first and last characters. Now while the two references don’t cross each other, compare the characters at each reference, being sure to skip over any non alphabetic characters, and to ensure both characters are compared using the same case. Here’s a worked solution in C++ that takes both null terminated strings and C++ string objects.

#include <cstring>
#include <cctype>
#include <iostream>
#include <string>

bool is_palindrome( const char *s ) {
    const char * first = s;
    const char * last = s + strlen(s)1;
    while ( first < last ) {
        while ( ! isalpha( *first ) && *first != 0 )
            first++;
        while ( ! isalpha( *last ) && last >= s )
            last–;
        if ( toupper( *first ) != toupper( *last ) ) {
            return false;
            }
        first++;
        last–;
        }
    return true;
    }

bool is_palindrome( std::string s ) {
    return is_palindrome( s.c_str() );
    }

int main ( int argc, char **argv ) {
    for ( int i = 1; i < argc; ++i ) {
        std::string s(argv[1]);
        std::cout << is_palindrome( s ) << std::endl;
        }

    return 0;
    }
 

 

There’s not much to say about this. It is O(N) in running time and O(1) in space (unless you have an older C++ compiler, where it could be O(N) in space when called on a string object due to the way std::string::c_str() works).

Any professional programmer should be able to write this off the cuff without even thinking about it.