Crossing the river with a wolf, a goat, and a cabbage

The firm I'm working with was in the process of hiring some new developers. I was asked to come up with some programming tasks they could ask candidates during the interviews. These were of the problem-solving type, ones where you need to write an algorithm and solve a particular problem. The interviewer sits with you during this process and assesses your problem-solving and communication skills. I've been on both sides of these kinds of interviews many times. In general I think they are a good idea. Problem-solving and good communication are the best skills a developer can have. These tests can give you an insight into both.

But here's the catch. The problem needs to be right and the interview conducted in the correct manner. Asking the developer to implement a distributed b-tree in 30 minutes is not really going to prove anything except that you're a big nerd. So we researched hard about what problems to give  candidates. We came up with a handful of programming tasks, roughly of equal difficulty that could realistically be completed in 45 minutes. Each interviewee was then given a random problem to solve and was encouraged to ask questions and  speak their thoughts (explain their reasoning?) as they were 'searching' for the solution.
 
When talking about this to another developer friend he told me how he had recently had a similar programming interview (with another firm) and failed. I asked him to describe the question he was asked and he told me it was done online with a website called 'codility' and that he had only 30 minutes to complete. He emailed me a summary of the problem and it was something along these lines:


Problem 'Count the cycle'
 
You are given an array of integers: int numbers[]
Each element in this array represents an index on the same array. Your algorithm needs to follow the path from index 0 and
count how many elements are 'stuck' in a cycle. Your function should return this count.
This is best explained in an example (array indexes start from 0):
numbers = {3,2,4,4,1}
Starting from index 0 you read its value(3) and jump to index 3. You then read this value(4) and jump to index 4 and so on.
So following this process you'll end up getting: '3,4,1,2,4,1,2,4,1,2,4...'
In the above the cycle it would be 1,2,4 and it should return 3.

Easy right? No... an extra constraint is that it needs to have a worst time complexity of O(n) and worst space complexity of O(1). The question also specifies that the input array does not count as 'space'. So basically you can modify it without incurring any space complexity hit.

Here's my trail of thought on this, the first time I read the problem:
 
Reading question... Reading question...
Oh this is way too easy. This is just a linked list in an array, just put stuff in another linked list and count backwards after the first...
 
3 minutes
 
Crap there is a space limit of O(1)! No way this can work! How can it be possible? Oh hold on... I can modify the array.. aha... Ok think... think...
 
5 minutes
 
I have to store some 'cycle' state in the array itself. Hmmm... crap 10minutes have passed already... ok focus. We need at least two sorts of flags. One when we are doing the first pass and another when we're stuck in the cycle counting nodes.
 
12 minutes
 
Ok ok... I think I got it. How about negating numbers on the first pass and stopping when you hit the first negative number? Then a second pass making numbers positive, this time counting until you hit the positive tail. Something like:

  int index = 0;
while (numbers[index]<0) {
  numbers[index] = -numbers[index]
  index = abs(numbers[index])
}
int count = 0;
while (numbers[index]>0) {
  numbers[index] = -numbers[index]
  index = abs(numbers[index])
  count++;
}
 

18 minutes
 
NO! This won't work if we have a zero! Balls... Ok maybe we can shift everything forward by adding 1... actually hold on we can shift everything forward on the first pass and then everything backwards on the second. Right yes this should work. I just need to add a large number to everything and then subtract it on the second pass. The large number can simply be the array length:

  int index = 0;
int size = length(numbers)
while (numbers[index]<size) {
  numbers[index] = numbers[index] + size
  index = numbers[index] - size
}
int count = 0;
while (numbers[index]>=size) {
  numbers[index] = numbers[index] - size
  index = numbers[index]
  count++;
}
 

25 minutes
 
Does this work? Let me write some tests... yep looks like it's fine. Is it time O(n)? Well it's really O(2n) but that’s fine as O(n)==O(2n) yep. Is it space O(1)? Yep same argument as for time.
 
30 minutes
Phew... Just made it in time... I wonder if I would have made it under pressure in a real interview? Probably not.
 
I didn't feel great with my solution having solved it with only seconds to spare. So I decided to pass it on to some other developers at work and see how they got on. So one guy solved it in about the same time as me (on a piece of paper) and two others spent almost a full day thinking about it and finally quit and came to ask me for the solution.
 
Does it mean anything? Am I better than my colleagues who couldn't solve it? While it does make me feel better about myself, the reality is that I was lucky to have a light bulb moment while the others didn’t. This doesn't mean that my way of thinking is better. I discussed this with one of the guys that couldn't get it and he told me that he was thinking of ways to solve it with the space constraint but he couldn’t figure out how to encode the 'cycle' information in the array itself. In fact, as soon as I gave him a small hint on shifting numbers he quickly got to a similar solution (he shifted the numbers twice forward instead of one forward and one back).
 
This is why I believe the choice of question is very important. Choosing the wrong question is like asking someone to solve the famous 'Crossing the river with a wolf, a goat and a cabbage' problem. Anyone who comes up with a right answer in a few minutes does so because:
1. He has seen/heard it before
2. He's lucky and had a eureka moment thinking 'hey the goat can cross back'
3. He's a farmer and has goats, wolves and cabbages crossing rivers all the time
 
The moral here is that the 'wolf/goat/cabbage' problem just like the 'Count the cycle' problem does not prove you're any better for the job or that you are more intelligent or that your problem-solving skills are any better. In fact, it doesn't show much at all.
 
So what should the interview programming questions look like then? In my view it's difficult to get it just right. The problem needs to be easy enough to dot in the time allocated but hard enough so not everyone can do it. It should avoid being a puzzle but instead be a problem where the candidate can show his/her problem-solving skills and algorithm design. Problems that can be broken down into multiple smaller ones tend to be better and so are ones which require the use of multiple datastructures types. Problems like: 
1. You have an array of random integers. Find the first non-duplicate number in the array in O(NlogN).
2. You have two sorted arrays of size N and M where N <= M. Output the intersection in O(N)
3. How can you implement a linked list in an array (fixed size limit).
 
I know. The above are not exactly rocket science but neither is the 'Count the cycle' problem once you solve the encoding puzzle. And as for the wolf/goat/cabbage problem the cabbage didn't ask to cross bridges anyway.

Disclaimer: this is in no way saying codility is a load of rubbish. I've worked on some of their sample problems and I think they're very good for filtering out candidates that have no idea about computer science. It still amazes me that sometimes we get someone with years of experience on his CV who cannot write a simple findMax(array) function. So codility is a great tool for filtering some of the worst. I just think that whoever uses codility or similar services needs to be careful about the problems they choose and try to stay away from bad ones like the above.

---