Comment Feed for Gary Daniels and Evan Goldring - Mock whiteboard problem (TheChannel9Team on Channel 9)

Re: Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

variable — Fri, 13 Nov 2009 05:47:21 GMT

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.

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Philip Fitzsimons — Thu, 28 Aug 2008 13:30:23 GMT

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

Re: Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

José Marcelo Auler — Tue, 12 Aug 2008 03:20:11 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

IgorZ — Thu, 29 Mar 2007 07:18:38 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

emreknlk — Sat, 04 Nov 2006 21:02:15 GMT

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

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

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

IanB — Sat, 25 Feb 2006 04:26:35 GMT

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

}

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

bentan — Thu, 29 Dec 2005 04:42:46 GMT

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.

Re: a ruby way

ton_chat — Fri, 25 Nov 2005 18:15:27 GMT

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.

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

vivemoire — Tue, 04 Oct 2005 03:55:20 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

ritzbit — Mon, 03 Oct 2005 15:01:26 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

DoggettCK — Tue, 09 Aug 2005 15:17:38 GMT

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.

[code language="c++"]
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;
}
[/code]

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)

[code language="c++"]
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
    }
}
[/code]

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Kosher — Tue, 02 Aug 2005 19:41:27 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

RuneSpyder — Mon, 01 Aug 2005 07:00:58 GMT

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;

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

fxbrain — Mon, 23 May 2005 08:06:50 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Maurits — Thu, 28 Apr 2005 21:55:05 GMT

And here's the iterative version:
[code language="C#"]
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;
}
[/code]

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Maurits — Thu, 28 Apr 2005 21:20:41 GMT

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

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

[code language="C#"]
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);
}
[/code]

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)

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

michkap — Thu, 28 Apr 2005 19:59:42 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Maurits — Thu, 28 Apr 2005 17:55:54 GMT

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:

[code language="C#"]
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);
}
[/code]

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

Posted driver app in Sandbox

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

michkap — Thu, 28 Apr 2005 15:37:19 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Maurits — Mon, 25 Apr 2005 23:28:05 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

SEWilson — Tue, 05 Apr 2005 02:11:51 GMT

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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

HippieGeek — Mon, 04 Apr 2005 22:01:55 GMT

'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

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

Jos104 — Mon, 04 Apr 2005 20:40:07 GMT

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;

}

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

peterpeter — Mon, 28 Mar 2005 15:56:41 GMT

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

What do you think?

Re: Gary Daniels and Evan Goldring - Mock whiteboard problem

homerjay — Fri, 25 Mar 2005 22:34:40 GMT

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.