VoltInsider

An Interesting Hiring Interview Question

July 8th, 2010

I was chatting with one of my buddies who has been working at Microsoft for nearly 10 years as a software developer. We both started at Microsoft in the same week and worked on Internet Explorer version 3. Here’s an interview question he has used for years: “Write a function which prints a list of the longest palindromes in a string.”

He uses this question for both software development positions and for SDET (engineers who write test automation) positions. The first thing he looks for is if the candidate qualifies exactly what this question means. As stated, it is (deliberately) ambiguous. He also gains some insight into the candidate’s communication skils at this point. Anyway, here’s what he means by the question. Suppose the input string is:

abbadbbeebb

The output should be:

abba
bbeebb

Palindromes are strings that read the same in both diections. For example, “aba” and “cddc” are palindromes. Notice that the output does not contain strings “bb”, “ee”, and “beeb” because they are contained within larger palindromes. The trick is to realize that to find the longest palindromes in a string, you have to work from the inside out. The middle of a palindrome will be either two letters which are the same (as in “cddc”), or a single letter (as in “aba”). Once you identify the midpoint of a potential palindrome, you work outward, checking to see if the two current end characters are the same. If the characters are the same, you keep working outward because you want the longest palindrome.

Once a candidate has figured out the algorithm, then they’ve got to implement it. Like most hiring managers, my buddy does really care if the candidate uses C, Java, C#, JavaScript, Visual Basic, or whatever. If a candidate gets this far, then my buddy will ask questions about the performance of the algorithm, including “Big O” questions.

Entry Filed under: Interviewing