Hacker News Reader

Just as a data point: I read the paper and thought "that sounds like it might be fun, so let's have a go" and wrote down a (correct aside from an off-by-one error) O(n) solution in a couple of minutes. I am not a faculty-level algorithm specialist at CMU. I don't recall seeing a solution to this particular problem before. I am a mathematician working in industry doing kinda-algorithm-y things, though. There are at least two other people working at my (small) employer whom I would expect to be able to find an O(n) solution fairly quickly. (To quantify: >=75% chance that they find one, given 20 minutes to think.)

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.

Another data point: but I checked my LeetCode history and I actually solved this problem[1] a year ago. It's flagged as "easy" on LeetCode and I have one submission (which was accepted) but I don't even remember solving it, indicating it was probably routine. The problem also has 4809 "thumbs up" vs 177 "thumbs down" which is a strong indicator that others didn't find the problem too hard either; problems that don't match their stated difficultly get downvoted hard.

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

Did you provide the O(n) solution or O(n3) brute force solution? I think that's the important bit.

Nit: The brute-force solution for the one-dimensional case is O(n^2), not O(n^3).

According to the Wikipedia page[1], the brute force solution is O(n^3) for the one-dimensional case. They don't give an algorithm, but the obvious pseudo-code is:

    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

It takes three nested loops, with the third being the sum from i to j. This is obviously a very naive algorithm, but that's why it's called brute force. According to Wikipedia, Grenander apparently improved this to O(n^2), and then Jay Kadane came up with the first O(n) solution. For the 2D case, brute force is actually O(n^6).

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

Huh! That's a bit more brutishly forceful than I was expecting, and I concede the point. It hadn't occurred to me to stick that innermost loop in there rather than keeping a running sum in the second loop.

The brute force solution that seems most obvious to me is to pick a starting index and an ending index out of all possible indexes such that start < end, and calculate the sum of that sub-array (keeping the biggest result).

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

Brute is choosing every index pair (n^2) and calculating the sun of their subarray (n). With prefix sums you can get to n^2.

O(n). Faster than 75% of accepted solutions. :)

You're right and I stand corrected - it's not that hard of a problem. I found this out when (sometime later) I actually sat down to solve it, without considering any of the hints posted elsewhere in this thread.

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.

Maximum subarray is a typical problem solved by a dynamic programming algorithm.

It's possible to use dynamic programming but it's such a simple example you don't really have to. If you're familiar with dynamic programming at all, you should be able to get it - it would be pretty reasonable to assign this as a introductory homework program for the dynamic programming section of an algorithms class.

Presumably asking questions like these would be fine if the expectation to solve wasn't there, and instead their performance was evaluated based on how their reasoning/approach changes with hints and discussion with the interviewer. But instead gotta be able to solve at least 1 question and make good progress on a follow up to be considered for an offer from a FAANG company.

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

> to be considered for an offer from a FAANG company.

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.

When I last interviewed with Google (which was about 8 years ago, I think), they explicitly told me not to post my questions to the internet, and if I recall correctly, had me sign an NDA about the questions because they want to reuse them. I don't know if that has changed in the intervening years.

My info is also pretty out of date, but for a long time at least they would give a PDF/flier thingy with a "how to prepare for your interview" that had all that stuff listed, and it went in a lot of details.

They'll generally give a list of topics but not specific questions. For example facebook may put an emphasis on graph and tree data structures and search algorithms

100% agree. It's just an "are you willing to put in the work?" filter.

This is one of the problems with sites like HackerRank that lots of companies seem to be moving to for testing applicants. I know almost all of us hate whiteboard problems, but I would definitely prefer the opportunity to talk through my thought process on a problem rather than having X number of minutes to get my code to pass a unit test or I fail the interview.

> gotta be able to solve at least 1 question and make good progress on a follow up to be considered for an offer from a FAANG company

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.

Presumably asking questions like these would be fine if the expectation to solve wasn't there

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.

Another good one is the "does linked list have loop" question. If you don't know the answer, you have to figure it out from inspiration. Took over a decade for the first guy to do it.

The second pointer going twice the speed? I don't know the story, but I know the solution, because I've seen it.

Similarly for many other tricks.

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

> I know the solution, because I've seen it.

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

https://www.nomachetejuggling.com/2014/06/24/the-worst-progr...

In real life development, if you do have a circular linked list unintentionally, what can you do other than terminate the program?

but that one should be, in fact, well known. i've been out of school forever but surely it has to be taught now?

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.

If it's about experience, why not ask whether the person has an opinion on XYZ framework or other thing that you actually use?

