Why it’s hard for programmers to write a program to flatten a list? • Hacker News Board

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

#61

Post by cestith » Fri, Feb 24, 2017, 7:23 PM UTC

zzzcpan wrote: post #55

cestith wrote: post #35

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…

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.

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

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

#62

Post by franciscop » Fri, Feb 24, 2017, 7:24 PM UTC

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

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

#63

Post by dwc » Fri, Feb 24, 2017, 7:27 PM UTC

scotttrinh wrote: post #5

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 dat…

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

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

#64

Post by collyw » Fri, Feb 24, 2017, 7:27 PM UTC

valine wrote: post #58

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.

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

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

#65

Post by wz1000 » Fri, Feb 24, 2017, 7:28 PM UTC

ng12 wrote: post #51

wz1000 wrote: post #49

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 flatten(List ) Or something like List flatten(NestedList ) 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 y…

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.

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

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

#66

Post by dllthomas » Fri, Feb 24, 2017, 7:28 PM UTC

wz1000 wrote: post #49

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 flatten(List ) Or something like List flatten(NestedList ) 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 y…

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.

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

#67

Post by jsnell » Fri, Feb 24, 2017, 7:29 PM UTC

ghshephard wrote: post #37

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 l…

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.

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

#68

Post by dllthomas » Fri, Feb 24, 2017, 7:30 PM UTC

wz1000 wrote: post #65

ng12 wrote: post #51

Earlier quoted context omitted.

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.

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 o…

Not necessarily. See my bash solution in another comment :-D

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

#69

Post by alkonaut » Fri, Feb 24, 2017, 7:31 PM UTC

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

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

#70

Post by dllthomas » Fri, Feb 24, 2017, 7:32 PM UTC

dragonwriter wrote: post #28

brudgers wrote: post #14

Earlier quoted context omitted.

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 ? 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 Goo…

> 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 ? 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 >, which is somewhat problematic to type as anything but List given Java's lack of sum types.

Interfaces are (open) sum types. Or close enough for government work.