Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

Gary Daniels and Evan Goldring - Mock whiteboard problem

Download

Right click “Save as…”

During an interview for a technical position at Microsoft your interviewer might turn to you and ask you to write some code, or work out a problem on the whiteboard.

Here's a mock whiteboard session to see what an interviewer looks for during that stage of the interview.

This is a question made up for Channel 9 intended to demonstrate what is expected in an interview. There are many possible solutions and the answer is only a sample answer. Keep in mind that Evan Goldring (the interviewee) told us after the camera is off that he didn't answer the question with the best possible solution.

Do you have a better solution? Leave it here! Who knows, maybe a recruiter will email you and ask for your resume. Smiley

Tag:

Follow the Discussion

  • Jeremy WJeremy W that blogging guy
    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 Smiley

    edit: btw, the way Evan thought through everything was very good. Made me want to practice this before my onsite Wink
  • rasxrasx Emperor of String.Empty
    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.


  • Chris PietschmannCRPietschma​nn Chris Pietschmann
    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;

    }

  • MauritsMaurits AKA Matthew van Eerde
    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.
  • rasxrasx Emperor of String.Empty

    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.

  • MauritsMaurits AKA Matthew van Eerde
    oopsie - s1 used for two different purposes.  Rename the first occurrence s0.
  • MauritsMaurits AKA Matthew van Eerde
    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

  • MauritsMaurits AKA Matthew van Eerde
    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)
  • MauritsMaurits AKA Matthew van Eerde
    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

  • MauritsMaurits AKA Matthew van Eerde
    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
  • MauritsMaurits AKA Matthew van Eerde
    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;
    }

  • rpgrpg
    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 Wink


    #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?
  • ATAT

    // 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 Wink
                        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 Wink
     
    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 Sad

  • bonemanboneman Who, me?

    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.
  • barlo_mungbarlo_mung w00t
    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.
  • PeterFPeterF Aragon IT
    What happened to good old recursiveness? Wink

    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;
     }
    }

  • PeterFPeterF Aragon IT
    Sorry, somehow felt compelling to be original Wink

    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" Wink

  • MauritsMaurits AKA Matthew van Eerde

    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;

    }


  • PeterPeter Peter
    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.
  • MauritsMaurits AKA Matthew van Eerde
    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
  • MauritsMaurits AKA Matthew van Eerde
    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 Smiley:

    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;
    }
    -------

  • Chris PietschmannCRPietschma​nn Chris Pietschmann
    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 Wink. 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
  • ATAT
    // 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 Wink

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

     CString chars(buff);
     return chars.MakeReverse().CollateNoCase(buff)==0;
    }
  • rasxrasx Emperor of String.Empty
    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...
  • ezuezu

    I love this kind of exercies Big Smile. 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

  • MauritsMaurits AKA Matthew van Eerde
    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.

  • MauritsMaurits AKA Matthew van Eerde
    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;
    }
  • MauritsMaurits AKA Matthew van Eerde
    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;
    }

  • MauritsMaurits AKA Matthew van Eerde
    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)
  • MLML

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


    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?

  • Brice ItBrice It Email Brice
    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
    }
  • Brice ItBrice It Email Brice

    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);

        }

      }

    }

  • PeterFPeterF Aragon IT
    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.
  • xml-blogxml-blog I am what I am and that's all that I am.

    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;
       }
    };

  • MauritsMaurits AKA Matthew van Eerde
    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. Crying

    versus
  • MauritsMaurits AKA Matthew van Eerde
    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!!!
  • Sigfrido Rodríguez Santosidenty Identy
    I Unknown Assembly

    Models & COnceps & Good Languages i need

    i++ i* <#&x+0/> i not need
  • ATAT
    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 Wink
  • 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;
    }

  • MauritsMaurits AKA Matthew van Eerde
    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

  • ZippyVZippyV Fired Up

    Channel 9 should have a 'weekly coding challenge'.

  • jjjj J.J.

    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;
    }

  • jjjj J.J.

    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();

    }

  • Sven GrootSven Groot Don't worry... I'm a doctor.

    #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.

  • fabulousfabulous .NET Developer, unofficial Evangelist, geek
    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.
  • fabulousfabulous .NET Developer, unofficial Evangelist, geek
    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

  • rpgrpg
    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;
    }

  • Skewtzsc00ter Always in motion the future is..
    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 Wink). 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 Smiley

    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.

     

  • mikosoftmikosoft Evolution
    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
  • guydotnetxmlwebservicesguydotnetxm​lwebservices guydotnetxm​lwebservices
    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 Sad

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

    I could sent my code for palindrome function Sad

    Thanks you.
  • The Channel 9 TeamThe Channel 9 Team 5 guys from Redmond
    To watch the videos as soon as they are put up, either visit the home page every day, or get an RSS News Aggregator and subscribe to the Channel 9 Video RSS feed at http://channel9.msdn.com/rss.aspx?ForumID=14&Mode=0
  • 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?)

  • MauritsMaurits AKA Matthew van Eerde
    To be pedantic your alphaOnly parameter also allows underscores as well as alphabetic and numeric characters.
  • michkapmichkap Sorting It All Out
    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);
    }

  • MauritsMaurits AKA Matthew van Eerde
    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
  • michkapmichkap Sorting It All Out

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

  • MauritsMaurits AKA Matthew van Eerde
    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)
  • MauritsMaurits AKA Matthew van Eerde
    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 Smiley


    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;
     }
  • Philip FitzsimonsFigment​Engine Figment​Engine
    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;
    }

     

    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;
    }

     

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.