Thursday, August 28, 2008

A man, a plan, a canal - Panama!

Whilst viewing Gary Daniels and Evan Goldring - Mock whiteboard problem I noticed a strange thing. In the video they show an mock interview question and try to answer it. As Evan says in the video and afterwards his solution was not the best one. After this everyone posted their attempt (15 pages of comments at the moment).

The strange thing? not one is right! why? Gary hints towards the end that the solution needs to handle white spaces correctly - in effect suggesting the the function should calculate palindromes on the basis of words rather than byte symmetry. I'm off course not suggesting that my solutions are correct either, as the definition of palindrome was not defined fully enough for anyone to be able to judge if an answer is correct.

My first attempt ignored this hint and just went for a straightforward symmetry test:

static bool isPalindromeFirst(string subject)
{
bool result = false;

if (subject != null)
{
int endOffset = subject.Length - 1;
int midOffset = (int)Math.Ceiling(subject.Length / 2d);

for (int startOffset = 0; startOffset < midOffset; startOffset++, endOffset--)
{
result = (subject[startOffset] == subject[endOffset]);

if (!result)
break;
}
}

return result;
}
This solution appears generally correct for the byte symmetry approach, but I just don't feel happy with its lack of whitespace handling , so my second attempt is longer, but hopefully an evolutionary approach:


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



ps I'm sure "a" is a palindrome, but I suspect "b" is not... however this would mean getting into recognising words and all that entails...

result of running:



'(null)' palindrome? False
'' palindrome? False
'.' palindrome? False
'..' palindrome? False
'.,.' palindrome? False
'a' palindrome? True
'ab' palindrome? False
'aa' palindrome? True
'aaa' palindrome? True
'abc' palindrome? False
'aba' palindrome? True
'abca' palindrome? False
'abba' palindrome? True
'aabccbaa' palindrome? True
'a man, a plan, a canal - panama' palindrome? True
'a man, a plan, a canal - panama!' palindrome? True
'A Man, a Plan, a Canal - Panama' palindrome? True
'A man, a plan, a canal - Panama!' palindrome? True
'A man, a plan, a canal - Panamá!' palindrome? True
'A ma;n, a plan, a canal - Panamá!' palindrome? True
'A ma;;n, a plan, a canal - Panamá!' palindrome? True
'A ma;n, a plan, a canal - Pa;namá!' palindrome? True
'A ma;;n, a plan, a canal - Pa;;namá!' palindrome? True
'A ma;;n, a plan, a canal - Pa;;;namá!' palindrome? True
'!A man, a plan, a canal - Panamá!' palindrome? True
'!A man, a plan, a canal - Panamá' palindrome? True
'!!A man, a plan, a canal - Panamá' palindrome? True
'A man, a plan, a canal - Panamá!!' palindrome? True
'1' palindrome? True
'12' palindrome? False
'11' palindrome? True
'122' palindrome? False
'121' palindrome? True
'1221' palindrome? True
'12.21' palindrome? True
'..12.21' palindrome? True
Press any key to continue...

No comments: