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

https://shekhargulati.com/2017/02/24/why-its-hard-for-programmers-to-write-a-program-to-flatten-a-list/

by shekhargulati • 9 years ago

33 120 9 years ago

njd• 9 years ago

I'm a retired data architect and C developer with 36 years of professional experience. In my opinion, this is not how you find an appropriate candidate. It would be better to ask substantive questions that are related to the thing you are making. What does this person bring to the team? How will the team receive this person? Has this person delivered something of substance in the recent past that would convince you that he/she would succeed on your project? How was this person an asset on their previous job?

fiedzia6• 9 years ago

Those are questions for juniors. Most likely they had no previous job at all. The only thing they can bring is potential, and this question tests it rather well.

cableshaft4• 9 years ago

Doesn't stop people from asking these questions of people at all levels. I still get asked these coding questions pretty much every interview I have had, and I have almost a decade of programming experience, and have even been lead programmer on some projects (without the title).

I've been asked a barrage of these questions for senior positions, even.

Especially sucks because I don't usually program terribly fast or well in an interview environment, so I look worse than I actually am, and often get put on the defensive in these interviews, which I absolutely hate.

brudgers9• 9 years ago

It does not really test potential because a junior trained in Java has poor tools for flattening a list because idiomatic Java would not represent hierarchical data structure as a nested list. Idiomatic Java would use tree and node objects. Idiomatic Java also prefers arrays over lists for sequential data.

An experienced programmer might look at the problem and choose a better tool: a different language or call a service or rewrite the offending code that produces a nested list or any one of a dozen things that are not bashing away with the hammer of Java.

ng122• 9 years ago

Sounds to me like that's a really god way to hire people who are really good at bullshitting.

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".

walshemj• 9 years ago

yes its a very artificial Q a better one might be how would you use a computer to measure how efficient 100 different toilets are :-)

scotttrinh• 9 years ago

When reading this, my immediate instinct was to say: "Easy!"

  import { flattenDeep } from 'lodash';

  const flat = flattenDeep([1,2[3], [4, [5,6]]);

Not sure why employers care about developers being able to write utility functions from scratch, when that is not (typically) the job developers are hired for.

Having said that, I lament the issues that the OP brought up: poor naming, unfamiliarity with their language's data structures, etc. Those are issues that will come up. Especially naming.

dpark• 9 years ago

Not sure why employers care about developers being able to write utility functions from scratch, when that is not (typically) the job developers are hired for.

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.

dwc2• 9 years ago

Having said that, I lament the issues that the OP brought up: poor naming, unfamiliarity with their language's data structures, etc. Those are issues that will come up. Especially naming.

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.

fiedzia6• 9 years ago

Some reasons:

* Nobody required this from them before.

* Recursion is rarely used to write business logic, most common thing programmers write and learn. Same for static methods and being generic.

* Type checking is done by compiler for them, so no surprise that they don't know how to do it.

* Relatively few people go beyond minimal, so adoption of is java 8 is low

Overall, it looks like a good question to pick up the best developers - assuming this is what you want.

dethswatch• 9 years ago

To me, this smells like: * Required before: I only ever code at work. * Recursion: I didn't get any/much theory in school * Type checking: I don't know my language very well. * Going beyond minimal: agreed- try not to hire them.

klibertp3• 9 years ago

The word "Java" really should be in the title.

Whatever else you say about it, Java is one of the entry-level languages. It's no wonder there are many entry-level programmers among its users. It's obviously a trade-off, as you get that many more candidates to choose from, compared to for example OCaml, Clojure or Erlang programmers. On the other hand, a percentage of people who can flatten a list is greater in users of the more "advanced" languages.

If you want to have a good signal to noise ratio: avoid languages used in "Programming 101" like a plague and languages which are currently fashionable. This way you'll get candidates who learned the language by themselves, in most cases after learning and mastering their previous language.

Becoming a programmer is a long process. Depending on the person, the time required to learn a single programming language may be shorter than the time needed to really master all the essential programming skills. Which I think explains why there is a correlation between good programmers and people who know more than one programming language.

brudgers9• 9 years ago

One of the problems is that for Java the task is underspecified: Flatten a list of what? Sure this one is integers, is that always the case or should the list take <object>?

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)))))

and if they were taught the JVM rather than Java

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

