Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

shekhargulati.com

Post reply on HN
Print view View original

31–40 of 128 posts

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

#31

Post by contravariant »

brudgers wrote: post #14
klibertp wrote: post #8

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…

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…

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.

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

#32

Post by bushin »

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.

More precisely List :) That would be trivial in functional languages.

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

#33

Post by contravariant »

amyjess wrote: post #10
contravariant wrote: post #9

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.

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]

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

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

#34

Post by collyw »

cableshaft wrote: post #6
fiedzia wrote: post #4

Earlier quoted context omitted.

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.

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…

Have you ever needed to flatten a list in your career outside exams and interviews?

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

#35

Post by cestith »

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;

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

#36

Post by LgWoodenBadger »

brudgers wrote: post #17
fiedzia wrote: post #4

Earlier quoted context omitted.

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.

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

Idiomatic Java hasn't preferred Arrays since the advent of the Collections API back in 1.2.

Idiomatic Java as of 1.8 now has flatMap on Streams, which all Collection implementations provide.

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

#37

Post by ghshephard »

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)

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

#38

Post by iguanayou »

collyw wrote: post #34
cableshaft wrote: post #6

Earlier quoted context omitted.

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…

Have you ever needed to flatten a list in your career outside exams and interviews?

Yes.

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

#39

Post by dragonwriter »

bushin wrote: post #32
dragonwriter wrote: post #28

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

More precisely List :) That would be trivial in functional languages.

It would be trivial in languages with sum types and support for recursive signatures/constructors, which doesn't describe all statically-types functional languages. And there's no reason such a language would have to be functional, though most are.
Post reply on HN