Interview Question: Palindromic Words

Posted by Sean on Feb 17, 2009 under Javascript

Interviewing as a programmer is always kinda fun (in my opinion). The developers already at the company get to ask you fun challenges to solve (and what programmer doesn't like to solve problems). I just rememebered one of the first questions I'd been asked on an interview, and I wanted to write a post on how to solve the problem. But then I felt it might be nice to get others trying first. So I'll offer the question, and then I'll offer my own answer in a couple days.

Of course, part of the questioning is also to allow the developers to watch you think, since you'll only have a marker and whiteboard and asked to think outloud, and only have a few minutes. But its fun exercise nonetheless.

Palindromic Words

Palindromic words are words that can be read in either direction. If you spell the word backwards, it will say the same thing. Examples include racecar , level , kayak , and so forth. There are also palindromic sentences, like Rats live on no evil star . However, my question did not involve solving sentences. I think it'd be nice extra credit to include in your answer though.

Homework

Now that you know what a palindrome is, write a function that will return true or false based on if the supplied word is a palindrome. Part of the question involves whether the interviewee can solve it, but another part is also to see if he can realize a more optimal solution than the most immediate. You can use any language you'd like, though I'd prefer a common language (no lolcode please).

Include your answer in a pre tag in the comments.

Update

Thanks all for the quality answers. I describe mine here along with some thought process and discussion.

Next: Palindromic Word: Answer Previous: Job Title: Web Magician

22 Comments

nwhite Feb 17, 2009

function isPalindromic(word) {
    var letters = word.split(''), len = letters.length, mid, mid2;
    if (! (len % 2)) {
        mid = len / 2 - 1;
        mid2 = mid + 1;
    } else {
        mid = Math.floor(len / 2) - 1;
        mid2 = mid + 2;
    }

    var first = letters.slice(0, mid + 1);
    var second = letters.slice(mid2).reverse();

    var l = first.length, i = 0, matches = true;
    while (i < l && matches) {
        if (first[i] != second[i]) matches = false;
        i++;
    }

    return matches;
}

Would have been nice if I cleaned white spaces. This should solve sentences too.

Donald Feb 17, 2009

This works in PHP and will do sentences.

function isPalindromic($word) {
  if ( $word == strrev( $word ) ) {
    return true;
  } else {
    return false;
  }
}

Sean Feb 17, 2009

@nwhite: That's definitely a solution. Though, that's a bit more work than needed, at least in Javascript. Part of the question originally, which doesn't really translate to other languages, is to assume that you don't have a lot of memory or processing power (my first job was a Mobile development position in Java).

@Donald: I can't decide if that's cheating or being resourceful. Try pretending PHP doesn't have such a method, and you need to do it manually.

Barnabas Kendall Feb 17, 2009

I think this is what you want:

public function is_palindrome($str)
{
    $chars = str_split(str_replace(' ', '', strtolower($str)));
    $length = count($chars);
    for($i = 0; $i < ($length / 2); $i++)
        if($chars[$i] != array_pop($chars))
            return FALSE;
    return TRUE;
}

Sean Feb 17, 2009

@Barnabas: Yep. Almost exactly like mine. I like the clever use of array_pop.

I don't actually create an array from the string. Depending on the language, I simply access the character at an index. In PHP or Javascript, that works like this: $str[0]. Originally in Java, it was str.charAt(0).
nwhite Feb 18, 2009
I don't think Donald's method is cheating, just resourceful ;-) My approach is a bit cumbersome. I got caught up that the indexing would be different for odd or even length strings.

I think I see where your going.
```
function is_palindrome(word){
	var i = 0, j = word.length-1;
	while( i < j){
		if( word.charAt(i) != word.charAt(j)) return false;
		i++; j--;
	}
	return true;
}
```

John Doe Feb 19, 2009

Java version :-)

public boolean isPalindrome(String word){
   return new StringBuffer(word).reverse().toString().equalsIgnoreCase(word);
}

Fernando Feb 19, 2009

A java one:

public boolean isPalindrome(String word) {
    char[] chars = word.trim().toLowerCase().toCharArray();

    for(int i = 0, l = chars.length - 1; i < l; i++, l--) {
      if(chars[i] != chars[l]) { return false; }
    }

    return true;
}

