Gary Daniels and Evan Goldring - Mock whiteboard problem

I haven't programmed in a while, but couldnt' the logic be:

1. Ensure all values are proper (not nulls, right datatypes, etc)
2. Read through string forwards
3. Reverse string
4. If both are identical, you've got your palindrome

...

Or is that flawed?

I'm trying to throw cases at this to see how it would break. Seems to me that it must not be the case, otherwise your 2 guys would have thought of it.

It also seems like just the kind of thing that a young upstart like me would suggest in an interview, only to have someone like Evan go "no, you haven't considered [x]"...

I'll happily concede that I haven't considered everything, but the above would take into account everything the original question asked for, unless I heard it wrong

edit: btw, the way Evan thought through everything was very good. Made me want to practice this before my onsite

Many *-style eugenics programs in the United States of America feature the job-interview as one of their primary ways of purifying the white collar work force this country.

The kid who founded Netscape hipped me to what he calls The Law of Crappy People. This states in summary that people who are crappy tend to hire crappy people.

None of these remarks have to with Microsoft Corporation or its affiliates, reffering to any specific events thereof. You know what George Bush says about guys like me: we're just "happy" about having the chance to say something negative.

What I do know from many specific events is that I have actually disappointed people when my efforts in the workplace have been successful. They had the world all figured out and then suddenly here I come to turn their world upside down.

Here is an example of that function in C# (it is case sensitive):

private bool CheckPalindrome(string myString)

{

int First;

int Second;

First = 0;

Second = myString.Length - 1;

while (First < Second)

{

if(myString.Substring(First,1) == myString.Substring(Second,1))

{

First ++;

Second --;

}else{

return false;

}

}

return true;

}

I'd do a different algorithm to allow for more flexibility (to allow for different collations, for example)
1) Find or write a string_reverse() function that would take a string and return it's reverse (for example, string_reverse("ABCDE") would be "EDCBA") - this would have to handle Unicode data intelligently as the byte-reverse order of a set of bytes is not the same as the character-reverse order of a Unicode string.  UTF-8 is also different from UTF-16 or UTF-32.  If the data is guaranteed US-ASCII this is not a problem.
2) write is_palindrome(s) as follows:

Count the number of characters (not bytes) in the string using a string_length function
Create four local string variables s1, s2, s3, and s4

s1 <= Make a copy of s
Strip all palindrome-insignificant characters from s1 (punctuation, whitespace, etc.)  Perhaps it would be easier to define palindrome-significant characters (A-Z, sure.  0-9? _? "-"?  Are accented characters to be replaced with their vanilla equivalents?  Perhaps preserve accented characters and let string_compare handle that.)
Canonicalize case of s1 as appropriate - all upper-case or lower-case

If the number of characters in the string is odd:
    * Set s1 = the first half of the string, NOT including the middle character
    * Set s2 = the second half of the string, also NOT including the middle character.
    * Note if s was a single character (smallest positive odd number), both s1 and s2 are the empty string.
Otherwise I can safely assume the number of characters in the string is even (perhaps 0)
    * Set s1 = the first half of the string
    * Set s2 = the second half of the string

Here the branches join again.

Set s3 = string_reverse(s2)
if s2 and s3 are "the same" (with respect to collation) then return TRUE
otherwise return FALSE
    * Create a copy s3 = string_reverse(s2)
    * if s2 and s3 are "the same" (with respect to collation) then return TRUE
    * otherwise return FALSE

There it is

It would take a lot more code than I feel comfortable typing right now.

The message that I am getting from this fictional interview question is, “Please solve this ridiculous problem to prove to me that you are intelligent.”

This line of command and performance encourages pride in being able to solve the specific problem without placing the problem in context. It sends out a false sense of security in being able to do whatever it takes to get the job done. It encourages “hard coding” instead of developing once for many problems.

And talking about this matter instead of writing code in this post is just me showing many sophomoric folk out there in the “real” world that I am simply stalling because I cannot solve the problem. I am using my slick talk to slide out of getting “real” work done. Right?

Many, many years ago, I failed to answer a job interview question where the interviewer was measuring my experience with VBA by finding out if I knew whether the StrReverse() function existed or not. What the interviewer would never know is that I wrote all of my string handling functions years before the interview and years before the StrReverse() function appeared in VBA. So I was doomed because I was unaware of this new function and I failed to memorize my own code that worked so well I forgot about it!

I will have the same problem now with C# because I fully intend to write my code so well that I won’t need to memorize every algorithm just to impress an interviewer. In the same manner that writing in Microsoft Word 2003 does not improve spelling skills, writing good code does not help me remember every algorithm under the sun. “Good” code is meant to be forgotten—and “good” documentation helps us remember in the appropriate context.

To me, the best way to interview a programmer is to put her in a room with a computer, tell her what the problem is and walk out of the room with a promise to return in 15 minutes. Very, very few programmers get the opportunity to stand up in front of a white board and “lecture” to people about solving the problem.

oopsie - s1 used for two different purposes.  Rename the first occurrence s0.

Hmmm... there's also the question of memory.  If there's a large chunk of lower-case punctuation-free white-space US-ASCII data, the video algorithm is much better.  Consider a lower-case punctuation-free white-space copy of War and Peace.

