Microsoft's JobsBlog

zoë,

Were solutions sent to you by email considered as well? I had sent a response by email and was wondering...

"We took a look at all the solutions that people came up with for the whiteboard problems and submitted to us through Channel 9 and have picked out a few of the best."

And, zoë, the contact me link is broken. I wasn't going to use it... But it's broken.

That said, I'm sure the people who won are smart enough to find your email address!

Yes - we looked at all solutions that were sent via email and submitted through Channel 9. Russ actually was one of the people that sent his info through email.

Thanks Jeremy for the heads up on the broken link.

;-) He-he ..
How about submissions to your blog and bugs found before video was released (beta testing ;-) ?

What was Russ' solution?

Thanks Moon Gals !

Maurits,

My submission was in C#, similar in idea to most peoples suggestions, of cleaning the string and reversing it ... Apart from providing test cases I suppose the difference to most suggestions was the use of char.IsLetterOrDigit() to strip out punctuation and whitespace.

Thanks Russ! (what are you doing up so late? ;)

One last thing to get off my chest about palindromes.

One thing that bugs me about the whole are-numbers-palindromes question is that palindromicity is not a mathematical property at all. It changes with the base you write the number in!

Take a "palindromic" number like 101. If you write it in hex notation, that's 65. If you write it in binary, it's 1100101.

On the other hand, take the six-hexadecimal-digit HTML color-code for "white" - ffffff. That's palindromic - but if you convert it to decimal you get 16777215!

So palindromicity, for numbers, is a function of *both* the value *and* the base (though 10 is a reasonable default)
BOOL isPalindromicNumber(int value, int base = 10);

This would allow a web developer to pass base 16 for hex, or someone analyzing bitfields to pass base 2.

Russ, is that similar to this solution?
http://blogs.chroniclesdesign.com/rbuckton/archive/2004/09/16/154.aspx

I don't reverse the string though, i use a counter to increment the first and last index. the operation is approx O(n/2) where n is the length of the string. It assumes a) null is not a palindrome, b) 0-length strings are palindromes, and c) palindromes consist of letters and numbers but not whitespace or punctuation. I also handle upper/lowercase conversion on a character by character basis only when necessary.

You're welcome everyone and thanks for continuing a great conversation!

Maurits, It wasn't that Late in the UK!

Ron, It's similar but I took a slightly simpler approach.

Because Palindromes are Palindromes regardless of case,whitespace or punctuation I simple took the passed string and converted it ToLower(). Then I foreached char on that string and if the char passed IsLetterOrDigit() I added it to a new string.

I reversed the new string into a temporary string, and if they were the same, return true.
I'd post the source but it's on my work machine.

Efficiency wise, its not the best way to do it, but for the purpose of a Whiteboard question I wrote it in the best way to explain and easily read ... and we all know that some of the best code is the hardest to read :)

When I get back to work I'll post my Function on your Blog Ron.

Russ,

In the case of my code I was looking at it from an efficiency perspective, although I'm sure it could run much faster if I used unsafe code and pointers in C#. Calling ToLower() on the whole string is expensive, especially on larger strings, and == on string is also expensive.

To concatenate characters to a new string, and to perform the secondary comparison is costly, and will at least double the time for the operation. By using indexes for the beginning/end character you can increase performance because a) you're cutting the length of the operation in half and b) you're not performing any concatenation.

I know using indexes is slower than pointers, but I wanted to stay away from unsafe code blocks in that example.

Hi,

Just some brain teasers for everyone...

Has anyone considered that palindromes differ according to the character encoding used to create the source palindrome string? (i.e. the word "MOM" in english would not be the same in Russian, which represents some single letters using multiple letters.) How would you go about compensating for this difference? Remember, the example assumed a TCHAR data type being passed into the palindrome routine. Assuming unicode issues are taken care of by the correct compilation settings, how would you adjust your solution to accomodate character encodings? Or would you need to worry about this? If you depend upon a starting and ending index, and the language encoding you are working with maps a single character onto may characters, how would you compensate your index logic? In this case, the string would be a palindrome, but the word would not be spelled the same forward and backward. Just something to chew on...

Second, localization context has not been considered. There are some languages that express sentences and/or concepts using a single word or phrase (latin comes to mind). How would one handle localization context?

Brian

Ron,

I've posted my Function on your Blog ...