Favorite Interview Question (Part 3)

From Part 2 we know that we have asked the candidate to interleave a linked list. So how do we evaluate how smart they are based on their answer?

The first and possible most important part of the "answer" is that they ask more questions.  There is no way they have enough information to solve the problem at this point.  Some typical questions that should be asked are do we care more about space or time?  Should the list be swapped in place or do you want a new list to come out?  And of course some clarifying questions on what exactly interleaving a linked list is.

The answers are that we want to optimize for both space and time. And we want the list to be interleaved in place.  So given that there are usually three stages of solution that candidates come up with.

First:

• Get the first item.
  
• Traverse the list to the last item and insert it after the first item.
  
• Move the pointer over the (original) second item.
  
• Get the new last item.
  
• Rinse and repeat.
  

This is a good starting point.  It allows you to make sure that can traverse a linked list, and then have a conversation about how to measure the speed of an algorithm.  Then I ask, OK but how could you improve it? (O(n^2) time, O(1) space).

Which leads us to the second solution:

• Create an array of all the items in the linked list.
  
• Pull from from the array and build up a new linked list.
  

This is a arguably better answer (given that we want to minimize both time and space) as there is no n^2 in either time or space.  It interesting to see the thought process that gets people here.  Some people, now that that are more familiar with the problem space, grasp it right away and some take some prodding. (O(n) time, O(n) space).

Now I ask them if it can be improved.  Because this is usually where people stop advancing.  So I give "points" for realizing that there probably is a better way to do this without worrying about if they are actually able to figure out the algorithm.  So now that we've established there there is a better way to do it, how do you do it?  Very few people figure it out.

• Traverse the list once to get the length
• Traverse to half way through the list
• Flip the links for the back half of the list, so if we had 1 -> 2 -> 3 -> 4 -> 5 we end up with 1->2 -> 3 <- 4 <-5
• Now we can build the new list in one pass

This is the best solution I have come up with (O(n) time, O(1) space).  If the candidate gets this one, I still ask if there is a way to do better, 1) because if there is a better way that would be cool to learn.  And 2) to see if they stick to their points when they think their are right, which is an important skill too.

Once we get to the best possible solution the candidate can come up with I like to have them then come up with test cases for their solution.  I have yet to see it but I would give big bonus "points" to someone who wrote the tests first and did TDD for the interview question.

So there it is, now I've ruined my favorite question and will have to come up with a new one.  Any ideas?