Any string_reverse() algorithm is going to make a copy of either the whole string or half the string (depending on whether it's split in the middle first.)  This could be a problem if it's a very large string.

So maybe the best thing to do is check
(i) whether it's pure ASCII
(ii) whether it's very big
and let these choices decide the algorithm.

If it's a very big string, there's also the idea of checking (say) 50 random places in the first half of the string against their corresponding mirror locations.  If any one of them fails, you can stop right there and don't have to do a string copy.  Big win.  If you do have to do a string copy, the time you spent on the 50 random places is miniscule in comparison to all the memory swapping you're going to have to do to get a copy (or half a copy.)

Just so the VB.NET folks don't feel too left out...

Private Function IsPalindrome(ByVal TestString As String) As Boolean

Dim First As Integer = 0

Dim Last As Integer = TestString.Length - 1

While First < Last

   If TestString.Substring(First, 1) = TestString.Substring(Last, 1) Then

First += 1

Last -= 1

Else

Return False

End If

End While

Return True

End Function

Here's a good test string:
A man, a plan, a canal - Panamá!
(Just in case, the second-to-the-last character is an a with a right-leaning accent.)
This is a good check for
(1) case-insensitivity
(2) accent-matching
(3) the two combined (capital A vs. small a-with-accent)

It's tempting to do the whole thing in SQL.  Then the collation stuff is automatic.

Too bad REVERSE() doesn't take ntext or it would be real easy.

pseudo-SQL follows

PROCEDURE
    IsPalindrome
       @string ntext (in)
       @ispalindrome bit (out)
AS
BEGIN
declare @a nchar
declare @b nchar
declare @done bit
declare @interestingcharacterpat = '[a-zA-Z]'
declare @length numeric
declare @index1 numeric
declare @index2 numeric

select
    @done = 0,
    @index1 = 1,
    @length = len(@string), -- use len, not datalength - characters, not bytes
    @index2 = @length

while @index1 <= @index2
begin
    -- get the first interesting character
    select
        @a = substring(@string, @index1, 1) -- uses characters
    while (@a NOT LIKE @interestingcharacterpat AND @index1 <= @index2)
    begin
        select
            @index1 = @index1 + 1,
            @a = substring(@string, @index1, 1)
    end

    -- get the last interesting character
    select
        @b = substring(@string, @index2, 1) -- uses characters
    while (@b NOT LIKE @interestingcharacterpat AND @index1 <= @index2)
    begin
        select
            @index2 = @index2 - 1,
            @b = substring(@string, @index2, 1)
    end

    if @a not like @b -- use like, not == (for collation)
    begin
        select
            @ispalindrome = 0
        return (0) -- no need to continue
    end

    -- narrow the search by one both ways
    select
        @index1 = @index1 + 1,
        @index2 = @index2 - 1
end

select
    @ispalindrome = 1

RETURN 0
END

Actually my code has some problems
* wildcarded data in the string being misterpreted by LIKE - fix by using @a = @b (works with collation despite my previous comment)
* strings like '<-' with two different non-interesting-characters are falsely returned as "not palindromes" even though they are - create an @c for the "interesting" loops and only assign it to @a or @b if it ends up being interesting

But I think the idea is sound

Oh, and if @string is NULL there's problems - but then at the beginning something like

if @string IS NULL
begin
    SELECT @IsPalindrome = NULL -- pass the null through, let the caller decide
    RETURN (0)
end

would take care of that.

public bool IsPalindrome(string palindrome)
{
   if(palindrome == null || palindrome.Length == 0)
      return false;

   palindrome = palindrome.Replace(" ", "").ToLower();
   int start = 0, end = palindrome.Length - 1;

   while(end - start >= 1)
   {
      if(palindrome[start] == palindrome[end])
      {
         start++;
         end--;
      }
      else
         return false;
   }

   return true;
}

This will validate palindromes without case sensitivity even if they have spaces, for example: A man a plan a canal Panama

public bool IsPalindrome(string palindrome)
{
   if(palindrome == null || palindrome.Length == 0)
      return false;
   palindrome = palindrome.Replace(" ", "").ToLower();
   char[] reverse = palindrome.ToCharArray();
   Array.Reverse(reverse);
   string s = new string(reverse);
   return palindrome == s;
}

Here's a case/space insensitive and smaller palindrome checker.

Out of my own curiosity, I did a few tests to test performance. I'm no performance test guru, but what I did was use an array of 271 palindromes and an array of 271 non-palidromes, then tested the array for x Iterations. The score on top is using the Array.Reverse method (the method I posted second) and the bottom score checking character by character (the method I posted first). The score is the average number of ticks per method call. The average non-palindrome was longer than the average palindrome, so that may account for the slightly slower performance.

Palindromes:

1000 Iterations
18.1072177121771
1000 Iterations
12.1946568265683

5000 Iterations
17.8115896678967
5000 Iterations
12.046842804428

10000 Iterations
17.2203335793358
10000 Iterations
11.4925402214022

15000 Iterations
17.121790897909
15000 Iterations
11.6280364083641

20000 Iterations
17.1833800738007
20000 Iterations
11.5294937269373

30000 Iterations
17.2080157441574
30000 Iterations
11.7019434194342

Non-Palindromes:

1000 Iterations
21.8025682656827
1000 Iterations
15.1509372693727

5000 Iterations
21.6547542435424
5000 Iterations
15.2248442804428

10000 Iterations
21.8764752767528
10000 Iterations
14.6335881918819

15000 Iterations
21.777932595326
15000 Iterations
14.6089525215252

20000 Iterations
22.0981963099631
20000 Iterations
14.6890184501845

30000 Iterations
22.3075995079951
30000 Iterations
14.7444487084871

The character by character method beating the Array.Reverse method on non-palindromes is a no brainer, because it returns false after the first check, where as the Array.Reverse has to reverse and test the whole string every time.

I was a bit surprised by it winning on palindromes, though. If anyone has any insight into this, I'd love to hear it. All I can assume is that a character by character check is more efficient than putting a string into an array, reversing it, and putting it back into a string.

bool IsPalindrome(char *text)
{
   if (text)
   {
      char *first = text;
      char *last = text + strlen(text) - 1;

      while (first <= last)
      {
         if (*first != *last)
            return false;

         first++;
         last--;
      }
      return true;
   }
   return false;
}

Here is the function that checks for palindrome

public bool IsPalindrome(string s)
  {
   //Parameter validations
   if(s==null||s==string.Empty) return false ;
   //replace whitespaces
   s = s.Replace(" ", "").ToLower();
   int len = s.Length ;
   Stack ds = new Stack(len);   
   for(int i=0;i<len;i++)
    ds.Push(s[i]);
   for(int i=0;i<len;i++)
   {
    char c = (char)ds.Pop();
    if(c == s[i])
     continue;
    else
     return false;
   }
   return true ;
  }

here is my stab at the palindrome problem. its the complete code to the program and all =D and it even works with spaces

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

bool IsPalindrome(string strName)

{

string strReverse = strName;

if(strName == "")

{

return false;

}

reverse(strReverse.begin(), strReverse.end());

for(int i = 0; i < strName.size(); i++)

{

if( strName[i] == strReverse[i] )

{

continue;

}

else

{

return false;

}

}

}

int main()

{

string strPalindrome;

cout << "Enter a word: ";

getline(cin, strPalindrome);

if(IsPalindrome(strPalindrome.c_str()) == false )

{

cout << strPalindrome << " is not a palindrome" << endl;

}

else

{

cout << strPalindrome << " is a palindrome" << endl;

}

getchar();

getchar();

return 0;

}

So, in the Longhorn timeframe, we'd just call

bool b = System.String.IsPalindrome(str,
   PalindromeOptions.CaseInsensative);

, right?

// This function will check if there is any alpha-numeric characters and if they orginise a palindrome
// Examples:
//  "ABBA"  = true
// "Borrow or rob?"  = true
// "ABCD" = false
// "?!?"   = false
bool IsPalindrome(TCHAR* str) {

 // Special case , invalid input can not be palindrome
 if (NULL==str) {
   return false;
 }

 // Pointer to first character in string
 TCHAR* first = str; // Initialy point to start of string
 // Pointer to second character in string
 TCHAR* second = first; 
 // Pointer to last character in string
 TCHAR* last  = str + _tsclen(str); // Initialy point to null terminator
// Point to terminator character (not nessesary NULL terminator!)
 TCHAR* term = last;
 // Flag to indicate if any alpha-numeric characters were found
 bool   nonEmpty = false;

 do {
   do {
    // Threat second character as start of new string
    first = second;

    // Get pointer to next character in new string
    // Will be used to calculate length of first character
    second = CharNext(first);

    // If first character point to terminator - this mean that there is no any valid
    // characters - so nothing that can be different. Stop comparation
    if (first>=term) return nonEmpty;
   } while (!IsCharAlphaNumeric(*first));

   do {
     // Thread previous character as terminator of new string
     term = last;

     // Extract character previous to new terminator
     last = CharPrev(str,term);

     // If we terminator crossed start of our string - return information we know already
     if (first>=term) return nonEmpty;
   } while(!IsCharAlphaNumeric(*last));

   // Compare thouse extracted characters if they are equal
   if (CompareString(LOCALE_SYSTEM_DEFAULT, // Use system default because IsCharAlphaNumeric rely on system default
                    NORM_IGNORECASE | NORM_IGNOREWIDTH | NORM_IGNOREKANATYPE, // Some crazy flags
                    first,  // first alphanumeric chacter in our string
                    second-first, // length of first character
                    last, // last alphanumeric character
                    term-last    // length of last character
                    ) != CSTR_EQUAL) {
      return false;
   }

   // Here we can set flag to indicate if any AlphaNumeric characters were found
   nonEmpty = true;

 // Loop while there any character beetwean start of string and previnator
 } while (first<term);
 
 // Looks like nothing wrong were found
 // This is valid palindrome
 // But it will be nice to check if any AlphaNumeric were found
 return nonEmpty;
}

P.S> This is C++ source code. To convert to C declare variables early. I'm unsure it will compile and work - I've coded it in WordPad
 
NOTE: As I've found CharPrev and CharNext does not support Unicode 2.0 surrogates. Also this is unknown if CompareString support them.
But this is definitely an issue with IsCharAlphaNumeric function.
Looks like modification requered to work with Unicode correctly

There's lots of code already here, so I won't add mine, but there are some issues such as desired behavior (and security) that should be addressed prior to coding, and I'm rather surprised they haven't been addressed yet in this thread.

How is the algorithm to handle punctuation and whitespace?  My thoughts are to strip them off prior to the forward/reverse iterative checking loop.

When dealing with TCHAR's the issue of internationalization needs addressed; this introduces some other interesting concepts.

Should case be considered?  Some languages have single character lower case but that same "character" in upper case is actually two characters (ala the German ß (sharp-s).  This makes for interesting buffer manipulation.

Should accented characters be accepted as equivalent to non-accented characters?  In Turkish, there are four representations of the letter 'i' that are all equivalent if you are ignoring case. 

Should we even consider the culture of the source string, or assume the current culture?

Last, but not least, is the issue of string length.  These days, I am surprised that the interviewer/interviewee did not add a string length parameter, stipulate the string is null-terminated, or better yet #include strsafe.h above the function prototype.

I'm also wondering if asking for these types of clarifications is too much - the interviewer may be thinking "get on with it already, I just want to know if you understand pointer arithmetic!"

For my own edification primarily, could you do this with regex?

ignore case, iternational, etc

strip white space, symbols, numerals etc
get length of string
divide by two = base length
      if not divisible by two -"not palindrome"

net length = base length - 2 // you do not have to compare the last two letters if all others match.

compare first and last character
    if no match - "not palindrome" 
compare second and second last........

this is bloody rough, hope you get the gist     

Hi everyone!  Evan Goldring here (the one who got talked into making my whiteboard coding public!).

Having read through many of the posts in reply to the video, I want to say that I see a lot of great thinking around this particular coding question.  Many of you are thinking clearly through the whole problem, which is very important.  It really underscores the "think first, then code" mentality I talked about in the video.

What I'm even more impressed with is seeing some of you going above and beyond and starting to think about the next logical question that an interviewer might ask: How would you test this code.  Thoughts on security, performance, and other issues raised are great to see.  It's not all about the code functioning correctly.  As I mentioned in the video, I'm an SDE/T manager, so the follow-up test question is one I use often. 

Although mentioned almost everywhere you are reading about technical interviewing, I feel it is worth repeating here: As an interviewer, I'm not necessarily looking just at what your answer was, but HOW you answered the question.  Although contrary to popular belief, questions like this aren't a "final exam" with a strict Pass/Fail grade based solely on the code you wrote judged against some mythical "right" answer.  There are many "right" answers with even more unique paths to get there.  These questions are a good look beyond just "coding" into your engineering style, problem solving approach/skills, how you handle a new challenge, how you deal with being put on the spot - the list goes on. 

Finally, remember that this is only one of many types of questions you'll see in a technical interview (at Microsoft or otherwise).  For a good summary of what to expect in general, take a look at these two posts at the Technical Careers at Microsoft blog: Part I and Part II of Interviewing at Microsoft.

//This does not handle white space but it should efficiently

//look for a forward and reverse character pattern. like so "ab c ba"

bool IsPalendrone(char* ptext)

{

bool rtnval = true;

//Check for NULL or a zero length string

if((ptext == NULL) || (*ptext == 0))

return false;

int textlen = strlen(ptext);

//Check for the case where ptext is only on char

if(textlen == 1)

return rtnval;

//ptext is more than one car we need to do some

//comparisons

char* lptr = ptext;

char* rptr = ptext + (textlen - 1);

do

{

//If we find a case where the character pointed to on

//the left and right are not equal we can say this is

//not a palendrone

if((*lptr) != (*rptr))

{

rtnval = false;

break;

}

//Move our pointer towards each other

lptr++;

rptr--;

}while(lptr <= rptr);

return rtnval;

}

Actually I think I could get away with performing one less iteration for odd length strings by changing

while(lptr <= rptr);

to

while(lptr < rptr);

because we would not need to look at the center character for odd length strings.

rasx writes:
"To me, the best way to interview a programmer is to put her in a room with a computer, tell her what the problem is and walk out of the room with a promise to return in 15 minutes. Very, very few programmers get the opportunity to stand up in front of a white board and “lecture” to people about solving the problem"

This only works if the person is not expected to work on a team.  If they are just expected to sit and hack out their code then fine.  Software that is large and complicated requires a team of people with good communication skills.  That is the real goal of the white board test. 

i would just like to point out that mine handles spaces, every type of character, numbers and letters, and  the whole schmeal. EXCEPT, now that you mention it i never checked about casing. now i ask this question though, is aBbA or AbBa a palindrome. basically i want someone to list the criteria that makes a string a palindrome and we can work from there.

static private bool isPalindrome (string stringToTest)

{

char[] stringChars = stringToTest.ToCharArray();

foreach (char character in stringChars)

{

if (char.IsPunctuation(character) || char.IsSeparator(character))

{

stringToTest = stringToTest.Replace(character.ToString(), "").ToLower();

}

}

if (stringToTest.Length % 2 == 0) // even number of characters in the string

{

int halfwayMark = (stringToTest.Length/2);

char[] firstHalf = stringToTest.Substring(0, halfwayMark).ToCharArray();

char[] secondHalf = stringToTest.Substring(halfwayMark, stringToTest.Length-halfwayMark).ToCharArray();

bool flag = true; // innocent until proven guilty

Array.Reverse(secondHalf);

for (int i=0;i<halfwayMark;i++)

{

if (firstHalf[i] != secondHalf[i])

{

flag = false;

break; // break out of the loop

}

}

return flag;

}

else // odd number of chars, middle char needs to be ignored

{

int halfwayMark = (stringToTest.Length/2) + 1;

char[] firstHalf = stringToTest.Substring(0, halfwayMark).ToCharArray();

char[] secondHalf = stringToTest.Substring(--halfwayMark).ToCharArray();

bool flag = true;

Array.Reverse(secondHalf);

for (int i=0;i<halfwayMark;i++)

{

if (firstHalf[i] != secondHalf[i])

{

flag = false;

break; // break out of the loop

}

}

return flag;

}

}

I think I'd prefer something simple like

bool IsPalindrome1(string &s)
{
	if(s.length() == 0) return false;
	string::iterator begin = s.begin();
	string::iterator last = s.end() -1;
	while(begin < last)
	{
		if(*begin++ != *last--) return false;
	}
	return true;
}

and go on from there. always liked iterators.

What happened to good old recursiveness?

This version should work for sentences as well (with punctuations etc).

public bool IsPalindrome(string inputString)
{
 StringBuilder inputStringBuilder = new StringBuilder(inputString);
 for (int i = inputString.Length-1; i > -1; i--)
  {
   if (!Char.IsLetterOrDigit(inputString.Substring(i, 1),0))
   {
    inputStringBuilder.Remove(i, 1);
   }
  }
 return IsPalindromeNormalized( inputStringBuilder.ToString().ToLower());
}

private bool IsPalindromeNormalized(string inputString)
{
 switch (inputString.Length)
 {
  case 0:
   return false;
   break;
  case 1:
   return true;
   break;
  case 2:
   return inputString.Substring(0, 1) == inputString.Substring(1, 1);
   break;
  default:
   if (inputString.Substring(0, 1) == inputString.Substring(inputString.Length - 1, 1))
   {
    return IsPalindromeNormalized(inputString.Substring(1, inputString.Length - 2));
   }
   else
   {
    return false;
   }
   break;
 }
}

Sorry, somehow felt compelling to be original

Well, reversing the string is off course a very simple and wise choice not to over-complicate the code and move on to the next task. If speed would be a goal (when using it very often), it would depend on the type of input data. If you would check the English dictionary for Palindromes, the reversing strings step could in the end be a more time consuming task than moving pointers, compare and return false after the first few iterations in most cases...

Why recurse when someone else has already written the code for you?

    Private Function IsPalindrome(ByVal strTest As String) As Boolean

        If (strTest.Length > 0) Then

            Dim sourceArray As Char() = strTest.ToCharArray()

            Dim reversedArray(sourceArray.Length - 1) As Char

            System.Array.Copy(sourceArray, reversedArray, sourceArray.Length)

            reversedArray.Reverse(reversedArray)

            Return (sourceArray = reveredArray)

        Else
            Return (False)
        End If

    End Function

BLOG: www.anguslogan.com

just out of curiosity i also did some timing. the first version was pretty much the version in the video: TCHAR* char by char comparison and incrementing/decrementing pointers.
the second fragment was the std::string::iterator based version (same thing here, comparing the dereferenced iterators and incrementing/decrementing).

these should be very accurate data. i used queryperformancecounter-based timing routines, release build with vs2003.

1000000 runs (in seconds, doesn't matter for this comparison, though):

tchar-pointer-method:
             0.17408

iterator-method:
             0.0713183

the iterator-method seemed to be much faster. ripping out the calls to _tcslen() in the tchar-pointer-method improves the situation (note: no length needed in the iterator-based version, of course):

tchar-pointer-w/o-tcslen-method:
            0.0578906

seems that the strlen functions are a real performance problem. I found it very interesting that the iterator version is so close to the _TCHAR* version.. i was a little surprised actually.

i know these measurements don't reveal anything new. just thought it would be interesting to compare a little... "old style" vs. "new style"

Here's my javascript implementation.  I couldn't find a way to make javascript equate accented characters of the same character class (a, a w/accent, a w/ring, etc.) so this is katana-sensitive.

Comes with a driver function and a test-driving form.







<h1>Javascript: function is_palindrome(s)</h1>

<script type="text/javascript">

// driver function
function check_palindrome(s)
{ var b = is_palindrome(s);

 if (b)
 { alert("YES\n\n" + s + "\n\nIS a palindrome\n");
 } else if (b == null)
 { alert("Is null a palindrome?  The answer is null.");
 } else
 { alert("NO\n\n" + s + "\n\nIS NOT a palindrome\n");
 }
}

// doesn't collate (n w/tilde doesn't match n w/o tilde)
// if accents are necessary then a Unicode-based function is probably the best way to go
function is_palindrome(s)
{ if (s == null) return null;  // pass ambiguity back to caller - let them decide

 var interestingcharspat = /[a-z]/i; // maybe add digits? or do /[:alpha:]/
 var casesensitive = 0;
 var index_left = 0;
 var index_right = s.length - 1;
 var char_left;
 var char_right;
 var debug = 1;

 while (index_left < index_right)
 {
  if (debug) alert(s.charAt(index_left) + ", " + s.charAt(index_right) + " at " + index_left + ", " + index_right);
  // get first interesting character on the left
  while (
   index_left < index_right &&
   !interestingcharspat.test(s.charAt(index_left))
  )
  { index_left++;
  }

  if (debug) alert(s.charAt(index_left) + ", " + s.charAt(index_right) + " at " + index_left + ", " + index_right);
  // get first interesting character on the right
  while (
   index_left < index_right &&
   !interestingcharspat.test(s.charAt(index_right))
  )
  { index_right--;
  }

  if (debug) alert(s.charAt(index_left) + ", " + s.charAt(index_right) + " at " + index_left + ", " + index_right);
  // if index_left >= index_right we're done
  if (index_left < index_right)
  { char_left = s.charAt(index_left);
   char_right = s.charAt(index_right);

   // handle case insensitivity
   if (!casesensitive)
   { char_left = char_left.toUpperCase(); // no-op on nonletters
    char_right = char_right.toUpperCase(); // no-op on nonletters
   }

   // if there's a mismatch then it's NOT a palindrome
   if (char_left != char_right)
   {
    if (debug) alert(char_left + ", " + char_right + " at " + index_left + ", " + index_right);
    return false;
   }

   // otherwise narrow the search by one
   index_left++;
   index_right--;
  }
 }

 // if we made it through with no mismatches it's a palindrome
 return true;
}

</script>

doesn't equate accented characters with their unaccented equivalent
<form onsubmit="check_palindrome(this.string.value); return false;">
<textarea name="string" rows="10" cols="50"
 >A man, a plan, a canal - Panama!</textarea><br>
<input type="submit" value="Check Palindrome-ness">
</form>

<a href="#" onclick="check_palindrome(null); return false;">Check palindrome-ness of null</a>

Beyond the specifics of the problem definition (what is a palindrome, case sensitivity, whitespace, punctiation, etc.) I think that it's also important to ask what properties the ideal solution should have.  Many posters have utilized pre-built string reversals and string compares.  This allows them to code a quick solution, but it may not be the most optimal in terms of performance, i.e. cpu time and memory utilization.

My thought process followed something like this:

1. work on the assumption that the best solution is the most efficient at execution time.  This makes the problem more interesting...

2. Reverse and compare are too expensive in terms of CPU and Memory.

3. I think you should be able to do that at around O(n), where n is the length of the string.

4.  I played around with different ideas about traversing the string once, and creating a hash of 1) the entire string, and 2) the first half of the string.  The importance of the order of the characters makes this impractical though, and the different cases of odd and even length strings add complexity.  Abandoned this....

5.  Next idea was to start with pointers at both ends and work my way towards the middle, comparing as I go.  I added a while/compare to skip spaces.  Code follows:

bool IsPalindrome(TCHAR* tcstring)
{
 if(tcstring==NULL|| *tcstring==NULL) return false;
 TCHAR* first=tcstring;
 TCHAR* last=(tcstring+_tcsclen(tcstring)-1);
 TCHAR space=*_T(" ");

 while(1)
 {
  if(*first!=*last)
   return false;
  while(*(++first)==space);
  while(*(--last)==space);
 if(last<=first)
  return true;
 
 } 
}

Now I wasn't quite happy with having to use the built-in _tcsclen, but this does provide a relatively efficient result, and I managed to work in the ignoring of spaces, and I checked for null strings and null pointers.

6.  In an effort to make the solution a little more "pure", I decided to manually traverse the list, looking for the null, and then work my way half-way backwards checking as I go backwards. Code follows:

bool IsPalindrome(TCHAR* tcstring)
{
 if(tcstring==NULL|| *tcstring==NULL) return false;
 TCHAR* ptr=tcstring;
 TCHAR* halfptr;
 while(*(++ptr)!=NULL);
 halfptr=tcstring+(ptr-tcstring)/2;
 while(*(tcstring++) == *(--ptr) && ptr>halfptr);
 if(*(--tcstring) == *ptr) return true; 
 return false;
}

I like this solution for its efficiency, even though it won't handle spaces, case, or punctuation.  I could handle any of those by expanding the while loops.

7.  Lastly, I thought I'd see if I could gain anything by trying the typicalyl gimmicky recursion method.  Code follows:

bool IsPalindromeHelper(TCHAR* first, TCHAR* last)
{
 if(first>=last) return true;
 if(*first!=*last) return false;
 return(IsPalindromeHelper(first+1,last-1));
}

bool IsPalindrome(TCHAR* thestr)
{
 TCHAR* last=thestr;
 while(*(++last)!=NULL);
 return(IsPalindromeHelper(thestr,--last));
}

While the recursion adds a bit of a "cool" factor to the solution, it doesn't handle spaces or case, and you have the added overhead of the recursive call, so I don't think it's quite worth it.

8.  I'd probably go back to my second solution, and work in any requirements for spaces / case insensitivity. (and add comments of course!)

9.  For preliminary testing, I'd include null pointers, invalid pointers, null strings, non-terminated strings, even-length palindromes, odd-length palindromes, even and odd length non-palindromes, near palindromes with differences at the beginning/end, near palindromes with differences at the middle two chars for even length, and differences at +/-1 from middle for odd length.  Palindromes and non-palindromes of length 1,2, 3, and very large palindrome and non-palindrome inputs of lengths 2^10, 2^16-1,2^16,2^16+1, 2^32-1,2^32, 2^32+1, etc.  Also test palindromes that excercise any of the special requirements, i.e. spaces, punctuation, etc...  Include these special chars at beginning/end/middle...

Thanks for the tips!!!

Is it Palendrome or Palindrome?   Anyway here is my C# version using Recursion.

public bool isPalindrome(String s)

{

if ( s.Length <= 1 ) return true;

if ( s.EndsWith(s.Substring(0,1) ))

     return isPalindrome( s.Substring(1, s.Length - 2 ) );

return false;

}

RickH asked what is to me at least a crucial question: What would be the properties of a good solution. Knowing what to aim for is crucial.
Maybe it is the C angle that has most here assuming that "speed & space" are the top desirable characteristics.

Personally I would rather have the candidates assume security, clarity and maintainability by default, and only go for increased efficiency as a sort of second coming. Better to ask though.

Finding out that the application domain for your little function is testing multi gigabyte strings stored on sequential access media after you have written the code might be a sort of "Duh!" moment.

Peter wrote:

Finding out that the application domain for your little function is testing multi gigabyte strings stored on sequential access media after you have written the code might be a sort of "Duh!" moment.

Indeed!
In that case, other algorithms present themselves.  The immediate solution seems to be "slurp everything into memory and pray the virtual memory doesn't run out", but if this fails there are fallbacks.

Do we know the size of the string in advance?  Is there a way for us to determine which media the nth character of the string is on?  Are all characters significant?  (That is, is the nominal middle the same as the palindromic middle?)

If all these three things are true you can read from the media holding character (length / 2) out.  If the string is not a palindrome, it is very likely you won't need to read any other media.

I must also note that at some point complexity of code becomes an issue.  If the solution is over-optimized (yes, there is such a thing) it becomes very easy to introduce bugs when maintenance is required.  As a user, I would rather have a solution without bugs than a solution that saved me a few media swaps.

Also, complex solutions are slow to develop.  If there's competition in the marketplace, speed to release may be a factor.  There's a lot to be said for keeping it simple.

I'd do it in C in any of the three ways I did it here:

First Way

#include<stdio.h>
#include <string.h>

int IsPallindrome(char*);

int main()
{
    int bRetVal =0;

    char str[100];
    printf("Enter a word: ");
    scanf("%s", &str);
    bRetVal= IsPallindrome(str);
    if (bRetVal==1)
    {
        printf("%s is a pallindrome.\n", str);
    }
    else
    {
        printf("%s is not a pallindrome. \n", str);
    }
   
    return 0;
}

int IsPallindrome(char* str)
{

    int i, j, len;
    i=j=len=0;

    //the string is not null
    if (str==NULL) return 0;

    //It might just have a null-terminator and no contents. Zero length string.
    if ((len=strlen(str))==0) return 0;

    for(i=0, j=len-1; i<=j; i++, j--)
        if(*(str+i) != *(str+j))
            return 0;

    return 1;
}


Second Way

I'd copy the string in place to another memory location and simply reverse it, and check if they are identical.


Third Way


Design Goals

No checking for spaces, because a space thing opens up two different options:

1. Under this scheme, the text, "Mal Ayal Am" would be a pallindrome  because if you prun the spaces, it reads the same forwards and backwards. In such a case it would be correct to first trim the spaces inside the string and outside it (leading and trailing) and then use the IsPallindrome function above on the resultant string.
   
2. However, if you do not ignore the spaces, it is not a pallindrome because the spaces encountered in a forward traversal do not coincide with the spaces encountered backward. In such a case, the above mentioned IsPallindrome should yeild the correct results.
   

Notes:

(1) I've used scanf which should stop reading after a white space. I might have used getline as well, and that'd have been better.
(2) The comparison done here is Binary and not Text based, so "Pop" won't be a pallindrome but "PoP" will be, The alternative TextBased solution would have either used LCase or Ucase functions or just a transpose of the ASCII values by adding or subtracting 32 for the alphanumeric keys.

A Visual Basic solution is even simpler:

Public Function IsPallindrome(ByVal StrWord As String) As Boolean
    IsPallindrome = (StrComp(Trim(StrWord), Trim(StrReverse(StrWord)), vbBinaryCompare) = 0)
End Function

Private Sub Command1_Click()
    MsgBox Text1.Text & IIf(IsPallindrome(Text1.Text), " is", " is not") & " a pallindrome."
End Sub

Sathyaish Chakravarthy wrote:

    //It might just have a null-terminator and no contents. Zero length string.
    if ((len=strlen(str))==0) return 0;

I've seen a lot of people do this but yours was a convenient example.
The more I think about it, the more I think that zero-length strings ARE palindromes.  This is especially important in recursive algorithms applied to even-length strings.
NULL strings, on the other hand - in languages where there is a distinction - are another matter.

These are exceptional cases, of course, and of secondary importance.

Maurits wrote:

The more I think about it, the more I think that zero-length strings ARE palindromes.  This is especially important in recursive algorithms applied to even-length strings.

Could you please elaborate?

I would tackle the palindrome problem in this manner. Opinions on the code and complexity are welcome :

Input:
Characters, Numbers, Alphanumerics, White Spaces, Wildcards.
----

Example Test Cases:
tarat, ta r at, tar at, ta 1 at, ab 1A1 ba, ab1A 1ba etc (The code considers them correct inputs).
Ta a, ta 1 ata, etc are not palindromes.
----

Output:
True or False
----

Algorithm:
To acheive efficient memory management, computation time and code complexity, I would parse through the text from the two

corners ie begining and end and reach the center of the text while comparing each of the input characters. There would be

checks for white spaces. Other characters such as commas, appostrophies etc would be considered as character inputs. If it

encounters white spaces, it would ignore them and (increment the begining counter or decrement the end counter).

Other implementation such as a recursive one would require extra stack space and recursive calls to the heap. Which might

not be a good idea. Reversing the string and comparing with the original one would also not be a good idea as extra memory

would be required.

Pseudocode:
-Initilize all variables ie int beg, end, bool check variables.

-point the beg pointer to the first character of the input string.

-Find length of string and point the 'end pointer' to the (str_len - 1)th position.

-Enter a while loop and compare the beg and end.

---If they are equal, do beg++ and end--.

---if they are not, check for white spaces, ignore white spaces, and inc or dec accordingly ie if beg, inc beg and leave end

as it is, OR, if it is end, than dec end and leave beg to point to where it is pointing.

----if they are still not equal, return FALSE.

-end of program.
----

Complexity:
The complexity of the code would be O(n) where n is the length of the input string. In reality, the code would run for n/2

iterations as when the beg pointer reaches the middle+1th part of the string, it would stop the while loop.

Code:

#include <iostream.h>
#include <string.h>

bool ispalin(char * input)
{
 char * beg=new char;
 char * end = new char;
 
 beg = input;
 end = &input[strlen(input)-1];
 
 if(beg==0 || beg==NULL)
  return false;
 
 while(*beg==*end && *beg != input[strlen(input)/2])
 {
  if(*beg == ' ')
   beg++;
  if(*end = ' ')
   end--;
  if(beg!=end)
   return false;
  if(beg==end)
   return true;

  beg++;
  end--;
 }
 

}

int main()
{
 bool check=false;
 char * input = new char[30];
 cin.getline(input, 30, '\n');//as cin.getline caters to white spaces as well
 check = ispalin(input);

 if(check==0)
 {
  cout<<"equal\n";
 }
 else
  cout<<"not equal\n";

 return 0;
}
-------

Sathyaish Chakravarthy wrote:

A Visual Basic solution is even simpler:

Public Function IsPallindrome(ByVal StrWord As String) As Boolean
    IsPallindrome = (StrComp(Trim(StrWord), Trim(StrReverse(StrWord)), vbBinaryCompare) = 0)
End Function

Private Sub Command1_Click()
    MsgBox Text1.Text & IIf(IsPallindrome(Text1.Text), " is", " is not") & " a pallindrome."
End Sub

Yes, that Visual Basic Solution is even simpler, but it also has alot slower performance. It is alot faster to go through and check each character, than to make a reverse copy of the whole string and compare it.

I am not even debating that the Visual Basic solution would be slower than the C code.

// Quickie C++ - worked the first time. 
// Easier than the whiteboard question I got in
// my MSFT interview.
//
// Oh yeah, this version ignores spaces just
// for grins.
//
#include <cassert>

template <
   typename RandIt, 
   typename CharT, 
   CharT space
   >
bool IsPalindrome(RandIt start, RandIt end)
{
 end--;
 do
 {
  while (space == *start)
   start++;
  while (space == *end)
   end--;
  if (end < start)
   return false;
  if (*start != *end)
   return false;
  start++;
  end--;
  
 } while (start<end);
 return true;
}

bool IsPalindrome(const char* str)
{
 assert(str);
 return IsPalindrome<const char*,char,' '>(
   str,
   str+strlen(str)
   );
}

here is an updated version of the code i pasted before. it can handle all characters and white spaces or a mix of everything together . the thing i would like the most is a technical clarification on a palindrome so we can build off of what they REALLY are and not our guesses =/. i reinvented the wheel on the Reverse() rather than using reverse() in the STL algorithm class so it would be a tad more challanging and fun to do. for space reasons, code organization and stuff like that i put it up on a code pasting site =). the link can be found here -> http://rafb.net/paste/results/1zLtoc63.html

