Interview question: Palindrome detecting algorithm

This is the beginning of what I plan on making a series of posts about programming questions I’ve had during interviews over the years. This first one shows how to create an algorithm for detecting if a string contains a palindrome.

You’re first question maybe, “What’s a palindrome?” and being that you’re in the software engineering field and not an English major makes that a valid question. A quick explanation of a palindrome is that it’s a word that is spelled the same forwards and backwards like the names Bob or Hannah.

Ok. So that seems easy enough. Why would a software company ask you this question in an interview? Well, what if I told you that the string “race car” is also a palindrome. Now knowing this, you can probably begin to see the number of test cases rise and amount of logic needed to correctly handle each one. This is why it’s a good interview question. It shows them how you think and if you can correctly test your own logic.

Let’s begin by defining what this algorithm needs to be able to do.

• Ignore non-alpha characters
• Case insensitive character comparison
• A single letter word like ‘I’ are a valid palindrome
• A string that has no characters to compare is not a valid palindrome
• Return true if the string contains a palindrome and false otherwise

Ok. Let’s get started. How do we go about doing this?

First off, we need to compare the characters in the order of first compares to last, second compares to second to last, and so on. If any of the characters don’t match while doing this, we know it’s not a palindrome. This can be done by having 2 indexes, one that starts from the beginning of the string and another from the end of the string. Each time the indexes point to a character that match, the front index is incremented and the back index is decremented. We loop through this process until the indexes meet or until we find a pair that doesn’t match.

We’re not going to worry too much about comparing the case of the characters. Most languages have a method to either force a character to upper\lower case or to do a non-case sensitive comparison. But you should bring this up to your interviewer just so he\she knows it's on your mind.

boolean IsPalindrome(String givenWord) {

   // Setting the initial index values
   int frontIndex = 0;
   int backIndex = givenWord.length() - 1;
        
   // Moving though all the characters checking for a palindrome
   while (frontIndex <= backIndex) {
            
      // Obtaining characters to compare
      char frontChar = Character.toLowerCase(givenWord.charAt(frontIndex));
      char backChar = Character.toLowerCase(givenWord.charAt(backIndex));
            
      // Do the characters match?
      if (frontChar != backChar)
         return false;
            
      // Preparing for next loop pass
      frontIndex++;
      backIndex--;
   }
  
   //  The word is a palindrome
   return true;
}

Now we have a solution that solves for our sanity cases of Bob and Hannah, but what about “race car”? What we need to do is verify that the front index and the back index point to alphabetical characters before doing the comparison. If an index does not point to a letter, we must increment\decrement it until it does. The thing we have to be aware of while doing this is that we don’t want our indexes to pass each other.

// Trying to find an alpha character by moving left to right
while (!Character.isLetter(givenWord.charAt(frontIndex)) && frontIndex < backIndex)
   frontIndex++;
char frontChar = Character.toLowerCase(givenWord.charAt(frontIndex));

// Trying to find an alpha character by moving right to left
while (!Character.isLetter(givenWord.charAt(backIndex)) && frontIndex < backIndex)
   backIndex--;
char backChar = Character.toLowerCase(givenWord.charAt(backIndex));

Things are looking pretty good, but what about the test case for a string that contains no letters like “1337”? Your first reaction would probably be to add a check after setting frontChar to verify that it’s a letter and return false if it isn’t. This is partially correct. The problem is that a string like “a7a” is a valid palindrome and adding this check alone would not allow this test case to pass. What is also needed is a way to indicate that no other alphabetical pairs have matched before returning false. Adding a Boolean value that is initially set to false can do this. When a matching character pair has been found, this value will be set to true. This way we will only return false if we come across a frontChar that is not a letter and no previous matches have been found.

// Checking to make sure the character is an alpha character and if it isn't, checking to 
// see if a previous match has been found already.
if (!Character.isLetter(frontChar) && !matchFound)
   return false;

...

// Preparing for next loop pass
frontIndex++;
backIndex--;
matchFound = true;

Great! All we need now is to put everything together, add a string is NULL and\or 0 length check at the beginning of the method, and you have a working palindrome algorithm detector.

You can view the full algorithm code here.

Variable Expansion Within a DOS FOR Loop

Ah, the DOS FOR loop. Had I known about you earlier in life, I would probably have a day or two back. But atlas, it wasn't until recently that we met.

My first tech blog post and I'm talking about a FOR loop in DOS? Well, I figured I should start at the beginning, and for me, that's DOS.

In my current contract, I do a lot of automation in DOS. And any kind of automation is made easier with loops. Enter the FOR command. I have to admit that I didn’t know anything about the FOR command under DOS before I started this job and had to analyze someone else’s batch files. But now that I have, I’m a better scripter for knowing it.

One of the more troublesome things that I’ve dealt with is trying to set environment variables and using them all within the FOR loop. It just doesn’t work. But if you stop to think about it, it makes sense as to why it doesn’t work. Look at the example below.

Script

SET check=0
FOR %%A IN (1 2) DO (
   SET check=%%A
   ECHO Mic check %check%.
)

Output

Mic check 0.
Mic check 0.

Because all of the environment variables within the DO () are expanded only when the FOR command is reached, not for every iteration of the loop, their values are static. So in this example when the FOR command is reached, the expansion of check to its current value of 0 takes place and then the looping begins. It would look something this.

SET check=0
FOR %%A IN (1 2) DO (
   SET check=%A
   ECHO Mic check 0.
)

Note how check is expanded to 0 inside the DO ().

So, how do you deal with this limitation? There are 2 ways. The first is by using the CALL command to move the logic out of the DO () and to a different part of your script. Below is a modified version of the script that behaves in the wanted manner.

Script

SET check=0
FOR %%A IN (1 2) DO (
   CALL :MicCheck %%A
)
GOTO :eof

:MicCheck
SET check=%1
ECHO Mic check %check%.
GOTO :eof

Output

Mic check 1.
Mic check 2.

The second way of handling this is by turning on delayed variable expansion. I don’t like this method as much because unless you have it enabled by default, which it’s not as of the time of this posting, scripts don’t work out-the-door. For them to work on first run, you have to play with the SETLOCAL and ENDLOCAL commands inside your batch file. I’ve run into odd scope behaviors in the past doing this, so I prefer the CALL method shown above.

Script

SET check=0
SETLOCAL ENABLEDELAYEDEXPANSION

FOR %%A IN (1 2) DO (
   SET check=%%A
   ECHO Mic check %check%.
)

ENDLOCAL

Output

Mic check 1.
Mic check 2.

Now, this is a simple example, but I’m sure you can see how you can expand this to do what you’d like.

Happy scripting!