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

51–60 of 128 posts

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

#51

Post by ng12 »

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.

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

#53

Post by dwc »

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…

This wasn't stated as a test for Java programmers. Rather that most programmers chose to implement in Java because they were familiar with it.

And you have to ask, if they were familiar with Java then why didn't they choose one of the idiomatic approaches you suggested? I mean, the "list" part is not an internal requirement so you could easily build a tree/node structure on input...

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

#54

Post by franciscop »

mmcconnell1618 wrote: post #48

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

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/plugi... ):

    return args.toString().split(/[\s,]+/).filter(/* ... */);

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

#55

Post by zzzcpan »

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.

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

#56

Post by hibikir »

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.

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

#57

Post by dragonwriter »

alkonaut wrote: post #50

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 or Java "List" interface. Both of those options are pretty terrible. I think the intents of the que…

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

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

#58

Post by valine »

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.

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

#59

Post by collyw »

maxander wrote: post #41
cableshaft wrote: post #15

Earlier quoted context omitted.

But...but Python is starting to become a Programming 101 language, and Python is awesome :( :(

The coming glut of Python devs is going to be a problem. Its an excellent language, I've used it for work for years, but its almost too powerful. A minimally skilled programmer can write mostly-functional Python programs while still not having the slightest notion of what they're doing, meaning the pressure for a developer to understand and improve their craft is often minimal. If I were responsible for hiring develo…

I have seen a fair bit of Python code in the style of Java (as well as some completely unreadable Python). Just because you can be useful in Python doesn't mean you are writing good idiomatic Python code. And if you aren't doing that, then what is the point in using Python?

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

#60

Post by brudgers »

dwc wrote: post #53
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…

This wasn't stated as a test for Java programmers. Rather that most programmers chose to implement in Java because they were familiar with it. And you have to ask, if they were familiar with Java then why didn't they choose one of the idiomatic approaches you suggested? I mean, the "list" part is not an internal requirement so you could easily build a tree/node structure on input...

See my answer to the sibling to your comment.
Post reply on HN