and with J

  flatten =: [: ; <S:0

I'd bet that the interviewer would not know if it was wrong or right. Which is the same issue of open endedness that the candidate faces.

klibertp3• 9 years ago

is going to disorient novices who in a high stress situation at the short end of an asymmetrical relationship.
What the question really measures is how lucky the candidate was in their education.

Yes! Exactly! This is the other point I wanted to make[1], thanks for doing it for me :)

flatten =: [: ; <S:0

Nice, I was playing with J quite a lot but somehow missed the spread word (for the curious: http://code.jsoftware.com/wiki/Vocabulary/scapco)

[1] In my comment here: https://news.ycombinator.com/item?id=13725095

dragonwriter4• 9 years ago

One of the problems is that for Java the task is underspecified: Flatten a list of what? Sure this one is integers, is that always the case or should the list take <object>?

Well, I don't Java much, but I think that even if the result List is just integers, the source list has to be (invalid syntax) List<Integer | List<Integer>>, which is somewhat problematic to type as anything but List<Object> given Java's lack of sum types.

contravariant4• 9 years ago

I suppose a fair counter question would be how on earth the interviewer ended up with a couple of nested heterogeneous lists in Java, instead of a simple Tree data structure.

cableshaft4• 9 years ago

But...but Python is starting to become a Programming 101 language, and Python is awesome :( :(

maxander• 9 years ago

The coming glut of Python devs is going to be a problem. Its an excellent language, I've used it for work for years, but its almost too powerful. A minimally skilled programmer can write mostly-functional Python programs while still not having the slightest notion of what they're doing, meaning the pressure for a developer to understand and improve their craft is often minimal.

If I were responsible for hiring developers into a Python post, I would only consider candidates to could show (ideally substantial) work in some other, strongly-typed, lower-level language. It hardly even matters if they haven't seen Python, a decent developer can become a useful Python programmer in a few hours. Python experience does not teach or demonstrate a decent understanding of software structure.

contravariant4• 9 years ago

Couldn't you just do something like:

    def flatten(x):
        if isIterable(x):
            for y in x:
                yield from flatten(y)
        else:
            yield x

Well, technically this is a generator, but it's easy enough to put its result in a list.

amyjess2• 9 years ago

I found this on Stack Overflow a while back, and I've been using it in my Python code since then:

    [item for sublist in l for item in sublist]

fiedzia6• 9 years ago

That's not generic and would not qualify as valid answer for this question.

klibertp3• 9 years ago

That wouldn't work in this case: it only works with lists where every element is also a list and it only flattens one level deep.

With these constraints, there are quite a few interesting techniques, for example in Scheme you can apply append:

    (apply append list-of-lists)

or in Python you can use reduce with add operator:

    reduce(op.add, list_of_lists) # op == operator module

And anyway, even if it's not the constrained version, the solution is indeed trivial, for example in Erlang:

    flatten(L) -> flatten(L, []).

    flatten([], Acc)            -> Acc; 
    flatten([[] | T], Acc)      -> flatten(T, Acc); 
    flatten([[_|_]=H | T], Acc) -> flatten(T, Acc ++ H);
    flatten([X | T], Acc)       -> flatten(T, Acc ++ [X]).

(please don't mind the inefficient use of ++, it's a toy example...)

It can get a bit more complex in a statically typed language, especially if you want to have static guarantees (no down-casting from Object), but it's still doable in a couple of minutes...

...is what this post - and discussion - is not about.

It's trivial once you get it, of course. But it's also true that it's almost impossible to figure it out on your own during a stressful interview if you didn't get it beforehand. It's so easy to forget that. We all once struggled with some concepts, and we all went through many discoveries of facts, techniques, and skills we didn't know existed, much less that we needed them.

What I want to say is that the beginners who fail to answer this question are not bad, they are just beginners. It's ok to reject them right now, but it's not ok to post an article suggesting that "programmers find it hard to solve trivial problems even with my help". It's not programmers, but beginner programmers; it's not trivial problem, just relatively widely known one; and it may well be the help was insufficient.

Latty2• 9 years ago

As others have pointed out, that only flattens one level (which, admittedly, is a much more useful thing most of the time - arbitrarily deeply nested structures are relatively rare).

If you do want to do this, the better method is:

  itertools.chain.from_iterable()

That has the advantage of being lazy, as opposed to a list comprehension, and has the potential to be more optimised. It also doesn't rely on the somewhat obscure and relatively hard to read nested list comprehension syntax.

Docs: https://docs.python.org/3.6/library/itertools.html#itertools...

contravariant4• 9 years ago

Like others have pointed out you should have used recursion. Although, if you really wanted to you can make one similar to yours that doesn't (explicitely) use recursion. That results in the following:

    flatten = (lambda f: lambda *args: 
     (lambda x: lambda *args2: f(x(x))(*args2))
     (lambda x: lambda *args2: f(x(x))(*args2))(*args))(
        lambda f: lambda l: [item for sublist in l for item in f(sublist)] if isIterable(l) else [l]
    )

fiedzia6• 9 years ago

Sure, the point is that writing this requires knowing more than most candidates do.

Latty2• 9 years ago

The definition of isIterable here is a bit fun. In most real world cases, you end up needing to specify it down a bit:

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

Is the most common one. The first clause to check if it's an iterable (as per the collections.Iterable abstract base class - for those unfamiliar, basically a check for the `__iter__()` method), the second to check it's not a string, which is also iterable, but generally you don't want to split into individual letters - and if you do, you'll need to add more checks as strings split to other 1-length strings that are still iterable, making an infinite loop.

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.

NicoJuicy• 9 years ago

That's almost the exact same code as I thought, but it's an extension on c# and uses 'is Enumerable'. Which language is this?

contravariant4• 9 years ago

It should work in python 3.3+, provided you make a method isIterable to detect whether something is an iterator or not. For lower versions of python you can't use the phrase 'yield from', so you need to iterate over flatten(y) manually and yield each element.

andr3w321• 9 years ago

Some python 2

    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)

falcolas• 9 years ago

I'd personally change `if type(x) == list` to `if isinstance(x, (list, tuple, set))` to catch all common iterables and their subclasses.

gumby• 9 years ago

I am not sure what makes this problem tough for candidates.

Most people aren't programmers, and sad to say, most people employed writing code are not programmers.

I find trivial problems like this are good interview questions. What the person asks, says and does tells me a lot about what they would be like to work with. And it's not like you're using some bizarre datastructure or obscure CS case: this is an ordinary workaday problem. So it's not a "trick" or one-upsmanship, just "do you know your tools?"

linkedlist007• 9 years ago

#python code

def flat(x):

  if type(x) == type([]) and len(x)==1:

    return flat(x[0])

  if type(x) == type([]) and len(x)>1:

    return flat(x[0]) + flat(x[1:])

  else:

    return [x]

skybrian• 9 years ago

A slight rewrite makes this a reasonable question in Java. A list of lists has a tree structure and asking candidates how to print the items in a tree in depth-first order is reasonable.

The main issue is that you'd never use a list as a tree node in Java. There would be an explicit Node class of some sort.

I do ask a question where one possible solution is to define your own Node class, build a tree, and print it out. But you can also solve it without even realizing you're working with a tree.

cestith6• 9 years ago

This is pretty trivial. It doesn't require recursion, although the recursive implementation is much simpler. The spec doesn't specify breadth-first or depth-first. The example input offered comes out the example output offered either way. The spec in the article also doesn't mention making it generic, so I don't see how that's points away for programmers who tackle the input and output given as integers only.

Here's some pretty trivial Perl5 to do recursive or iterative versions.:

    use strict;
    use warnings;
    use Data::Dumper ();
    my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ];

    sub flatten {
        my @f;
        push @f, (ref $_ ? flatten( $_ ) : $_ ) for @{ $_[0] };
        return @f;
    }

    sub flatten2 {
        my $n = shift;
        my ( @f, @queue1, @queue2 );
        my $pass = 0;

        for ( @$n ) {
            if ( ref $_ ) {
                push @queue1, $_;
            } else {
                push @f, $_;
            }
        }
        until ( $pass > 0 && scalar @queue1 == 0 && scalar @queue2 == 0 ) {
            for ( @queue1 ) {
                if ( ref $_ ) {
                    push @queue2, @{ $_ };
                } else {
                    push @f, $_;
                }
            }
            @queue1 = @queue2;
            @queue2 = ();
            $pass++;
        }

        return @f;
    }

    print STDOUT (join ' ', flatten( $nested )) . "\n";
    my @flat = flatten( $nested );
    print Data::Dumper::Dumper \@flat;

    print STDOUT (join ' ', flatten2( $nested )) . "\n";
    my @flat2 = flatten2( $nested );
    print Data::Dumper::Dumper \@flat2;

zzzcpan3• 9 years ago

You can make it nicer and more reliable with Perl:

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

However, this is not something a Java/OO programmer would be comfortable with, especially under the stress of the interview. As it's a bit higher level and closer to a functional way of thinking, than OO.

cestith6• 9 years ago

I started to use map, but I've been told time and again anything that does is not a trivial example because you start by explaining what map does.

Anyway, I'm glad the first response to "this is trivial in Perl" is another, simpler Perl response rather than "Perl is dead".

alain_gilbert• 9 years ago

Non recursive algo with python:

  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)

ghshephard3• 9 years ago

I think a lot of this is based on your experience with languages. If you have exposure to a list/iterator native language like python, you come up with solution in a few seconds, even if you aren't even remotely a programmer. Other languages might not lend themselves to so obvious a solution.

The perl example cited here kind of blows my mind compare to the trivial python approach:

  def flatten(lst):
      rlst=[]
      for x in lst:
          if type(x)==list:
              for y in(flatten(x)):
                  rlst.append(y)  
          else:
              rlst.append(x)
      return (rlst)

jsnell• 9 years ago

You perhaps missed that there were two solutions (+ test infrastructure) in that Perl post. You Python code is the moral equivalent of the three-line "flatten" function in the Perl example. The long "flatten2" function was doing it without recursion.

ghshephard3• 9 years ago

The part that was/is challenging/mind blowing for me to grok was:

   sub flatten {
        my @f;
        push @f, (ref $_ ? flatten( $_ ) : $_ ) for @{ $_[0] };
        return @f;
    }

The implicit $_, and whatever @{ $_[0]} does, is challenging enough that I bet I could find people who had been using perl to do work for years who wouldn't be able to explain what was happening here at first glance, even if they could eventually work it out/write it themselves with a bit of effort.

That's what I meant by native iterative/sequence languages like python lend themselves to easy solutions for this type of question, even for people who aren't programmers, whereas you really need to be a programmer to come up with something as powerful as the above.

Put another way, doing a complex joined query might be a trivial question for someone who knows even the slightest amount of SQL, but would be beyond most novice python developers (without of course just using a SQL select statement...)

I will admit the (dense) perl solution certainly has its own beauty that the more drawn out python solution is lacking, though I'm guessing it could be written in a pythonic way itself...

Qcombinator• 9 years ago

The perl example cited here kind of blows my mind compare to the trivial python approach

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(@$_) : $_, @_ }