Jared Mellentine Feb 19, 2009
Donald's solution is awesome, and not just because it's similar to how I would have done it. Just a couple small changes...

First, let's shorten it up a bit:
```
function isPalindromic($word) {
  return ($word == strrev($word));
}
```
Since not all palindromic sentences have spaces in the same places on either end of the palindrome and some have punctuation and capitalization, let's make it work properly with sentences.

Quick example:
"A man, a plan, a canal, Panama!" != "!amanaP ,lanac a ,nalp a ,nam A"
"amanaplanacanalpanama" == "amanaplanacanalpanama"
```
function isPalindromic($string) {
  $string = preg_replace('/[^a-z]/', '', strtolower($string));
  return ($string == strrev($string));
}
```
So that's my solution.

Disclaimer: I didn't test that, so there could be bugs.
Sean Feb 19, 2009

Awesome, guys. I guess next time I'll have to make stricter instructions, but since I didn't, you're right to use built-in functions.

I'll post my answer in a new blog post in a couple of hours.

Another one in Java Feb 19, 2009

WTF happends with backslashes in your blog?

    public static boolean isPalindrome(String s) {
        s = s.toLowerCase().replaceAll("[^w]", "");
        int length = s.length();
        for (int i = 0; i < length / 2; i++) {
            if (s.charAt(i) != s.charAt(length - 1 - i))
                return false;
        }
        return true;
    }

anshul Feb 19, 2009

Ruby:

def is_palindrome s
  return true if s.length < 2
  return false unless  s[0,1] == s[-1,1]
  return is_palindrome s[1,s.length-2]
end

Barnabas Kendall Feb 19, 2009

Here's a super long test case: http://www.neatorama.com/2009/02/18/a-224-word-palindrome/

Robert Wictorzon Feb 19, 2009

My go in PHP:

function isPalindrome($word)
{
	$word = strtolower(str_replace(" ", "", $word));
	for($i=0, $j=strlen($word)-1; $i<=$j; $i++, $j--)
	{
		if ($word[$i] != $word[$j])
		{
			return false;
		}
	}
	return true;
}

Ian Feb 19, 2009

I agree that using built-in functions is OK unless explicitly disallowed. When I interview candidates, I'm looking to test the candidate's problem solving skills, but I also want to know more about their grasp of the language and how it can help you solve basic problems.

Francois Feb 19, 2009

What about a recursive version (in java)?

public boolean isPalindromic(String s){
   s = s.trim();
   if (s.length() <= 1) {
       return true;
   } else {
       if(s.charAt(0) == s.charAt(s.length() - 1)){
           return isPalindromic(s.substring(1,s.length()-1));
       }else{
           return false;
       }
   }
}

Frank Feb 19, 2009

My Ruby version

def palindrome?(text)
  t = text.downcase
  t == t.reverse
end

Amar Feb 22, 2009

All the solutions look great, but they are all missing a simple check at the start. If you compare the length of the two strings, if they are different, you can return false before even starting to compare them :)

Nice read... I love these kinds of posts, they really get your mind going over a quiet weekend!

antoine Feb 22, 2009

did it without looking at results..and donald's simplest built-in func
...I love arrays

function is_palindromic( $word ){
	$left2right = str_split(strtolower($word));
	$right2left = array_reverse($left2right);
	return count(array_diff_assoc($left2right, $right2left)) > 0 ? false : true ;
}

ken Feb 23, 2009

MooTools way

String.implement({
  reverse: function() {
    return this.split('').reverse().join();
  },
  isPalindrome: function() {
    return this.reverse() == this;
  }
});

Sean Feb 23, 2009

@Amar: We aren't comparing two strings. Just the reverse of the first string, so there's no way it could be a different length.

@Ken: Yay Mootools :)

akkerman Feb 23, 2009

Java will (will throw NullPointerException when s == null):

boolean isPalindrome(String s) {
  StringBuffer sb = new StringBuffer(s.replaceAll(" ", "").toLowerCase());
  return sb.equals(sb.reverse());
}

McArthur GFX