12 ms·

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

33 points by shekhargulati 10y ago

njd 10y 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?
- fiedzia 10y 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.
  - cableshaft 10y 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.
    - collyw 10y ago
      Have you ever needed to flatten a list in your career outside exams and interviews?
      - iguanayou 10y ago
        Yes.
      - scarface74 10y ago
        Yes. Something like: List<List<Blah>> records; We would send a request off to multiple services, wait for all the responses and then the front end would sometimes need all of the lists and other times need it flatten. How would I do it? var allitems = records.SelectMany(b => b).ToList();
      - mannykannot 10y ago
        I am not an enthusiast of this approach to recruiting, but to be fair, the purpose of the question is not to find someone to flatten lists. It is reasonable to ask, if a programmer cannot flatten a list, in what sense is that person a programmer? Putting aside the question of whether this is a good approach to recruiting, if this question is being failed with any regularity, it raises some interesting and important questions about the innate difficulty of programming and/or the methods by which it is taught.
        brudgers 10y ago
        If the person flattens a list with the: Google Copy Paste Algorithm, are they a programmer? Are they more or less of a programmer if instead they use racket or clojure's built-in =flatten=?
        mannykannot 10y ago
        It is the cases of failure that are interesting and informative, and if the methods you mention are the only ways a person can solve the problem, that counts as a failure - as I mentioned, this is not actually about flattening lists.
      - zzzcpan 10y ago
        "Have you ever needed to flatten a list in your career outside exams and interviews?" I had to write this function to flatten a tree of expressions, so I could sort them by precedence, etc and fold them into a tree. I already had a bunch of higher-order primitives for constructing a parser and that was basically a lazy hack for me to get expressions parsed. I eventually implemented a proper expression parser, that was basically the same thing, but produced a flat list from the beginning.
  - brudgers 10y 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.
    - fiedzia 10y ago
      > An experienced programmer might look at the problem and choose a better tool: a different language Come on, you are not going to call Haskell or Python to flatten a list in your Java. > or call a service I know we have "micro" services now, but really? Sending serialized data to ListFlatteningService to get deserialized FlattenedList? > or rewrite the offending code Something may produce it because it makes sense it its context, while it doesn't for you. No offence here.
      - deleted 10y ago
        [deleted]
      - brudgers 10y ago
        I make no claim to being a good programmer or having high potential (of any sort but the wasted), just the ability to occasionaly mimic those who are. Charged with flattening lists, I'd write my Java in Clojure. (flatten [1 [[2] [[3 4] [5 [6]]]]]) as much of it as I could because it would be less work and easier to read and maintain and debug. Since nested Java lists are isomorphic with trees, there's more than one way to deserialize them: inorder, preorder and postorder. Flattening deserializes in preorder. Expecting different consumers of the nested list to deserialize it in different ways might be a reason that producing a nested list makes sense in a particular context. Once we start talking about "consumers of the nested list" we are using the language of services. That, for better or worse, is a road that currently tends to lead to micro-services.
- ng12 10y 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 10y 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 :-)
deleted 10y ago
[deleted]
scotttrinh 10y 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 10y 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.
- dwc 10y 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.
fiedzia 10y 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 10y 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.
klibertp 10y 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.
- brudgers 10y 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.
  - klibertp 10y 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 http://code.jsoftware.com/wiki/Vocabulary/scapco) [1] In my comment here: https://news.ycombinator.com/item?id=13725095 https://news.ycombinator.com/item?id=13725095
contravariant 10y 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.
- amyjess 10y 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]
  - fiedzia 10y ago
    That's not generic and would not qualify as valid answer for this question.
  - klibertp 10y 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.
gumby 10y 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?"
ghshephard 10y 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 10y 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.
  - ghshephard 10y 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...
    - zzzcpan 10y ago
linkedlist007 10y 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 10y 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.
cestith 10y 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;
- zzzcpan 10y 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.
  - cestith 10y 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".
dllthomas 10y ago
{ echo [; sed s/[][]//g; echo ]; }
- valbaca 10y ago
  This is the TYPE of answer I like to see.
nolite 10y ago
$ irb 2.3.1 :001 > [1,[2,3], [4, [5,6]]].flatten => [1, 2, 3, 4, 5, 6] BOOM!
mmcconnell1618 10y 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?"
- franciscop 10y 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/plugins/args/args.js#L17 https://github.com/franciscop/umbrella/blob/master/src/plugi... ): return args.toString().split(/[\s,]+/).filter(/* ... */);
- throwaway729 10y 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 ;-) )
wz1000 10y 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?
- ng12 10y 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.
  - wz1000 10y 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
    - dllthomas 10y ago
      Not necessarily. See my bash solution in another comment :-D
- dllthomas 10y 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.
alkonaut 10y 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.
- dragonwriter 10y 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.
  - alkonaut 10y 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 10y ago
It's trivial, of course, in Common Lisp: (defun flatten (x) (if (listp x) (reduce #'append (mapcar #'flatten x)) (list x)))
hibikir 10y 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 10y 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.
- 10y ago
valine 10y 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.
- collyw 10y 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).
franciscop 10y 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), []);
- throwaway729 10y 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.
alkonaut 10y 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.
- throwaway729 10y 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.
  - alkonaut 10y 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 10y 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 10y 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.
deleted 10y ago
[deleted]
deleted 10y ago
[deleted]
alkonaut 10y 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 10y 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 10y 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 10y 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 10y 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 10y ago
$ node > [1, [2, 3], [4, [5, 6]]].toString().split(',').map(n => Number(n)) [ 1, 2, 3, 4, 5, 6 ]
kazinator 10y 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 http://www.kylheku.com/cgit/txr/tree/lib.c functions lazy_flatten_scan, lazy_flatten_func and lazy_flatten.
QML 10y 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.

