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

The absolute hardest thing about hiring developers is hiring people who I can trust to write code. Most applicants are just not adequate programmers and any other redeeming qualities they have can't overcome that core deficiency. I need people who can look at different ways to solve a problem, implement an approach that makes sense, and explain why it does. I need code reviews to be about architecture decisions and correctness not lessons on how to write code. If someone can't do that I really don't care how well they can sell themselves as an "asset".

I wonder if part of this test is to see if a programmer will choose a language that's appropriate for it. Picking the right tool for the job and whatnot.

If the interviewee guesses whether or not security, speed, memory use, portability, maintainability or anything else are important, maybe they will do the same in production code.

Leaving out that information from the question is going to disorient novices who in a high stress situation at the short end of an asymmetrical relationship. I suppose if the interviewer lets them Google, then it is a fair test (and objectively, not Googling before writing code is probably the best criterion for failing miserably).

What the question really measures is how lucky the candidate was in their education. If they were taught in Racket rather than Java:

  (flatten '((1) ((2 3 ((4) (5 6)))))

  (flatten [[1] [[2 3 [[4] [5 6]]]]]

  flatten =: [: ; <S:0

That's because the Perl version is a two-for-one deal: just for fun, Cestith threw in a non-recursive version too. The 'trivial' recursive approach is more or less equivalent to the Python:

  sub flatten { map ref($_)? flatten(@$_) : $_, @_ }

  sub flatten
  {
      my @in = @{$_[0]};
      my @out;
      while (@in) {
          my $item = shift @in;
          if (ref $item eq 'ARRAY') {
              unshift @in, @$item;
          } else {
              push @out, $item;
          }
      }
      return \@out;
  }

The main difference is that I opted to manipulate a copy of the source list in place to expand sublists rather than recurse.

As others have noted, a recursive version using map can be written much more concisely.

  def flatten(nested_list):
      output_list = []
      for elem in nested_list:
          if type(elem) == list:
              output_list.extend(flatten(elem))
          else:
              output_list.append(elem)
      return output_list

  import collections

  def flatten(nested_list):
      if isinstance(nested_list, collections.Iterable):
          return [a for i in nested_list for a in flatten(i)]
      else:
          return [nested_list]

I know it's verbose because of type definitions, and because there's no bare functions in Java, but it sure does balloon up small programs with a lot of boilerplate, and tends to hide the point of the program behind stuff that doesn't look like the purpose of the program.

   import org.junit.Test;
   
   import java.util.ArrayList;
   import java.util.Arrays;
   import java.util.List;
   import java.util.stream.Collectors;
   import java.util.stream.Stream;
   
   import static junit.framework.TestCase.assertEquals;
   
   public class FlattenList {
   
       @Test
       public void test() {
           // [1, [2, 3], [4, [5, 6]], [7, [8, [9, 10]]]]
           final FlattenableList<Integer> list = new FlattenableList<>();
           list.add(new SingleFlattenable<>(1));
   
           list.add(new ListOfSingles<>(Arrays.asList(2, 3)));
   
           list.add(new Flattenable<Integer>(){{
               add(new SingleFlattenable<>(4));
               add(new ListOfSingles<>(Arrays.asList(5, 6)));
           }});
   
           list.add(new Flattenable<Integer>(){{
               add(new SingleFlattenable<>(7));
               add(new Flattenable<Integer>(){{
                   add(new SingleFlattenable<>(8));
                   add(new ListOfSingles<>(Arrays.asList(9, 10)));
               }});
           }});
   
           assertEquals(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), list.flatten());
       }
   
       public static class FlattenableList<T> {
   
           final List<Flattenable<T>> list = new ArrayList<>();
   
           void add(final Flattenable<T> item) {
               list.add(item);
           }
   
           List<T> flatten() {
               return list.stream().flatMap(Flattenable::flatten).collect(Collectors.toList());
           }
   
       }
   
       private static class Flattenable<T> {
   
           final List<Flattenable<T>> contents = new ArrayList<>();
   
           Stream<T> flatten() {
               return contents.stream().flatMap(Flattenable::flatten);
           }
   
           void add(final Flattenable<T> content) {
               contents.add(content);
           }
   
       }
   
       private static class ListOfSingles<T> extends Flattenable<T> {
   
           final List<T> list;
   
           ListOfSingles(final List<T> list) {
               this.list = list;
           }
   
           @Override
           Stream<T> flatten() {
               return list.stream();
           }
   
       }
   
       private static class SingleFlattenable<T> extends Flattenable<T> {
   
           final T item;
   
           SingleFlattenable(final T item) {
               this.item = item;
           }
   
           @Override
           Stream<T> flatten() {
               return Stream.of(item);
           }
   
       }
   
   }

    [item for sublist in l for item in sublist]

   isinstance(el, collections.Iterable) and not isinstance(el, str)

Of course, the original problem did state "lists" explicitly, so I guess you could just type check for lists, but that's really unpythonic and not useful in the real world.

    def flatten(x):
        def flatten_generator(x):
            if type(x) == list:
                for y in x:
                    for z in flatten(y):
                        yield z
            else:
                yield x
        return list(flatten_generator(x))

    assert(flatten([1, [2,3]]) == [1,2,3])

    ary = [1, [2,3], [4, [5,6]]]
    print flatten(ary)

    return args.toString().split(/[\s,]+/).filter(/* ... */);

you fail.

(I don't intend to be mean to you, I intend to be mean to the question ;-) )

Because of the reasons you listed in your next paragraph:

> poor naming, unfamiliarity with their language's data structures, etc. Those are issues that will come up. Especially naming.

No one actually wants a candidate to write "flatten". They want the candidate to demonstrate that they can work through a small problem and write something sane and functional. Utility functions tend to be small and reasonable to put together in about an hour.

With that said, I think this is a mediocre question because no one would create this list of lists-or-ints in Java. If presented well, the problem might be decent. If presented poorly, a lot of junior candidates would likely fail even if they're good candidates.

Indeed. And those things came up in writing a fairly simple utility function, so they're going to come up later in some large codebase.

While you're seldom hiring programmers to write utility functions like this, this kind of test shows whether the candidates have a basic familiarity with topics that will definitely come into play in their day-to-day work. I regularly run into "professionals" who can't structure their code in sensible ways, who don't even try to name things well, don't think about edge cases, etc. As it turns out, you don't want these people gluing together library calls either, because you'll end up with a mess on your hands.

    sub flatten {
       map { ref $_ eq 'ARRAY' ? flatten(@$_) : $_ } @_ 
    }

  def flatten(array):
      queue = [array]
      result = []
      while len(queue) > 0:
          item = queue.pop(0)
          if isinstance(item, list):
              for sub_item in item:
                  queue.append(sub_item)
          else:
              result.append(item)
      return result

  a = [1,[2,3], [4, [5,6]]]
  print 'input:', a, '\noutput:', flatten(a)

If you're going to ask this question of a Java developer, you should carefully indicate what form the input takes. Heterogeneous collections are canonical in dynamically typed languages, and also in reasonable typed languages as recursive sum types. But in Java you're stuck between awkward subtyping / dynamic casting, or coding up your own definition of a heterogeneous collections. And in particular, the wording of the question suggests List<Object>, which is terrible style in Java land.

The real take-away is that Java's type system stinks for this sort of thing, and the standard libraries don't offer much help. But if you're interviewing Java developers, you shouldn't start off by asking them to writing terribly non-idiomatic Java code.

OTOH, if you are going to be using Java dealing with real world problems, many of which have aspects that are not neatly representable in Java's type system, some test of how you deal with the mismatch of that type system with a problem statement may be appropriate.

A lot of whether this is appropriate in an interview goes beyond the language used to what the job entails and what you are trying to learn about the candidate from the response.

The one thing I do like about this problem is it shows when TDD is useful. If you try to write a test case first the representation problem will be the very first thing you run into, and the code will mostly follow from there.

Drawing analogy to lisp, we need to be able to answer "is this a list or an atom?"

Note that the actual structure involved is "really" a rose tree.

But are you allowed to do that? The problem write-up makes it sound like you're supposed to be ingesting the interviewer's input. So, how did the interviewer code up sum types? With tons of nasty casting out of List<Object>, or with a slightly less terrible object hierarchy mimicking sum types?

That's what makes the question terrible. It implies you're supposed to be coding against an interface, but in the allowed language (Java) it's totally non-obvious what the interface is.

I'll submit this criteria for coding question: if a big chunk of your candidates can't write down the friggen type of the program you want them to implement -- and if two reasonable people could write down extremely different types for the same question -- then your question is bad and you should throw it out.