Why it’s hard for programmers to write a program to flatten a list?

I take many programming interviews at my current organisation. These days one of my favourite interview question is to flatten a nested list structure. I give user an input [1,[2,3], [4, [5,6]]] and ask them to write a program that will give output [1,2,3,4,5,6]. So, far I have asked this question to at least 20 candidates and 18 out of them have failed to write this program. I find this question better than canonical FizzBuzz problem as flattening a list is comparatively more involved problem.

This is how interview goes:

  1. I ask candidate to write a program that takes [1,[2,3], [4, [5,6]]] as input and return [1,2,3,4,5,6] as output. I specifically say you have to flatten a list.
  2. They can choose any programming language they like. Usually they are Java programmers so they end up choosing that.
  3. I ask them to write test case as well.

The common patterns I have noticed in most interviews:

  1. Candidate fail to write proper method signature. They get confused about what type of list they should use. Some start with List of integers List<Integer> ints. They fail to see how they will store a List<Integer> to a List<Integer>.
    public List<Integer> flatten(List<Integer> numbers)
  2. Some candidates start with a primitive array. Very quickly they realize array is fixed size data structure so they should use a List.
  3. They give method bad name like getList or processList etc. While explaining the problem, I explicitly mention that they have to flatten a list still they don’t use flatten as name of the method.
  4. Most programmers fail to get that they can recursion to solve the problem. Candidates who solved this problem get that they have to use recursion in a few seconds.
  5. Some programmers have hard time storing result in a List using the recursion approach. They use recursion but forget to store result. Most don’t know difference between recursion and tail recursion.
  6. Some programmers have hard time thinking how they should check instance is of some type.
  7. Most of them make flatten instance method. Programmers don’t think whether they should make method static. Programmers for some reason think static is bad.
  8. No one starts with a test. Most jump straight away to code. You have to pause them and ask can you please write down in plain English what you are trying to achieve.
  9. I tend to give a lot of help and pointers to the candidate. I want to make sure that they solve this problem. Candidates end up taking close to 45-60 mins to finish the solution. Some fail to get it working even after an hour.
  10. No one thinks about generic program so that solution will work across all types.
  11. No one used Java 8. Candidates tell they have heard some features of Java 8 but they don’t use it. I doubt adoption of Java 8 has reached a critical mass.

I am not sure what makes this problem tough for candidates. May be pair programming with interviewer just does not work. What are your thoughts?