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

101–110 of 128 posts

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

#101

Post by ghshephard »

zzzcpan wrote: post #98
ghshephard wrote: post #96

Earlier quoted context omitted.

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…

> 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 Don't jump to conclusions. You will not find such people, because those are very basics. Understanding of $_[0] is necessary to use arguments in Perl functions and understanding of @{...} is necessary to use array references as lists.

Challenge accepted.

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

#102

Post by andr3w321 »

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.

Some python 2

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

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

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

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

#104

Post by brudgers »

pcmonk wrote: post #44
brudgers wrote: post #29

Earlier quoted context omitted.

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

Aren't list-of-lists more like trees where values are only stored on the leaves? In this case, aren't {pre,in,post}order all the same?

The example input in the article is:

  [1,[2,3], [4, [5,6]]]
It happens to be representable as a binary tree. Indeterminacy regarding whether or not that is accidental or intentional is due to underspecification of the interview problem. The first time I read a description of Linkedin using logs as the fundamental data structure (for what turns out to be Kafka I later learned) I had an epiphany that there is no such thing as a generic simple data structure living in the wild because data is data because it has semantics, without semantics it is just noise.

To me, it looks like the root node is |1|.

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

#105

Post by brudgers »

collyw wrote: post #45
brudgers wrote: post #29

Earlier quoted context omitted.

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

Sorry, are you suggesting that "flatten a list" leads to microservices?

If the flattening a list is taken seriously, then it might. Or it might not. Taking the exercise seriously might be a better gauge of a person's long term professional potential than if that person treats the question as frivolous because there is a whole lot of things like testing and error handling and refactoring that might be discarded by a programmer who treats their craft frivolously.

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

#106

Post by brudgers »

mannykannot wrote: post #72
collyw wrote: post #34

Earlier quoted context omitted.

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

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

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

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

#107

Post by cestith »

pcmonk wrote: post #44
brudgers wrote: post #29

Earlier quoted context omitted.

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

Aren't list-of-lists more like trees where values are only stored on the leaves? In this case, aren't {pre,in,post}order all the same?

For the trivial case in which the nesting always gets deeper at the end like in the OP, perhaps. Take a look at nodes and leaves from my Perl5 example elsewhere in the thread.

    my $nested = [ 1, [ 2, 3 ], [ 4, [ 5, 6, [ 7, [ 8, [ 9, 10 ] ], 11, 12, [ 13, [ 14, [ 15, 16 ], 17 ], 18 ], 19 ], 20 ] ] ];
What the code does when there are leaves and nodes intermixed at arbitrary depths in arbitrary order from left to right determines the final order of your leaves. Are you pre-flattening all the more deeply nested lists and then building your flat list, or are you walking along a certain nesting level and deferring anything that's not a leaf to later flattening?

I gave two examples. One produces a flattened list like this:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
The other products this:

    1 2 3 4 5 6 20 7 11 12 19 8 13 18 9 10 14 17 15 16
Are either of those outside the specification set forth?

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

#108

Post by tzs »

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…

A similar trivial approach works in Perl:

  sub flatten
  {
      my @in = @{$_[0]};
      my @out;
      while (@in) {
          my $item = shift @in;
          if (ref $item eq 'ARRAY') {
              unshift @in, @$item;
          } else {
              push @out, $item;
          }
      }
      return \@out;
  }
Input is a reference to the source list, output is a reference to the flattened list.

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

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

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

#109

Post by amyjess »

klibertp wrote: post #16
amyjess wrote: post #10

Earlier quoted context omitted.

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]

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

Thank you for the correction!
Post reply on HN