// Not a performance or memory effective and does not work with punctuation
// But it's pretty easy to maintain and cool C++ code I can not keep private

bool IsPalindrome(TCHAR* buff) {
 if(NULL==buff) return false;

 CString chars(buff);
 return chars.MakeReverse().CollateNoCase(buff)==0;
}

boneman: all that girly detailed stuff will be taken care of in a service pack! Let these burly men sling brains!

I'm surpised we haven't seen the use of regular expressions...

I love this kind of exercies . Here is my solution

private bool IsYalendrome2(string t)
{
   if(t == null || t.Length == 0)
     return false;

   bool r = true;
   
   for(int i = 0, n = t.Length -1; i < n && r; i++, n--)
     r = t[i] == t[n];

   return r;
}

I like the XML-Blog solution (it's very elegant), but i think this one is a little more readable, and i think that's is one of the goal we (as developers) have to take care.

Anyway: B# use C# ;-D

Sathyaish Chakravarthy wrote:

Maurits wrote: The more I think about it, the more I think that zero-length strings ARE palindromes.  This is especially important in recursive algorithms applied to even-length strings.

Could you please elaborate?

OK.  One algorithm I've seen is:
Is_Palindrome:
  If the string length is 0, return TRUE *
  If the string length is 1, return TRUE
  If the first character is different than the last character, return FALSE
  Otherwise, recursively check the string minus the first and last character

The *'d line is what I'm referring to.  If the TRUE is changed to a FALSE, then every even-length palindrome will incorrectly return FALSE.

rasx wrote:

I'm surpised we haven't seen the use of regular expressions...

You didn't see my javascript solution?  I used a regular expression to test for interestingness of characters.

I feel that functional languages haven't been well represented. This is Scheme code:

(define (palindrome? s)
  (define (iter s)
    (cond ((equal? (length s) 0) #t)
          ((equal? (length s) 1) #t)
          ((equal? (car s) (car (reverse s)))
           (iter (reverse (cdr (reverse (cdr s))))))
          (else #f)))
  (iter (string->list s)))

Feel the elegance =)

Unfortunately, you can't use a regular expression to check for every palindrome. This is because the "language of palindromes" isn't a regular language.

You should be able to read more about this in a textbook that covers formal language theory. This includes a lot of textbooks which cover parsing and compilation.

Decided to try and cook up a solution. Did some testing, it handled all the test cases I threw at it correctly. It's not exactly a pretty solution, but eh.

#include <list>

inline bool isAlphanumeric(_TCHAR ch) {

    return ((ch >= 'a') && (ch <= 'z') || (ch >= 'A') && (ch <= 'Z') || (ch >= '0') && (ch <= '9'));

}

int isPalindrome(_TCHAR* string) {

    // init

    if (string == 0) return -1;

    _TCHAR *c = string;

    std::list<_TCHAR> stack;

    // build stack

    while (*c != 0)

        stack.push_back(*c++);

    _TCHAR a, b;

    while (stack.size() > 1) {

        // pull the start and end items off the stack

        a = stack.front(); b = stack.back();

        stack.pop_front(); stack.pop_back();

        if (a != b) return 0;

        // they are both equal so just test one

        if (!isAlphanumeric(a)) return 0;

    }

    // if the middle character is not alphanumeric the stack scanning algorithm won't catch it, so check

    if ((stack.size() > 0) && (!isAlphanumeric(stack.back()))) return 0;

    return 1;

}

MattK wrote:

Unfortunately, you can't use a regular expression to check for every palindrome. This is because the "language of palindromes" isn't a regular language.

Not directly.  That is, there isn't a single regular expression that detects palindromes - or to put it another way, no value of ... will make this function work:

# Perl - this function doesn't work
sub is_palindrome($)
{   return shift =~ /.../;
}

But regular expressions can be used as part of a larger tool.  This function does work (unfortunately it's still katana-sensitive...)

# Perl - this function does work but still doesn't equate ñ with n
sub is_palindrome($)
{   my $string = shift;

    # Strip out uninteresting characters
    # The following line assumes only a-z and A-Z are interesting
    $string =~ s/[^a-z]//ig;

    # Make lowercase letters uppercase
    $string =~ tr/a-z/A-Z/;

    # if the string equals it's reverse then it's a palindrome
    return $string eq reverse $string;
}

MattK wrote:

I feel that functional languages haven't been well represented. This is Scheme code:

(define (palindrome? s)
  (define (iter s)
    (cond ((equal? (length s) 0) #t)
          ((equal? (length s) 1) #t)
          ((equal? (car s) (car (reverse s)))
           (iter (reverse (cdr (reverse (cdr s))))))
          (else #f)))
  (iter (string->list s)))

Feel the elegance =)

OK, now make it handle spaces.
Kind of makes you wish that ( and ) were home-row, huh?
(devilish-grin)

I think this one is a good candidate (threats space as an ordinary char). Feel free to use it


public static bool IsPalindrome(string s)
{
    if(null == s)
        return false;

    for(int f=0, b = s.Length - 1; f < b; f++, b--)
    {
        if(s[f] != s[b])
            return false;
    }
    return true;
}

Cheers Martin, with a phone number in palindrome...cool huh?

I hate to be a ball buster to all those who have provided their solutions for the palindrome problem but I was able to solve the problem in less than 5 minutes using Visual Basic.Net.

Even the Visual Basic solutions that I read were, in my opinion, over-analyzed!

You guys are overthinking things. What I try to do when I code is to think about a problem in terms of SIMPLICITY. Have we all forgotten the cliche? KISS - keep is simple stupid!

Sounds like those of you who are using VB.Net need to be MORE aware of the incredibly power FUNCTIONS that are included in the current version of Visual Studio. It makes all the difference in the world...

Here is the VB code I've come up with - it's 5 lines:
-------------------
If Me.txt1.Text = StrReverse(Me.txt1.Text) Then

Me.txt2.Text = "True"

Else

Me.txt2.Text = "False"

End If
---------------------------

The code entails 3 objects - 2 text boxes and a button. Attach the code to a button control and
you are done.

The code handles punctuation, nulls, whitespaces and is even case sensitive meaning, this code recognizes case sensitive palindromes, so AbBa would not be considered a palindrome using this algorithm.

Now, depending on what side of the philosophical argument you are on in terms of what constitutes a palindrome relative to upper and lower case letters, the code I provided can be minimally tweaked to accommodate the palindrome for either interpretation. All that is needed to recognize mixed case palindromes is to integrate an additional function (UCase) to the mix.

I found this problem interesting but fairly easy to solve.

Brice It wrote:

I found this problem interesting but fairly easy to solve.

That's the obvious answer, but has several flaws. It's very memory hungry and requires multiple iterations through the string.

The easy, efficient way is a single pass through the string, comparing first/last characters (ignoring whitespace/punctuation as required). FWIW, that solution took less than 5 minutes to arrive at.

Since everyone's posted that though, I'll go with.

stack s
queue q

for (i = 0;i < str.Length; i++)
{
   if str[i] != whitespace
   {
      q.enqueue(str[i])
      s.push(str[i])
   }
}

palindrome=true
while (!(q.Empty))
{
   if q.dequeue != s.pop then palindrome = false
}

AndyC:::

You may be correct in your analysis regarding memory allocation within my proposed solution but that was not part of the initial problem.

The challenge was to come up with a coding algorithm that could parse text to determine whether or not a palindrome existed.

No one said anything about memory requirements within the solution.

AS technology advances, memory allocation issues will slowly begin to become a non-issue in programming in my view.

The future programmer needs to focus on understanding namespaces, classes, functions, and object thinking rather than whether or not memory has been optimized within a given algorithm.

This was a fun way to kill an hour - thanks!


using System;

using System.Collections.Generic;

#endregion

namespace IsPalindrome

{

  using System.Globalization;

  using System.Text;

  class Program

  {

    static void Main(string[] args)

    {

      Program program = new Program();

      Console.WriteLine("IsPalindrome method passes: " + program.testIsPalindrome().ToString());

    }

    bool IsPalindrome(String candidate)

    {

      return IsPalindrome(candidate, CultureInfo.CurrentCulture);

    }

/// <summary>

/// From m-w.com, definition of Palindrome: a word, verse, or sentence (as "Able was I ere I saw Elba") or a number (as 1881) that reads the same backward or forward.

/// For the purposes of this method, a palindrome is a string whose component characters "read" the same

/// forwards or backwards, ignoring whitespace, punctuation, and control. Whether it means anything in the

/// target language is, unfortunately, ignored! But it should work with strings of any culture.

/// A null culture is assumed to mean the current culture.

/// A null or zero-length candidate string is not considered a palindrome.

/// </summary>

/// <returns></returns>

    bool IsPalindrome(String candidate, CultureInfo culture)

    {

      if (null == candidate)

        return false; // null candidates are not palindromes.

      if (candidate.Length == 0)

        return false; // zero-length candidates are not palindromes

      if (null == culture)

        culture = CultureInfo.CurrentCulture; // use the default if a null was provided.

      StringBuilder blackStringB = new StringBuilder(candidate.Length); // black string; no whitespace.

// remove whitespace, punctuation, control characters; they don't count towards palindromes.

      for (int i = 0; i < candidate.Length; i++)

      {

        if (!Char.IsWhiteSpace(candidate, i)

&& !Char.IsPunctuation(candidate, i)

&& !Char.IsControl(candidate, i))

          blackStringB.Append(candidate, i, 1);

      }

// now we have no whitespace.

      if (blackStringB.Length == 0)

        return false; // zero-length candidates are not palindromes

      String blackString = blackStringB.ToString().ToUpper(culture);

// we've removed case sensitivity by converting all characters to upper case.

      int length = blackString.Length;

      for (int i = 0; i < length / 2; i++)

      {

        if (0 != blackString[i].CompareTo(blackString[(length - i) - 1]))

        return false;

      }

      return true;

    }

    bool testIsPalindrome()

    {

// palindromes

    if (!IsPalindrome("a", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("aA", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("aa", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("aaa", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("2a7a2", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("aaaa", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("aBa", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("a Ba", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("aB a", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("a.Ba?", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("A B?; a?", CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome("Able was I ere I saw Elba", CultureInfo.CurrentCulture)) // Napoleon, we hardly knew ye.

      return false;

    if (!IsPalindrome("A man, a plan, a canal: Panama!", CultureInfo.CurrentCulture))

      return false;

    StringBuilder sb = new StringBuilder();

    sb.Append(Char.MinValue);

    sb.Append(Char.MaxValue);

    sb.Append(Char.MinValue);

    if (!IsPalindrome(sb.ToString(), CultureInfo.CurrentCulture))

      return false;

    if (!IsPalindrome(GeneratePalindrome()))

      return false;

    if (!IsPalindrome(GeneratePalindrome()))

      return false;

    if (!IsPalindrome(GeneratePalindrome()))

      return false;

// not palindromes

    if (IsPalindrome("oiiunrviuhnuiycgcbzsrucgckjzsehbcuycu33ndjdjdj", CultureInfo.CurrentCulture))

      return false;

    if (IsPalindrome("67__32++7S'", CultureInfo.CurrentCulture))

      return false;

    if (IsPalindrome("ab", CultureInfo.CurrentCulture))

      return false;

    if (IsPalindrome("aB", CultureInfo.CurrentCulture))

      return false;

    if (IsPalindrome("", CultureInfo.CurrentCulture))

      return false;

    if (IsPalindrome(null, CultureInfo.CurrentCulture))

      return false;

    if (IsPalindrome("A man, a plan, a canal: Suez?", CultureInfo.CurrentCulture))

      return false;

    sb = new StringBuilder(); // check a string that can't be a palindrome with end chars.

    sb.Append(Char.MinValue);

    sb.Append(Char.MaxValue);

    sb.Append('a');

    sb.Append('a');

    sb.Append(Char.MinValue);

    sb.Append('a');

    if (IsPalindrome(sb.ToString(), CultureInfo.CurrentCulture))

      return false;

    return true;

    }

/// <summary>

/// A method for testing IsPalindrome, which brings forth the pressing question: who's testing GeneratePalindrome?

/// </summary>

  string GeneratePalindrome()

  {

    Random random = new Random();

    int halfLength = random.Next(80);

    char[] buffer = new char[halfLength * 2];

    for (int i = 0; i < halfLength; i++)

    {

      buffer[i] = (char)(random.Next(Char.MinValue, Char.MaxValue));

      buffer[buffer.Length - 1 - i] = buffer[i];

    }

    return new string(buffer);

    }

  }

}

Maurits wrote:

Sathyaish Chakravarthy wrote: Maurits wrote: The more I think about it, the more I think that zero-length strings ARE palindromes.  This is especially important in recursive algorithms applied to even-length strings. Could you please elaborate?

OK.  One algorithm I've seen is:
Is_Palindrome:
  If the string length is 0, return TRUE *
  If the string length is 1, return TRUE
  If the first character is different than the last character, return FALSE
  Otherwise, recursively check the string minus the first and last character

The *'d line is what I'm referring to.  If the TRUE is changed to a FALSE, then every even-length palindrome will incorrectly return FALSE.

See my solution, just treat 2-length strings differently, so that it only checks if both characters are the same, and then return true or false in stead of invoking itself with string length zero.

bool CheckPalindrome (string CheckString)
{
    if (null == CheckString || 0 == CheckString.Length) return false;
    for (int i = 0; i < CheckString.Length / 2; i++)
    {
        if (CheckString[i] != CheckString[CheckString.Length - 1 - i]) return false;
    }
    return true;
}

My goals were to keep the algorithm short and simple and to support a majority of common scenarios. Things not taken into account include treating spaces or accented characters in a special way, just to name two. My contribution to this thread is that a conditional statement for the odd/evenness of a string is unnecessary because the integer division will always return an integer (leaving the remainer to mod). This means in the algorithm above even strings get compared to the last character and  odd strings ignore the mod character. Also, the use of iteration (as opposed to recursion) and array-index lookup make for very fast execution times on the order of O(n).

P.S. Thanks for the props, ezu: http://channel9.msdn.com/ShowPost.aspx?PostID=19369#19369

P.S.S. Let's keep this thread interesting - anyone want to take a stab at a palindrome - generating function that uses the entire Unicode character set?

P.S.S.S. If you like these sorts of problems, check out http://www.topcoder.com

class Processor{
   internal static bool isPallindrome(string strValue){
      bool result = false;
      if(strValue==null)return result;
      byte[] bits = System.Text.UTF8Encoding.UTF8.GetBytes(strValue);

      short begin = 0, end = (short)bits.Length;
      for(short x = begin, z = end; x < bits.Length / 2 ; x++, z--)
         result = (bits[x]==bits[z-1]);

      return result;
   }
};

PeterF wrote:

Maurits wrote: Sathyaish Chakravarthy wrote: Maurits wrote: The more I think about it, the more I think that zero-length strings ARE palindromes.  This is especially important in recursive algorithms applied to even-length strings. Could you please elaborate? OK.  One algorithm I've seen is: Is_Palindrome:   If the string length is 0, return TRUE *   If the string length is 1, return TRUE   If the first character is different than the last character, return FALSE   Otherwise, recursively check the string minus the first and last character The *'d line is what I'm referring to.  If the TRUE is changed to a FALSE, then every even-length palindrome will incorrectly return FALSE.

See my solution, just treat 2-length strings differently, so that it only checks if both characters are the same, and then return true or false in stead of invoking itself with string length zero.

There's only one way to settle this - GoogleFight!

Googlefight

Darn, I lose.

empty string is a palindrome ( 2 640 results)

versus

empty string is not a palindrome ( 3 990 results)

But if I use quotes I win:

"empty string is a palindrome" (38 results)

versus

"empty string is not a palindrome" (4 results)

The winner is:    "empty string is a palindrome"   

Very Sweet!

What's going on here?  We're on the eve of what will be one of the greatest game launches in history and Tina has been absent for over a month - very distressing!  I seriously hope that she will have something to say when Halo launches.

While I wouldn't mind chilling at EB on midnight, I have work and school to deal with...so I preordered it way back when and it will come to me.  EB online FTW!  Victory!!!

I Unknown Assembly

Models & COnceps & Good Languages i need

i++ i* <#&x+0/> i not need

Maurits wrote:

The winner is:    "empty string is a palindrome"   

Here is nice problem statement http://acm.uva.es/problemset/v2/257.html and you can submit your solution to be validated (note there used GCC, not MSVC).

But in reality in real world no one customer will give complete problem statement. You have to collect requerements yourself.



BTW, On 2004/08/24 9:00 (UTC time) there will be real-time online contest.

Thouse who like problems similar to this one (and a lot of others more hard problems) are invited

How about this:

private bool IsPalindrome(string phrase)
{
  for(int i=0; i<phrase.Length/2; i++)
  {
    if(!(phrase[i]==phrase[phrase.Length-1-i]))return false;
  }
  return true;
}

A 17,259-word palindrome is available at:
http://www.norvig.com/pal2txt.html

It's the work of Peter Norvig, Director of Search Quality for Google

refactored my earlier code:

static private bool isPalindrome (string stringToTest)
{
 char[] stringChars = stringToTest.ToCharArray();
 
// format the string
 foreach (char character in stringChars)
 {
   if (char.IsPunctuation(character) || char.IsSeparator(character))
   {
     stringToTest = stringToTest.Replace(character.ToString(), "").ToLower();
   }
 }

 int halfwayMark = (stringToTest.Length/2);
 char[] firstHalf = stringToTest.Substring(0, halfwayMark).ToCharArray();
 char[] secondHalf = stringToTest.Substring(halfwayMark).ToCharArray();

 Array.Reverse(secondHalf);

 for (int i=0;i

 {
    if (firstHalf[i] != secondHalf[i])
   {
     return false;
   }
 }
 return true;
}

performance wise, this is much cheaper than most other solutions presented as it goes char by char.

eeesh, it ate my for loop...

static private bool isPalindrome (string stringToTest)

{

char[] stringChars = stringToTest.ToCharArray();

// format the string

foreach (char character in stringChars)

{

if (char.IsPunctuation(character) || char.IsSeparator(character))

{

stringToTest = stringToTest.Replace(character.ToString(), "").ToLower();

}

}

int halfwayMark = (stringToTest.Length/2);

char[] firstHalf = stringToTest.Substring(0, halfwayMark).ToCharArray();

char[] secondHalf = stringToTest.Substring(halfwayMark).ToCharArray();

Array.Reverse(secondHalf);

for (int i=0;i<halfwayMark;i++)

{

if (firstHalf[i] != secondHalf[i])

{

return false;

}

}

return true;

}

bool IsPalindrome(TCHAR *s) {

   TCHAR *e, *p = s;

   if (p == 0 || *p == 0) return false;

   e = p + _tcslen(p) - 1;

   while (*e == *p && e != p && e != s) { e--; p++; }

   return e == p || e == s;

}

printf("%s=%d\n", "ABBA", IsPalindrome("ABBA"));
printf("%s=%d\n", "ABXBA", IsPalindrome("ABXBA"));

ABBA=1
ABXBA=1

Channel 9 should have a 'weekly coding challenge'.

private bool IsPalindrome(string checkString)
{
   bool result = true;

   if (checkString != null)
   {
      for (int i=0; i<checkString.Length; i++)
      {
         if (checkString.Substring(i, 1) != checkString.Substring(checkString.Length - (i + 1), 1))
         {
            result = false;
            break;
         }
      }
   }
   return result;
}

private bool IsPalindrome(string checkString)
{
   if ((checkString == null) || (checkString == ""))
      return false;

   bool result = true;

   for (int i=0; i<checkString.Length; i++)
   {
      if (checkString.Substring(i, 1) != checkString.Substring(checkString.Length - (i + 1), 1))
         {
            result = false;
            break;
         }
   }
   return result;
}

Implementing IsPalindrome with a call to _IsPalindrome is not a solution to the problem. Neither are implementations where reverse is used or split-string-in-two-for-comparison. I am talking about the problem those interviewers had (i.e. to find a skilled programmer).

Higher level languages need another problem domain. Here's a problem to a C# developer that should match IsPalindrome in C/C++.

- Implement a fund trading system!

Or this one ... What's the output from this program (copied from Essential .NET):

public interface ICommon {

         void DoIt();

}

 

public class Base : ICommon {

         void ICommon.DoIt() { Debug.Write (“A”); }

         public virtual void DoIt() { Debug.Write (“B”); }

}

 

public class Derived : Base, ICommon {

         void ICommon.DoIt() { Debug.Write (“C”); }

         public new virtual void DoIt() { Debug.Write (“D”); }

}

 

public class ReallyDerived : Derived, ICommon {

         public override void DoIt() { Debug.Write (“E”); }

}

 

static void Main() {

         ReallyDerived r1 = new ReallyDerived();

         Derived r2 = r1;

         Base r3 = r1;

         ICommon r4 = r1;

 

         r1.DoIt();

         r2.DoIt();

         r3.DoIt();

         r4.DoIt();

}

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool IsPalindrome(string sz)
{
  string szReverse(sz.length(), ' ');
  reverse_copy(sz.begin(), sz.end(), szReverse.begin());
  return szReverse == sz;
}

bool IsPalindrome2(string sz)
{
  string::iterator forward = sz.begin(), backward = sz.end() - 1;
  while( forward < backward && *forward == *backward ) {
    ++forward; --backward;
  }
  return forward >= backward;
}

template<typename T>
bool IsPalindrome3(T sz)
{
  T::iterator forward = sz.begin(), backward = sz.end() - 1;
  while( !(forward - 1 == backward || forward == backward) && *forward == *backward ) {
    ++forward; --backward;
  }
  return (forward - 1 == backward || forward == backward);
}

int main()
{
  string sz;
  cout << "Please enter a string:" << endl;
  getline(cin, sz);
  if( IsPalindrome2(sz) )
    cout << "It's a palindrome!" << endl;
  else
    cout << "It's not a palindrome!" << endl;
 
  return 0;
}

Three versions in C++, the first one is the lazyman's version, using std::reverse_copy. The second one is the iterator implementation. And since I figured I was using iterators anyway, so why not make a templated version that works on any standard container that defines a begin() and end() that return a bidirectional iterator. That way you can check a std::list for being a palindrome too! ^_^
You could also make a version two template iterator parameters, like many of the <algorithm> functions, that would work on any bidirectional iterator, including pointers.

If I had been asked this question I would be all smiles. Throughout college, the excercise we were asked to do with all languages except COBOL was to write a function that determined whether or not a word was a palindrome.

This was a great video, and it excites me to see what MS Campus is like.

Oops, here is a quick implementation in VB.NET. I am not addressing the spaces or case sensitivity. This is in a class with Option Compare Text turned on. For those who don't speak VB, Option Compare Text will allow you to evaluate true and TrUe as equal because it compares how the string is read and not the individual characters where a != A.

Private Function IsPalindrome(ByVal inWord As String) As Boolean
   Dim max As Integer = inWord.Length - 1
   For i As Integer = 0 To max \ 2
      If Not inWord.Substring(i, 1) = inWord.Substring(max - i, 1) Then
         Return False
      End If
   Next
   Return True
End Function

Here is a recursive version of palindrome checker

public bool IsPalindrome(string s)
{
   if(s==null) return false; 
   s = s.Replace(" ", "");
   if(s.Length == 0) return false;
   return IsPalindrome(s, 0, s.length);
}

private bool IsPalindrome(String s, int first, int last) 
{
   if(first >= (s.Length / 2)) return true; 
   if ( s[first] == s[last])
    return IsPalindrome(s, ++first, --last);
   else
    return false;
}

ZippyV, that would an excellent idea.

Had to throw my 2 cents in. A lot of you have great ideas about how to reverse and compare a string but I haven't seen anyone really interrogate the problem top down correctly. That goes for the guy in the video who posed it.

A palindrome is a word, phrase or verse that is READ the same backward as forward. I believe this also implies Means the same. Just the fact that it must be a word, phrase or verse means aBBa is not a Palindrome. (In English anyway)  Neither is 'm'. Neither could a book (ie War and Peace ). So the guy in the video was incorrect in answering yes to that question. (Needs to sharpen HIS information gathering skills). Since reading a word, phrase or verse implies it is in a consistent language (Joyce's Ulysses aside) characters inconsistent with that language make testing impossible. An accent grave or aigu used in a standard English sentence would disqualify it and should raise an INVALID_CHARACTER_ERROR.
Punctuation such as commas, colons, dashes etc.. are in another layer of sentence structure addressing interpretation. They are irrelevant to determining whether a word, phrase or verse is a palindrome.
 
So the rules for reversing a string and comparing it are much different from determining if a word, phrase or verse is a palindrome.

Some of you hinted at this when you suggested puncutation and spaces should be stripped before making the comparison. I suppose to make the function generic one would have to add an additional parameter of dictionary. This would also help take care of Unicode issues.

If we consider the poser of the original task as playing the role of user I think we can glean something from the excercise other than 100 routines to find out if a string is layed out the same backwards as forwards. It is something that I think we can all relate to in our efforts to define a problem as communicated to us by our users. When he said 'Palindrome' and proceeded to outline the rules, at some point we would think "I get it. He means reverse the string and see if it is the same. He's using Palindrome to let us know that he knows (or thinks he knows) the word and therefore is an intelligent and exciting individual." We would then go write the String_Compare_Reversal method according to his rules and he would be happy.

That was an interesting clip

The result I would have come up with would have been something similar to:

bool IsPanlindrome( TCHAR *pszString )
{
   if ( NULL == pszString )
      return false;

   const int length = lstrlen( pszString );
   const int repeat = length / 2;

   for ( int loop = 0; loop < repeat; ++loop )
   {
      if ( pszString[ loop ] != pszString[ length - 1 - loop ] )
         return false;
   }

   return ( 0 != length );
}

I say similar, because I would probably have been very nervous so it may not have been exactly the same. I also think I wouldn't have written as much pseudo code as in the video, as the simplicity of the question coupled with my nervousness may have had me thinking 'he just wants me to write the code'.

I would have pointed out I was dividing the length by two because the integer arithmetic would simply discard the central character for odd length strings.

n!

ZippyV wrote:

Channel 9 should have a 'weekly coding challenge'.

10 out 10 for a good idea!!!!

Just stumbled across this, I'm not sure though if your question was answered, but here's my widow's mite. Yes a char by char check is more efficient.

A level lower and a look at the asm/binary generated by your compiler would reveal the external calls made using the second option. Now realize that every single func call would force your processor to save its registers to mem and eventually restore them as well as set-up stack frames and a return address.

With the first option you would likely find a simple reg/reg comparison and jump. Progression thru the arrays would likely be accomplished thru pointer arith.

Compilers are pretty smart but relatively unnecessary clutter fools them. More elegant with func calls but you'll take a processing hit.

that was for "TimP" by the way.

I'd liek to try my simple C++:

bool isPalen(const string & s)
{
   int len = s.length();
   if(len <= 0)  // we can also add more string checking here
   {
       cerr << "empty input" << endl;
       return false;
   }
   for(int i = 0; i < len / 2; ++i)
   {
       cout << s[i] << endl;  // for debugging
       if(s[i] != s[len - i - 1])
            return false;
   }
   return true;
}

I'm a new graduate and I wish some engineer in Microsoft liked to interview me.

Just wanted to recomend this book, 4 stars rating based on 114 reviews

Introduction to Algorithms, Second Edition
ISBN 0-262-03293-7

http://www.amazon.com/exec/obidos/tg/detail/-/0262032937

Preface

This book provides a comprehensive introduction to the modern study of computer algorithms. It presents many algorithms and covers them in considerable depth, yet makes their design and analysis accessible to all levels of readers. We have tried to keep explanations elementary without sacrificing depth of coverage or mathematical rigor.  Each chapter presents an algorithm, a design technique, an application area, or a related topic.

Algorithms are described in English and in a “pseudocode” designed to be readable by anyone who has done a little programming. The book contains over 230 figures illustrating how the algorithms work. Since we emphasize efficiency as a design criterion, we include careful analyses of the running times of all our algorithms.

The text is intended primarily for use in undergraduate or graduate courses in algorithms or data structures. Because it discusses engineering issues in algorithm design, as well as mathematical aspects, it is equally well suited for self-study by technical professionals.  In this, the second edition, we have updated the entire book. The changes range from the addition of new chapters to the rewriting of individual sentences.

To the teacher

This book is designed to be both versatile and complete. You will find it useful for a variety of courses, from an undergraduate course in data structures up through a graduate course in algorithms. Because we have provided considerably more material than can fit in a typicalone-term course, you should think of the book as a “buffet” or “smorgasbord” from which you can pick and choose the material that best supports the course you wish to teach. You should find it easy to organize your course around just the chapters you need. We have made chapters relatively self-contained, so that you need not worry about an unexpected and unnecessary dependence of one chapter on another. Each chapter presents the easier material first and the more difficult material later, with section boundaries marking natural stopping points. In an undergraduate course, you might use only the earlier sections from a chapter; in a graduate course, you might cover the entire chapter. We have included over 920 exercises and over 140 problems. Each section ends with exercises, and each chapter ends with problems. The exercises are generally short questions that test basic mastery of the material. Some are simple self-check thought exercises, whereas others are more substantial and are suitable as assigned homework. The problems are moreelaborate case studies that often introduce new material; they typically consist of several questions that lead the student through the steps required to arrive at a solution.

We have starred (⋆) the sections and exercises that are more suitable for graduate students than for undergraduates. A starred section is not necessarily more difficult than an unstarred one, but it may require an understanding of more advanced mathematics. Likewise, starred exercises may require an advanced background or more than average creativity.

To the student

We hope that this textbook provides you with an enjoyable introduction to the field of algorithms. We have attempted to make every algorithm accessible and interesting. To help you when you encounter unfamiliar or difficult algorithms, we describe each one in a step-bystep manner. We also provide careful explanations of the mathematics needed to understand the analysis of the algorithms. If you already have some familiarity with a topic, you will find the chapters organized so that you can skim introductory sections and proceed quickly to the more advanced material.

This is a large book, and your class will probably cover only a portion of its material. We have tried, however, to make this a book that will be useful to you now as a course textbook and also later in your career as a mathematical desk reference or an engineering handbook. What are the prerequisites for reading this book?

·        You should have some programming experience. In particular, you should understand recursive procedures and simple data structures such as arrays and linked lists.

·        You should have some facility with proofs by mathematical induction. A few portions of the book rely on some knowledge of elementary calculus. Beyond that, Parts I and VIII of this book teach you all the mathematical techniques you will need.

To the professional

The wide range of topics in this book makes it an excellent handbook on algorithms. Because each chapter is relatively self-contained, you can focus in on the topics that most interest you. Most of the algorithms we discuss have great practical utility. We therefore address implementation concerns and other engineering issues. We often provide practical alternatives to the few algorithms that are primarily of theoretical interest.

If you wish to implement any of the algorithms, you will find the translation of our pseudocode into your favorite programming language a fairly straightforward task. The pseudocode is designed to present each algorithm clearly and succinctly. Consequently, we do not address error-handling and other software-engineering issues that require specific assumptions about your programming environment. We attempt to present each algorithm simply and directly without allowing the idiosyncrasies of a particular programming language to obscure its essence.

 

Start:
jmp Go
string db 'AXaXA'

Palindrome proc near
 mov al,0
 test ecx,ecx
 jz ext
 pusha
 mov ebx,0
 mov edx,edi
 add edx,ecx
 shr ecx,1
 lop:
  mov ah,[edi+ebx]
  inc ebx
  cmp ah,[edx-ebx]
  jne nope
 dec ecx
 jnz lop
 inc al
 nope:
 popa
 ext:
 retn
Palindrome endp

Go:
lea edi,[string]
mov ecx,5 ;length
call Palindrome
;al=1 == true

It is cool video...

But I am very sad because this video was release at 10/18/2004 3:36:34 PM in home Channel 9, but first post was submitted at Tuesday, Aug 24, 2004 3:59 PM

I wanna see it, in first day. How..??? Where..????

I could sent my code for palindrome function

Thanks you.

bool IsPalindrome(string str){

   if(str.length()==0)

      return false;

   else if(str.length()<=2)

      return str[0]==str[str.length()-1];

   else{

      if(str[0]==str[str.length()-1])

         return IsPalindrome(str.substr(1,str.length()-2));

      else

         return false;

   }

}

Function isPalendrome(ByVal a As String) As Boolean

If a.Length < 2 Then Return True

If a.Chars(0) = a.Chars(a.Length - 1) Then

a = a.Remove(a.Length - 1, 1)

If a.Length > 0 Then a = a.Remove(0, 1)

Return isPalendrome(a)

End If

Return False

End Function

Boy, oh boy, the presentors would never get a job in our company: poor reasoning process, bad solution.

This problem is so simple that the whole solution is just one line of generic code (also with guaranteed complexity):

template<typename StringType>
inline bool is_palindrom(const StringType& str)
{ 
   return std::equal(str.begin(), str.begin() + str.size()/2, str.rend());
}

now you can instantiate the function on std::string, std::wstring, std::vector<char>, or whatever container is appropriate for your application, which has random access iterators. And if you need to make it case-insensitive, just add a corresponding binary predicate for std::equal, which is another one line of code for English, or can be non-trivial for other languages. You can even test for palindrom objects that are not strings, as long as they contain equality comparable types.

Is it just me, or is the code in the video broken? The "=>" in the "while" condition ought to be "<"...

What do you think?

bool IsPalindrome(TCHAR* tzString)
{

   // The odds of a string being Palindrome 
   // is less than one in a million so this function
   // returns false, just being safe.

   // TODO: add code here to improve this function.

   return false;


}

'puncuation and case and space sensitive
Function ispal(ByVal str As String) As Boolean
   Dim chars As Char() = str.ToCharArray()
   Array.Reverse(chars)
   If TextBox1.Text = chars Then
      Return True
   Else
      Return False
   End If
End Function

namespace Infocus
{
   using System;

   public sealed class Util
   {
      private Util(){}

      /// <summary>
      /// Verifies the input text is a palindrome.
      /// </summary>
      /// <param name="input">The text to be       verified.</param>
      /// <param name="ignoreWhitepspace">Option set to true to ignore whitespace.</param>
      /// <param name="caseSensitive">Option that toggles case-sensitive.</param>
      /// <param name="alphaOnly">Option that verifies only alpha-numeric characters exist.</param>
      public static void VerifyPalindrome(string input, bool ignoreWhitespace, bool caseSensitive, bool alphaOnly)
      {
#if DEBUG
         // verify input is not null
         // NOTE: we could simply rely on Replace() below to throw this exception, hence DEBUG
         if (input == null) 
            throw new NullReferenceException("Input cannot be null.");
#endif

         // strip whitespace
         if (ignoreWhitespace)
            input = System.Text.RegularExpressions.Regex.Replace(input, @"\s", "");

         // verify alphanumeric
         if (alphaOnly && System.Text.RegularExpressions.Regex.IsMatch(input, @"\W"))
            throw new ApplicationException("Input contained non-alphanumeric characters.");

         // lowercase input
         if (!caseSensitive)
            input = input.ToLower();

         // verify input length is valid for a palindrome
         if (input.Length < 2)
            throw new ApplicationException("Length of input must be greater than 1.");

         int forwardIndexer = 0, reverseIndexer = input.Length-1;

         while ((forwardIndexer <= reverseIndexer) && (input[forwardIndexer] == input[reverseIndexer]))
         {
            forwardIndexer++;
            reverseIndexer--;
         }

         if (forwardIndexer <= reverseIndexer)
            throw new ApplicationException("Not a valid Palindrome.");
      }

      /// <summary>
      /// Performs a case insensitive, non-whitespace intensive palindrome verification on the input string.
      /// </summary>
      /// <returns>true if input is a palindrome</returns>
      public static bool IsPalindrome(string input)
      {
         try
         {
            VerifyPalindrome(input, true, false, false);
         }
         catch (ApplicationException appex)
         {
            return false;
         }
         return true;
      }
   }
}


I prefer that exceptions be leveraged especially for internal code. Optimization based on failure-rates aside, I think it's more elegant to say in-code:

string input = "dood";
VerifyPalindrome(input);

and then fail back to the caller if he supplied us with invalid input. No need to continually re-invent error checks because of booleans along the stack.

Of course, 1 or two more overloads wouldn't hurt.

I didn't read through ALL posts made by everyone. If it looks like I copied your code, sorry, just know I didn't get past the t-sql post on the first page before realizing I thought the code should be done differently. This took me 9 minutes. I didn't test it (whiteboards don't have a debugger at Microsoft, do they?)

To be pedantic your alphaOnly parameter also allows underscores as well as alphabetic and numeric characters.

Here is an internationally savvy solution that works with Whidbey Beta 2....

using System;
using System.Text;
using System.Globalization;

bool IsPalindrome(string st) {
  StringInfo si = new StringInfo(st);
  int count = si.LengthInTextElements;

  if (count == 0) return false; 

  for (int i = 0; i < ((count % 2 != 0) ? count - 1 : count) / 2; i++) {
    string st1 = si.SubstringByTextElements(i, 1);
    string st2 = si.SubstringByTextElements(count - i - 1, 1);

    if (CultureInfo.CurrentCulture.CompareInfo.Compare(st1, st2) != 0) {
      return(false);
    }
  }

  return (true);
}

Locale-dependency!  The missing piece!  Sweet!
Throw in a couple ToLower() and IsAlpha() calls and we finally have a C-like solution that can handle the test case I proposed at the very beginning of this thread:

A man, a plan, a canal - Panamá! (note the accent)

EDIT: Hmm, the CompareOptions enum has things like IgnoreCase, IgnoreKanaType (Japanese has two alphabets), IgnoreNonSpace (accents etc.), IgnoreSymbols (spaces are symbols) - tailor-made!  Might even be able to write one-line IsPalindrome with this kind of power.

EDIT2:
Not quite one-line, but nice:

using System;
using System.Text;
using System.Globalization;

bool IsPalindrome(string s)
{   char[] cs = s.ToCharArray();
    Array.Reverse(cs);
    string r = new string(cs);

    CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;
    CompareOptions co =
        CompareOptions.IgnoreCase |
        CompareOptions.IgnoreKanaType |
        CompareOptions.IgnoreNonSpace |
        CompareOptions.IgnoreSymbols |
        CompareOptions.IgnoreWidth;

    return (ci.Compare(s, r, co) == 0);
}

Note IsPalindrome("A man, a plan, a canal - Panamá!") == true
Also note IsPalindrome("") == true - a feature

Posted driver app in Sandbox

Note that this will fail for all types of combining characters -- thus the stringinfo stuff being needed?

Ah... due to the ArrayReverse... I see... working on a fix

EDIT: here's the fix (don't have Whidbey beta 2, sorry)

string StringReverse(string s)
{    TextElementEnumerator e = StringInfo.GetTextElementEnumerator(s);
    string r = "";

    while (e.MoveNext())
    {    r = e.GetTextElement() + r;
    }

    return r;
}

bool IsPalindrome(string s)
{   string r = StringReverse(s);

    CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;
    CompareOptions co =
        CompareOptions.IgnoreCase |
        CompareOptions.IgnoreKanaType |
        CompareOptions.IgnoreNonSpace |
        CompareOptions.IgnoreSymbols |
        CompareOptions.IgnoreWidth;

    return (ci.Compare(s, r, co) == 0);
}

I'm trying to do an iterative version too - where instead of copy/reverse, you put a finger on the beginning and the end and compare relevant TextElements until you either find a mismatch (return false) or your fingers meet (return true)

And here's the iterative version:

bool IsPalindrome(string s)
{    CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;
    CompareOptions co =
        CompareOptions.IgnoreCase |
        CompareOptions.IgnoreKanaType |
        CompareOptions.IgnoreNonSpace |
        CompareOptions.IgnoreSymbols |
        CompareOptions.IgnoreWidth;

    int i = 0;
    TextElementEnumerator e = StringInfo.GetTextElementEnumerator(s);
            
    while (e.MoveNext())
    {    i++; // just counting, that's all
    }

    String[] ts = new String[ i ];

    e.Reset();
    i = 0;
    while (e.MoveNext())
    {    ts[ i ] = e.GetTextElement();
        i++;
    }

    // phew!  Now ts[ i ] is an array of textelements
    // place finger A on the beginning of the string
    // place finger B on the end of the string
    // move fingers toward the middle a step at a time
    // until you get to a mismatch or your fingers meet
    int a = 0;
    int b = ts.Length - 1;
    while (a < b)
    {    // move A forward until you find an interesting element
        while (a < b && ci.Compare(ts[ a ], "", co) == 0)
        {    a++;
        }

        // move B backward until you find an interesting element
        while (a < b && ci.Compare(ts[ b ], "", co) == 0)
        {    b--;
        }

        if (a < b)
        {    // compare the two elements
            // if they're the same, continue...
            if (ci.Compare(ts[ a ], ts[ b ], co) == 0)
            {    a++; b--;
            }
            else // they're different - NOT a palindrome
            {    return false;
            }
        }
    }

    return true;
}

Updated Sandbox project
Instead of hardcoding the CompareOptions I created checkboxes for all the Ignore... options.  Default is to ignore everything.

Why no one sees the obvious solution using regular
C++ standard library facility:

bool is_palindrome(const string& s) {
   return equal(s.begin(), s.end(), s.rbegin());
}


The equal funcition assumes that the second sequence is the same size as the first, so it does not need
and ending iterator.


Stefan

Not very efficient, and not even a MS product, but here is my interpretation.  I'm not horribly efficient, but oh well.

......

type
  TPalindromeResult = (prTrue, prFalse, prLengthMismatch, prException);

......

procedure TForm1.Button1Click(Sender: TObject);
begin
  Case IsPalindrome(edit1.Text, edit2.Text) of
    prTrue:
      MessageDlg('You the man',mtInformation,[mbOk],0);
    prFalse:
      MessageDlg('You not the man', mtInformation, [mbOk],0);
    prLengthMismatch:
      MessageDlg('Can''t compare, length mismatch', mtInformation, [mbOk],0);
  End;
end;

......

function TForm1.IsPalindrome(Str1, Str2: String): TPalindromeResult;
Var
  WorkStr : String;
  X : Integer;
begin
  Try
    Try
      //Perform basic checks before iteration.
      If (Length(Str1) <> Length(Str2)) Then Begin
        Result := prLengthMismatch;
        Exit;
      End;

      For X := 1 to Length(Str1) do
        Insert(Copy(Str2,X,1),WorkStr,0);

      If (WorkStr = Str1) Then
        Result := prTrue
      Else
        Result := prFalse;

    Except
      On Exception do Result := prException;

    End;
  Finally
    //Perform any necessary cleanup
  End;

TimP, yours is the best. You make use of the best performing C# implementation by using the native methods in the .net framework and the least lines of code. Just MHO Cheers, Kosher MCSD/MCAD .net

Here's what I came up with in a few minutes. It should run in linear time and in-place. Not sure if it will work with TCHARs yet, so I'll give that a shot in a few minutes.

bool isAlphaNumeric(char c)
{
    if(iswalpha(c) || iswdigit(c)) return true;
    return false;    
}

bool isPalindrome(char *str)
{
    if(*str == '\0')
    {
        return false;    
    }
    int len = strlen(str);
    if(len <= 1) return true; // 0- or 1-length strings are simplest palindromes
    
    char *start = str;
    char *end = start + strlen(str) - 1;
    
    while(start < end)
    {
        // if start not a char, increment start and continue
        if(!isAlphaNumeric(*start))
        {
            *start++;
            continue;    
        }
        // if end not a char, decrement end and continue
        if(!isAlphaNumeric(*end))
        {
            *end--;
            continue;    
        }
        // if two characters are not equal, return false
        if(towlower(*start) != towlower(*end)) return false;
        // otherwise start++, end--
        *start++;
        *end--;        
    }
    return true;
}

Edit: Yup, substituting TCHAR for char works just fine. And just for the hell of it, here's strrev (or revstr, to avoid name conflicts)

void revstr(TCHAR *str)
{
    if(*str == '\0')
    {
        return;    
    }
    
    TCHAR *start = str;
    TCHAR *end = start + strlen(str) - 1;
    
    while(start < end)
    {
        *start ^= *end;
        *end ^= *start;
        *start ^= *end;
        *start++;
        *end--;
        // could also use *start ^= *end ^= *start++ ^= *end-- if you want to get fancy
    }    
}

Ike-it's Ritz!  Where you been?  I was talking to JJ last night, and he said MJK had come across this video.  Nice work! 
-LIZ

A bit too late (like a year or so, but just stumbled on this video preparing for my own interview...). Anyway here is my 2 cents in Java (handles case, punctuation, spaces by ignoring them). Tried to compress the algorithm as much as possible, but still keep the readability:

    public static boolean findPolyndrom(String polynd) {

        if (polynd == null || "".equals(polynd = polynd.toLowerCase().trim())) {
            return false;
        }
       
        int index = 0;
        int length = polynd.length();

        char forward = 0;
        char reverse = 0;
       
        boolean isValidString = false;
       
        while (index < length) {
           
            while(!Character.isLetterOrDigit(forward = polynd.charAt(index++))) {
                if (index >= length) {
                    return isValidString;
                }
            }
           
            while(!Character.isLetterOrDigit(reverse = polynd.charAt(--length))) {
                if (length <= index) {
                    return isValidString;
                }
            }

            isValidString = true;
           
            if (forward != reverse) {
                return false;
            }

            if (length <= index) {
                break;
            }
        }
        return true;
    }

Try using my new non-KISS, très l33t solution to check any String for palindromosity.  I'm sure Matz should add this to 1.8.4.

#!/usr/bin/ruby

#extend Ruby's built-in String class to allow palindrome checking, then give it a try!
#public domain, november 25th, 2005 by dale anderson

class String
        def palindrome?
                #normalize the string, result: s
                s = self.gsub(/\W/, '').upcase

                #string length, half length
                sl = s.length
                hl = sl / 2

                # sl    hl      p1      p2      SAMPLE FIGURES
                # 8     4       0-3     4-7  
                # 7     3       0-2     4-6
                # 6     3       0-2     3-5
                # 5     2       0-1     3-4
                # 4     2       0-1     2-3
                # 3     1       0-0     2-2
                # 2     1       0-0     1-1
                # 1     0       0-0     0-0 *
                # 0     0       0-0     0-0 *

                # * we observe that 0 and 1 are special cases
                return true if sl <= 1

                #compare the p1 versus the backwards p2
                p1 = s[ 0       ..      (hl-1)  ]
                p2 = s[ (sl-hl) ..     (sl-1)    ]

                #puts " *** '#{p1}' vs. '#{p2}' ***"

                return true if p1 == p2.reverse
                return false
        end
end



tests = {
        'pull-up' => true,
        'Oo.pSpOo' => true,
        '' => true,
        'A' => true,
        '4321/abc\ba 1 2 3 4' => true,

        "hi there" => false,
        'mememe' => false
        }

for potpal,georgeboole in tests
        raise "Potential Palindrome: '#{potpal}' was #{not georgeboole}!" unless
                potpal.palindrome? == georgeboole
end

Thanks for the video. 

My approach would have been to first solve the problem in the quickest (i.e. takes the shortest time to think of) way, likely using standard C++ library or the reverse-string approach. This would give me a chance to bring up the fact that I recognize that I'm being paid by the minute to write code and that I'm interested in protecting the company's bottom-line and not just to fool around with a small piece of code and waste time doing unnecessary embellishments and speed optimizations. Once I'm sure the interviewer gets my point about business considerations then I would qualify my first answer by saying however if the code proved (in about 2-3% of the time) to fall within the "critical" code category then I would next show the more efficient code (which I could be working out in my head while mindlessly presenting the more obvious but inefficient one). Plenty of techies are good at being playfully ingenious but precious few realize that it is also important to show one's bosses that one is shares their companies' bottomline concerns.

Using C# 2.0....

public static bool IsPalindrome(string val)

{

   char[] _chars = val.ToCharArray();

   System.Array.Reverse(_chars);

   string _reverseVal = new string(_chars);

   return val.Equals(_reverseVal);

}

This is my code, it is pretty good...
if anyone destruct this, please tell me


bool isPalandrome( char* str ){
 bool result = true ;
 char *end = str + strlen( str ) - 1;

 while( str < end )
  result &= (((*(str++)) ^ (*(end--))) == 0);
 return result;
}

Hi All!

how about this
code does take in account for characters you want to skip,
but it does not check for case sensivivity

pure c++, not using any rtl
avoiding checking for special case if string is "ABA" for example

TCHAR ptszSkip[] = {' ', ',', '!', '-'};
bool IsPalindrome(TCHAR* ptsz)
{
   bool bRet = false;
   if(NULL != ptsz)
   {
      TCHAR* ptszEnd = ptsz;
      while(*ptszEnd != 0)  //get end pointer
      {
         ++ptszEnd;
      }
      --ptszEnd;
      bRet = true;

      while(ptsz < ptszEnd)
      {
         bool bDoCheck = true;
         for(size_t i = 0; i < sizeof(ptszSkip)/sizeof(ptszSkip[0]); i++)
         { /*check for skiped chars*/
            if(*ptsz == ptszSkip[i])
            {
               ++ptsz;
               bDoCheck = false;
               break;
            }
            if(*ptszEnd == ptszSkip[i])
            {
               --ptszEnd;
               bDoCheck = false;
               break;
            }
         }

         if(bDoCheck)
         {
            if(*ptsz != *ptszEnd) //as soon as find first not equal chars ,  return false
            {
               bRet = false; 
               break;
            }
            ++ptsz;
            --ptszEnd;
         }
      }
   }
   return bRet;
}

Ok, I know this is an old question, but I will post my code for the problem, but using 8bit chars, I think this does not change the overall solution : )

bool isPalyndrome(const char* aStr)
{

        if ( aStr == NULL ) return false;
        int size = strlen(aStr);
        --size;
        for( int i = 0; i < size/2; i++ )
        {
            if ( aStr[i] != aStr[size -1 -i] )
                return false;
        }
        return true;
 }

Very, very late ;-) this handles whitespace and number etc (closer to a real palindrome rather than byte symmetry)
 

static bool IsPalindrome(string subject)
{
  const int STEP_FORWARD = 1;
  const int STEP_BACKWARD = -STEP_FORWARD;
  const int BEFORE_START = -1;
  const int CHAR_AT_A_TIME = 1;
  const int COMPARE_EQUALS = 0;



  
  // assume its not a palindrome
  bool result = false;

  
  // how to compare
  CompareInfo ci = CultureInfo.CurrentCulture.CompareInfo;
  CompareOptions co =
    CompareOptions.IgnoreCase |
    CompareOptions.IgnoreKanaType |
    CompareOptions.IgnoreNonSpace |
    CompareOptions.IgnoreSymbols |
    CompareOptions.IgnoreWidth;

  
  // null strings are not palindromes
  if (subject != null)
  {
    int AFTER_END = subject.Length;
  
    // single letter words are palindromes
    result = (AFTER_END == 1 && IsPalindromeChar(subject[0]));
  
    // start the comparison points at valid characters
    int startOffset = GetNextValidCharacter(subject, BEFORE_START, STEP_FORWARD, AFTER_END);
    int endOffset = GetNextValidCharacter(subject, AFTER_END, STEP_BACKWARD, BEFORE_START);
  
    while (startOffset < endOffset)
    {
      result = ci.Compare(subject, startOffset, CHAR_AT_A_TIME, subject, endOffset, CHAR_AT_A_TIME, co) == COMPARE_EQUALS;
    
      if (!result)
        break;

      
      // move the comparison points towards each other
      startOffset = GetNextValidCharacter(subject, startOffset, STEP_FORWARD, endOffset);
      endOffset = GetNextValidCharacter(subject, endOffset, STEP_BACKWARD, startOffset);
    }
  }
 
  return result;
}

 
static int GetNextValidCharacter(string subject, int offset, int step, int bound)
{
  if (offset != bound)
    offset += step;

  while (offset != bound && !IsPalindromeChar(subject[offset]))
    offset += step;

  return offset;
}
 
static bool IsPalindromeChar(char c)
{
  return char.IsLetter(c) || char.IsDigit(c);
}

more on palindromes on my blog

Rasx, You are correct! One problem - you are dealing with an insane environment. People that work at Microsoft are inbread and will never listen to you. The inbreeding has created genetic freaks that can solve number puzzles on a white board whether this measures the value of a potential employee or not. And as you so rightly point out, the exercise is silly and shows the defect of the inbreeding.

 

bool is_palindrome(char *string) {
	int length = strlen(string);
	
	for(int i = 0; i < length / 2; ++i) {
		if (string[i] != string[length-i-1])
			return false;
	}
	
	return true;
}