The fact that the first couple of people to consider the problem didn't find efficient solutions doesn't mean that finding efficient solutions is a super-hard problem. Grenander wasn't really interested in the 1-dimensional problem but in the (I think distinctly harder) 2-dimensional problem, and I don't think he was really an algorithms guy. (That's not a polite way of saying he wasn't very smart; he clearly was, but I don't think finding optimal algorithms for things was what he was most interested in.)

For the avoidance of doubt, I don't think you're likely to get much insight into interview candidates by seeing whether they spot the most efficient solution to a problem like this unaided -- even an extremely strong candidate might just happen not to think of a good approach, especially under stressful interview conditions. (It might still be a useful question if a less adversarial approach is taken -- discuss the problem with the candidate, get a sense of how they think, and nudge them in a helpful direction if they get stuck -- or if the only question is whether the candidate can find and implement any approach, which for this problem I think any reasonably competent software developer should be able to do since you can basically just translate the question into straightforward but inefficient code that does the job.)

I'm not sure whether we actually disagree or not, but I do think you may be overstating the difficulty of this particular problem.

[1]: https://leetcode.com/problems/maximum-subarray/

    highest_total = 0
    for all i from 0 to length-1:
        for all j from i+1 to length-1:
            total = 0
            for all k from i to j-1:
               total += data[k]
            highest_total = max(total, highest_total)
    return highest_total

[1]: https://en.wikipedia.org/wiki/Maximum_subarray_problem

This is O(N^3) because iterating over index pairs is O(N^2) and doing the sum is O(N).

At least there seems to be some general agreement (within the thread) that, while not super-hard -- it's still basically a "eureka problem" -- that is, even among what we may consider to be adequately good engineers -- some will get the visual solution more or less right away; but a fair percent (25 or more) won't.

And that's given ideal circumstances -- working alone and in unhurried circumstances. Throw in the (considerable) distraction of having to think aloud in front of other people (who themselves may not exactly be providing the most relaxing vibe, to say the lease), and all the other stress that comes with interviewing -- and I'll bet that 25 percent failure rate rises quite considerably, in turn.

And in many cases -- if you fail just one of these "eureka" problems -- and maybe fail to provide the expected canned response to a "behavioral" question or two -- than that's pretty much all it takes. To be considered, you know, "not a fit".

As to why I jumped the gun -- fatigue, probably, from being fed a few too many "cute" problems like these.

Now if you'll excuse me I need to grind out some dynamic programming problems.

I don't disagree with the main point, but FAANG companies' interview questions are available all over the net. In many cases (most?) they'll literally tell you what they are ahead of time, so it's a lot more of a filter for grit than a filter for computer science aptitude.

Eg: I know for a while Google was pretty keen on asking about A* algorithms. A friend who worked there mentioned that to me. Not having a CS degree myself, my first reaction was that was a very "either you know it or you don't...maybe you can figure it out, but that's not gonna be fun" kind of situation.

At some point i saw the material Google gives out. A* was literally listed there as something that they were likely to ask.

Now, it does mean preparing for a very specific interview, which not everyone (or even most people) would be willing to do. And today I don't think Google has the reputation to pull that stunt off for much longer. But a couple of years ago, if you really wanted that free cafeteria? Its a small price to pay.

It's a little harder than that. That would be for the screening interview. But on-site, you'll get several algorithm interviews (I had 3 in two such companies, plus 2 system designs). The recruiter told me that you could fail one of the interviews, but you have to nail the four others.

Even if you are well-prepared, I find it quite hard to have consistant results on these algorithmic questions, especially considering the stress of the situation and the fatigue of going through several interviews in a raw. Practicing leetcode problems for months is fun, up to a point (especially if you already have a job).

That being said, I like that the rules are clearly stated and everyone is given a chance. They don't discriminate as much on your background/educations as some other companies.

What I would usually do with a programming question is ask a number of my coworkers to solve it and use that to evaluate what an "average good performance" looked like. So if most of your coworkers can solve a problem in 10 minutes, it's reasonable to expect that from someone you're interviewing.

Similarly for many other tricks.

I have never used it in real-life development, though.

> I have never used it in real-life development, though.

I'd wager both of these are true for the majority of technical interview problems, and I think that's exactly the point.

so, this question isn't testing if you can find a loop, it's testing whether you have enough experience to have heard of it. which is a fine enough thing to test for.

i understand your point, that questions are often designed poorly, but your example isn't necessarily a good one.

Eh, you really don't need to be a "faculty-level algorithm specialist" to solve this problem. I wouldn't even really call it dynamic programming.

Just make one pass to calculate the sum of the first n numbers for each n. Call that array prefixSum. Then you make a second pass calculating the lowest prefixSum[i] for i <= n. Call that smallestPrefixSum. The maximum subarray sum is then defined by the largest prefixSum[i] - smallestPrefixSum[i], and you can get the subarray itself with a bit more tracking.

I don't know if it's a great interview question but I think most of the engineers I have hired (at Google or Facebook) would be able to solve this problem on the spot, given 15-20 minutes.

If I ask them to draw a picture, they get your solution pretty much immediately.

So I put this problem in the “gotcha” drawer, because it basically depends on having a eureka moment to get the easy solution.

Still fun to pull it out, but more as extra credit than as a useful interview question.

The discovery of many things is done by people with a genius-level intellect. Like calculus, probability, etc. but I can certainly ask mechanical engineers calculus problems, or data scientist probability problems.

It is certainly difficult for someone who never seen anything related to it. But for people who had the background, it is not unreasonable. I think this kind of problem is biased toward people who

1. had a good (theoretical) CS education, or 2. solved lots of leetcode problems so they can just do "pattern matching".

I think the question first asks the interviewee to have cracked an algorithms textbook or be clever enough to come up with the method on the spot.

Second, it asks if you can explain the concept to another engineer. I've met engineers in their 40s who can implement something like depth first search but cannot explain it. That's an immediate red flag to me that, at the very least, the person I'm talking to is not able to meet the responsibilities of a senior engineer.

Reading the other comments I'm not sure d and c is the answer. Might be terminology, but I would split the array in two at the middle, see if the value I'm om is the one I'm searching for. If not, recursively do the same thing on the left or right side of the array.

I guess this is the old “there are two clusters of tech jobs” problems, where I can barely fathom the techniques of the other cluster.

This is on the order of fizzbuzz +1 level maybe. It's elementary stuff.

Or was he looking for best-case optimization or something more than just binary search.

- https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Impl...

> “When Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years. The Java programming language library implementation of binary search had the same overflow bug for more than nine years.”

When the array/list consumes a memory footprint larger than ptrdiff_t it was possible that the specific implementations might fail. It is crucial to remember that the difference between memory address is signed and that the size of objects (even if bare machine integers of some size) in the set might be displayed as a number smaller than one of the powers of two many recall.

On a 32 bit machine this wouldn't be approx 2 billion but rather often 500M 32 bit words or 250M-ish 'double' precision numbers. Let alone if the search is over more complex structures representing objects. For a smaller 16-bit embedded system I could even more readily see this occurring.

That’s not sincere, it’s disingenuous.

The (obvious) point is that binary search is widely misimplemented even by professionals writing textbooks (and this had little to do with the specific Java bug responsible for that one example), and this is all stated directly in the link you didn’t read.

It’s comically ill-suited for time based tech screens as even experts teaming with editors often still get it wrong.

Even if we leave aside the question of to what extent facility at competitive programming contests actually correlates with success in real engineering environments (my own sense is: yes it can help; but at the end of the day, just not all that much) --

if that's a skill you consider to be important, then for gosh sakes, put it in your job ads. Something like "We typically hire CS olympiads, and folks who have at one point or another have been fascinated by competitive programming contests. If this doesn't describe you, then this probably isn't the right company for you."

I can see an usefulness to questions like these. Maybe you are precisely not looking for reasonable but for exceptional people. Or maybe you want to see how the candidate behaves in front of a difficult and concrete problem, even if you do not expect them to solve it.

The unstated implication in most cases is that you damn sure are supposed to solve it - or get "flushed".

As to "seeing how the candidate behaves in front of a difficult and concrete problem" - I'm sure this is what a lot people who ask questions like these think they're achieving by asking them. But again, you have to ask yourself if that's what the questions actually do permit you to assess.

My sense is that it's not - and that questions of this sort are mostly, well - cheap gimmicks, basically.

Think about the potential hidden states (already knows the answer vs blank) vs the evidence you could get from the person answering right or wrong. What should your prior be? Surely that there's a very large chance this person is not a genius. Now how much is that going to move, given that by far most people are not geniuses?

To put it another way, what would you do to impress someone following your reasoning? I would pretend like I didn't know it, and then act out the miraculous direct line to the answer.

As for looking at how people behave in front of a hard problem, what on earth do you know about that? Do you have evidence connecting people's behaviour to subsequent on-the-job performance, both for people you hired and those you didn't?