Gary Daniels and Evan Goldring - Mock whiteboard problem

Posted By: The Channel 9 Team | Aug 24th, 2004 @ 12:44 PM

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

Tags: MS Personalities

Rating:

Views (244,513)

Comments (119)

Downloads

Jeremy 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

rasx
Programmer/Analyst III, 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.

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

}

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

rasx
Programmer/Analyst III, 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.

Maurits
AKA Matthew van Eerde

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

Maurits
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.)

Gerard O'Donnell

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

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