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

21–30 of 128 posts

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

#21

Post by Latty »

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]

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

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

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

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

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

#22

Post by Latty »

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.

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

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

Of course, the original problem did state "lists" explicitly, so I guess you could just type check for lists, but that's really unpythonic and not useful in the real world.

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

#23

Post by fiedzia »

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…

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

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

#24

Post by skybrian »

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.

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

#25

Post by dpark »

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…

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

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

#26

Post by NicoJuicy »

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.

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

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

#27

Post by [deleted] »

fiedzia wrote: post #23
brudgers wrote: post #17

Earlier quoted context omitted.

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…

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

[deleted]

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

#28

Post by dragonwriter »

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…

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

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

#29

Post by brudgers »

fiedzia wrote: post #23
brudgers wrote: post #17

Earlier quoted context omitted.

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…

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

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.

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

#30

Post by contravariant »

NicoJuicy wrote: post #26
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.

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

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