33 points by shekhargulati 10y ago

njd 10y 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?

fiedzia 10y 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.
- cableshaft 10y 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.
  - collyw 10y ago
    Have you ever needed to flatten a list in your career outside exams and interviews?
    - iguanayou 10y ago
      Yes.
    - scarface74 10y ago
      Yes. Something like: List<List<Blah>> records; We would send a request off to multiple services, wait for all the responses and then the front end would sometimes need all of the lists and other times need it flatten. How would I do it? var allitems = records.SelectMany(b => b).ToList();
    - mannykannot 10y ago
      I am not an enthusiast of this approach to recruiting, but to be fair, the purpose of the question is not to find someone to flatten lists. It is reasonable to ask, if a programmer cannot flatten a list, in what sense is that person a programmer? Putting aside the question of whether this is a good approach to recruiting, if this question is being failed with any regularity, it raises some interesting and important questions about the innate difficulty of programming and/or the methods by which it is taught.
      - brudgers 10y ago
        If the person flattens a list with the: Google Copy Paste Algorithm, are they a programmer? Are they more or less of a programmer if instead they use racket or clojure's built-in =flatten=?
        mannykannot 10y ago
        It is the cases of failure that are interesting and informative, and if the methods you mention are the only ways a person can solve the problem, that counts as a failure - as I mentioned, this is not actually about flattening lists.
    - zzzcpan 10y ago
      "Have you ever needed to flatten a list in your career outside exams and interviews?" I had to write this function to flatten a tree of expressions, so I could sort them by precedence, etc and fold them into a tree. I already had a bunch of higher-order primitives for constructing a parser and that was basically a lazy hack for me to get expressions parsed. I eventually implemented a proper expression parser, that was basically the same thing, but produced a flat list from the beginning.
- brudgers 10y 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.
  - fiedzia 10y ago
    > An experienced programmer might look at the problem and choose a better tool: a different language Come on, you are not going to call Haskell or Python to flatten a list in your Java. > or call a service I know we have "micro" services now, but really? Sending serialized data to ListFlatteningService to get deserialized FlattenedList? > or rewrite the offending code Something may produce it because it makes sense it its context, while it doesn't for you. No offence here.
    - deleted 10y ago
      [deleted]
    - brudgers 10y ago
      I make no claim to being a good programmer or having high potential (of any sort but the wasted), just the ability to occasionaly mimic those who are. Charged with flattening lists, I'd write my Java in Clojure. (flatten [1 [[2] [[3 4] [5 [6]]]]]) as much of it as I could because it would be less work and easier to read and maintain and debug. Since nested Java lists are isomorphic with trees, there's more than one way to deserialize them: inorder, preorder and postorder. Flattening deserializes in preorder. Expecting different consumers of the nested list to deserialize it in different ways might be a reason that producing a nested list makes sense in a particular context. Once we start talking about "consumers of the nested list" we are using the language of services. That, for better or worse, is a road that currently tends to lead to micro-services.
ng12 10y 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 10y 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 :-)

deleted 10y ago

[deleted]

scotttrinh 10y 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 10y 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.
dwc 10y 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.

fiedzia 10y 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 10y 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.

klibertp 10y 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.

brudgers 10y 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.
- klibertp 10y 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 http://code.jsoftware.com/wiki/Vocabulary/scapco) [1] In my comment here: https://news.ycombinator.com/item?id=13725095 https://news.ycombinator.com/item?id=13725095

contravariant 10y 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.

amyjess 10y 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]
- fiedzia 10y ago
  That's not generic and would not qualify as valid answer for this question.
- klibertp 10y 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.

gumby 10y 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?"

ghshephard 10y 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 10y 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.
- ghshephard 10y 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...
  - zzzcpan 10y ago

linkedlist007 10y 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 10y 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.

cestith 10y 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;

zzzcpan 10y 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.
- cestith 10y 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".

dllthomas 10y ago

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

valbaca 10y ago
This is the TYPE of answer I like to see.

nolite 10y ago

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

mmcconnell1618 10y 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?"

franciscop 10y 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/plugins/args/args.js#L17 https://github.com/franciscop/umbrella/blob/master/src/plugi... ): return args.toString().split(/[\s,]+/).filter(/* ... */);
throwaway729 10y 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 ;-) )

wz1000 10y 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?

ng12 10y 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.
- wz1000 10y 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
  - dllthomas 10y ago
    Not necessarily. See my bash solution in another comment :-D
dllthomas 10y 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.

alkonaut 10y 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.

dragonwriter 10y 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.
- alkonaut 10y 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 10y ago

It's trivial, of course, in Common Lisp: (defun flatten (x) (if (listp x) (reduce #'append (mapcar #'flatten x)) (list x)))

hibikir 10y 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 10y 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.
10y ago

valine 10y 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.

collyw 10y 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).

franciscop 10y 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), []);

throwaway729 10y 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.

alkonaut 10y 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.

throwaway729 10y 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.
- alkonaut 10y 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 10y 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 10y 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.

deleted 10y ago

[deleted]

deleted 10y ago

[deleted]

alkonaut 10y 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 10y 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 10y 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 10y 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 10y 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 10y ago

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

kazinator 10y 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 http://www.kylheku.com/cgit/txr/tree/lib.c functions lazy_flatten_scan, lazy_flatten_func and lazy_flatten.

QML 10y 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.