tzs• 9 years ago

A similar trivial approach works in Perl:

  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;
  }

Input is a reference to the source list, output is a reference to the flattened list.

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.

canadian_voter• 9 years ago

Gee, that's almost exactly what I got:

  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

I think that's easier to read than the following, and appears to run slightly faster as well?

  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]

dllthomas9• 9 years ago

{ echo [; sed s/[][]//g; echo ]; }

valbaca• 9 years ago

This is the TYPE of answer I like to see.

nolite• 9 years ago

$ irb 2.3.1 :001 > [1,[2,3], [4, [5,6]]].flatten

=> [1, 2, 3, 4, 5, 6]

BOOM!

mmcconnell1618• 9 years ago

Am I the only one who saw the string representation of the nested array and said "you could just walk it character by character and ignore the brackets and commas?"

franciscop2• 9 years ago

That is indeed, depending on the context (you know the strings won't contain commas OR that it should be split in the commas), one way to do it in Javascript ( https://github.com/franciscop/umbrella/blob/master/src/plugi... ):

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

throwaway7293• 9 years ago

Rubric item #10: "No one thinks about generic program so that solution will work across all types."

you fail.

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

wz10002• 9 years ago

I don't really write Java, but I fail to see any easy and robust way to assign a type to the flatten function in Java.

Is this the signature you would expect in a solution to this?

    List<Integer> flatten(List<Object>)

Or something like

    List<Integer> flatten(NestedList<Integer>)

with a definition for NestedList?

Is there even a way to define something like NestedList without coercing back and forth from Object? Is there a way you can do this so that you don't have to basically reimplement List?

ng122• 9 years ago

I would either use Object to be quick, or implement a NestedListItem with isNumber(), getNumber(), getList().

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.

wz10002• 9 years ago

Personally, I think this problem shows why sane type systems are useful.

In Haskell

    data NestedList a = Single a | Nested [NestedList a]
    -- Or equivalently, type NestedList = Free []

    flatten :: NestedList a -> [a]
    -- This is pretty much the only reasonable definition of flatten the compiler will accept given this type
    flatten (Single a) = [a]
    flatten (Nested xs) = concatMap flatten xs

    -- or given the Free variation of NestedList
    -- flatten = retract

dllthomas9• 9 years ago

Also not a Java programmer, but my approach would probably involve two classes implementing the nested list interface. One would hold a list, the other an integer (or maybe parameterize over that, depending on the context).

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.

alkonaut5• 9 years ago

The fact that "int or list of int" isn't sanely representable in any concise way in the mainstream OO languages is a sign that perhaps this isn't a great example problem for a Java interview.

Obviously you can do this with brute forcing the sum type with some class hierarchy (ugh) or make the algorithm accept some List<object> or Java "List" interface.

Both of those options are pretty terrible.

I think the intents of the question are good - see if the candidates understand the importance of naming, signature, tests.

There has to be a question that does this and doesn't immediately have the subject crying over the type system.

dragonwriter4• 9 years ago

The fact that "int or list of int" isn't sanely representable in any concise way in the mainstream OO languages is a sign that perhaps this isn't a great example problem for a Java interview.

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.

alkonaut5• 9 years ago

Yes obviously Java is going to be the tool at hand, but to keep focus on the good aspects of this exercise (naming, testing, etc) perhaps it would be best to have a problem that has a good solution in Java.

If the subject does this property with generics that simple sum type alone requires writing several classes just to represent the sum type.

It's not clear from the article what the input is. What signature I can use depends on what the input data is. Is it a string rep of the nested list? Can I assume it's any type I want such as my own NestedList?

ScottBurson• 9 years ago

It's trivial, of course, in Common Lisp:

  (defun flatten (x)
    (if (listp x)
        (reduce #'append (mapcar #'flatten x))
      (list x)))

hibikir• 9 years ago

The first problem I see is that your rubric is a complete shibboleth: The candidate has to guess what you are evaluating. In some interviews, all they want is working code. Others want performance. Others care about testing: Based on the question, I'd not be sure of what you want. There's places where writing the test first will, if anything, be detrimental. Others will love it. You have to be clear on expectations.

The second issue is that a question like that is not even remotely fair across programming languages. What about types? Is a list of lists a sensible, idiomatic practice in that language? It's a trivial question that makes sense in Lisp, and it won't faze a Scala programmer. People are probably going to come up with a good, concise solution in Python or Ruby. In Java, lists of lists are often considered awful things, the generics syntax is torture, and you'll find candidates that will actually think less of you for asking them to write that: If a list of lists happens, it's normally an intermediate step in a computation, and you'd not like to pass, or return, anything with that type signature to anything that isn't a private method.

So compare the very short, boring program that you need in a lisp, with the array of questions a professional Java programmer would have to ask you to make sure that you don't ding them with your list of questions, along with the extra knowledge of how to build generic functions.

Instead, why not ask a simple, yet realistic problem that can be solved in more than one way? A question where you can give someone points for doing good things, instead of subtracting points for not doing exactly what you consider the right solution to be. For extra success, make your rubric public.

I do a lot of interviews as part of my work, and I have noticed that, even for the same problem, little things like rubric clarity and tailoring requirements to the language make big difference in pass percentage on screens. Moreover, they also make a difference when they get to on site interviews if the rubrics all come from the same basic principles (and if they don't, you should change that).

Do yourself and your candidates a favor and abandon this question if you are interviewing people across languages.

whorleater• 9 years ago

The second issue is that a question like that is not even remotely fair across programming languages. What about types?

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.

kazinator2• 9 years ago

Or maybe they want a candidate who asks: what are the functional and non-functional requirements for this task?

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.

valine• 9 years ago

It took me about 5 minutes to solve this in Swift. My first thought was to use a recursive function that takes an array with a generic type. I'm not sure that would have been my first thought under the stress of an interview. Its very likely I would have frozen and wouldn't have produced anything at all.

collyw4• 9 years ago

It took me an embarrassingly long 15 minutes in Python. I had already seen the mention of recursion in the description, so I hope I would have realized that it was needed. (I am guessing I probably would have looked at recursion at the point when I realized that there were multiple levels of nesting, and not just one).

franciscop2• 9 years ago

I fail to see how some people see this as a contrieved test. It's an issue many programmers have probably found at some point as opposed to fizzbuzz or other artificial tests. Probably other questions related to your business would also be good, but using this as a first and quick filter sounds about right IMO.

In Javascript, depending on your context, it could be as easy as:

     // Only if we're using numbers or other variables without commas on them
     // divide them, remove empty things and make them numbers again
     const flatten = arr => arr.toString().split(/[\s,]+/).filter(e => e).map(n => 0+n);

Or a slightly more complex and "proper" one as:

    // Recursively flatten an array
    const flatten = arr => arr.reduce((all, one) => all.concat(one instanceof Array ? flatten(one) : one), []);

throwaway7293• 9 years ago

The complaint isn't that it's contrived in general. The complaint is that it's a bad question if you're interviewing Java developers (because Java's type system is impoverished, but that's really beside the point).

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.

alkonaut5• 9 years ago

No one thinks about generic program so that solution will work across all types.

Is this even possible to do generically in Java or C#?

You can do it for objects so that it works for ALL types (i.e "object"), but you can't make it work generically for a type T for any T.

That's why this is such an excellent example of why sum types really are useful.

Writing the flatten interface without generics (Java List or c# IEnumerable) is not generic. If you do that it will accept a heterogeneous list - which we probably don't want.

throwaway7293• 9 years ago

Yes you can code up sum types in the object system of Java or C#.

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.

alkonaut5• 9 years ago

Agree 100%.

Title of blog post could be "How do I keep failing to convey the basic constraints and requirements of a programming interview question?"

artmageddon• 9 years ago

I haven't done any interview prep in quite awhile and I feel like even a question like this would leave me dead in the water, given what the post laid out.

jasonkostempski• 9 years ago

If you give the option of any language and they choose Java to work on a single instance of an untyped array, they should be disqualified.

alkonaut5• 9 years ago

This is pretty easy actually: since the question is horribly vague on what the input type actually IS, I'm going to just assume it's a string.

So flatttening the list is just a string split on all delimiters. Done.

My Java is rusty but something like input.split("\[\],"). Done.

It's an answer of exactly the same quality as the question...

catdog• 9 years ago

As nobody seems to have posted a Java solution yet:

  import java.util.List;
  import java.util.stream.Collectors;
  import java.util.stream.Stream;
  import static java.util.Arrays.*;
  
  public class Flatten {
  
      public static void main(String[] args) {
          List<Object> nested = asList(1, asList(2, 3), asList(4, asList(5,6)));
          List<?> flat = flatten(nested);
          System.out.println(nested);
          System.out.println(flat);
      }
  
      public static List<?> flatten(List<?> nested) {
          return nested.stream()
                  .flatMap(x -> x instanceof List ? flatten((List<?>) x).stream() : Stream.of(x))
                  .collect(Collectors.toList());
      }
  }

I would say it's a bit of an odd question if you mainly target Java as it's very uncommon to encounter such a construct there, alone because the type system can't handle it properly.

SwellJoe• 9 years ago

Java never fails to astound in its verbosity, even today, even with much better utility functions for things like lists (flatMap/collect are new to me). But, now that I've taken the time to read through it, I see the actual flatten function isn't actually all that different an implementation from the Perl and Python variants other folks have suggested. But, Java sure does make you work for that list data structure.

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.

vivaamerica• 9 years ago

Type-safe, bonus unit test.

   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);
           }
   
       }
   
   }

relics443• 9 years ago

After reading the problem, I spent 5 minutes writing a performant, optimized, generic, recursive solution in Java (technically Kotlin). I don't consider that to be one the reasons that I'm a good engineer.

silverwind• 9 years ago

  $ node
  > [1, [2, 3], [4, [5, 6]]].toString().split(',').map(n => Number(n))
  [ 1, 2, 3, 4, 5, 6 ]

kazinator2• 9 years ago

A somewhat more interesting challenge is: write code to lazily flatten a list. It must instantly return, and access the original structure lazily. Each atom is fetched from the original list when the lazy list is accessed. No continuations allowed; at most lexical closures.

My C solution is in this file:

http://www.kylheku.com/cgit/txr/tree/lib.c

functions lazy_flatten_scan, lazy_flatten_func and lazy_flatten.

QML• 9 years ago

This is straight out of my homework for an introductory to CS class. If I can recall, we need an IF statement to detect whether the element IS INT, else length of list. Then just add [Int] or list[:] to the new list.

Ok point being: I didn't believe what I was learning was relevant to industry, in particular linked lists.

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

Related Stories