If you really think anyone -- short of a faculty-level algorithm specialist at places like CMU -- can be reasonably expected to derive an optimal solution to problems like these on the spot

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.

Many great engineers get pretty stuck when I ask this question; they try to do dynamic programming and unless they get lucky they get a little lost.

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 approach you just described is textbook dynamic programming.

Well, kind of. I would call it dynamic programming if you thought of the algorithm as calling some function many times in an inefficient version, and then caching that result to make it efficient. That is probably how the textbook would describe it, too. I don't think you need to understand dynamic programming to get this, is all.

I was a TA in a few undergraduate algorithms classes in at UIUC. This level of problems can show up in the exams. Although I hold UIUC students in high regard, certainly we don't expect undergrads to be "faculty-level algorithm specialist."

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 used to work with a guy who tech-screened applicants by demanding that they come up with the binary-search algorithm: “given a sorted list of numbers, find the fastest way to locate an element in the array”. Of course, if you had any university-level exposure to CS, you would have already seen the solution - I sort of suspected this was his tricky way to filter out non-CS graduates.

I wouldn't characterize it that way, I don't have a CS degree and could solve this trivially.

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.

Divide and conquer? I don't have a cs degree, but this was thought in highschool in Romania. If you went to the right kind of high school.

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... have a hard time imagining what coding job wouldn’t want candidates to know how to find a log N solution to a search problem.

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.

That was his position - I just recall that all of the CS grads got it, and none of the self-taught/bootcamp types did, though.

What are you getting at? That this is a trick or bad question?

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.

It seemed like a bit much to me at the time. It's not something that I've ever had occasion to actually use (I don't search sorted lists much...). I wondered if I would have been able to come up with it if I hadn't already seen it in data structures class years ago - I mean, of course I figured out the "algorithm" when I was a little kid playing "guess the number", but I'll never know if I would have come up with it in that context if I hadn't already seen it. The consensus here seems to be that it's a reasonable question, though - but I do remember that the only people who ever got it were people with CS degrees.

binary search is very widely misimplemented,

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

The bug only manifests if the range you're searching is within MAX_INT/2 (or whatever numeric datatype you're using). I'm not sure I understand the point you're trying to make.

I didn't understand what you were talking about offhand and thought range might be the value of the stored/searched data, not a pointer arithmetic issue.

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.

You make a good point. I was actually speaking about the general case, where you're simply pulling the bounds of x_min and x_max closer until f(x) reaches a target value or the bounds converge to the same value. f could be an array and x could be an index, but it doesn't have to be. The bug still exists in this general case. All you need is a numerical datatype that can overflow, and most of them can.

It seems you’re deliberately not trying to understand.

I assure you I'm being sincere.

Yet you focus only on one aspect of the linked discussion on the high rate of misimplementations, an aspect that represents the least relevant part, and then act as if this invalidates the point?

That’s not sincere, it’s disingenuous.

I didn't say it invalidates the point, because I honestly don't know what your point was to begin with. Which is why I asked the question originally. I'm still no closer to knowing, and it seems like you're not interested in elaborating. Suit yourself.

This is an extremely disingenuous reply as well. You started off your first reply by saying “the bug only manifests ...” already pre-supposing that the scope of my original comment was restricted to that one thing, and tacitly ignoring all the other aspects of the link.

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.

I think this is overstating things. Because of the way bleeding edge research gradually trickles down to being generic undergrad content, things like this that would've been the domain of algorithms researchers in the 80s are now tractable for smart undergrads who are into competitive programming.

Now tractable for smart undergrads who are into competitive programming.

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

This also happens in math and physics. One of my homework assignments was solving the quantum harmonic oscillator via path integral formalism. Something that took Feynman a modest amount of time.

I've looked at your test results and Im sorry to say you did not pass the test. You need to work on your algorithms. Can we keep your CV? /automatically generated message

I was absolutely rekt by this exact question several years back for a Microsoft internship interview. I had just finished my first CS class where I learned binary search, heaps, hash tables, but unfortunately not cumulative sums.

I don't think this problem is THAT difficult -- I did manage to solve this on my own after a semester of algorithms class and a bit of practice from DP problems. The intuition is that at each index you're either continuing a previous subarray or starting a new one, depending on which one results in a larger sum. It's pretty standard DP stuff, and I'm sure there's many undergrads out there who can bang it out in an interview. Though I personally did it in the comfort of my home and probably wouldn't have come up with it in an interview.

> If you really think anyone (..) can be reasonably expected to derive an optimal solution to problems like these...

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.

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.

I don't buy that at all.

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?