7 ms·

Let’s begin with a technical interview problem. Consider the following coding question from LeetCode, an online platform for preparing software development cand

Let’s begin with a technical interview problem. Consider the following coding question from LeetCode, an online platform for preparing software development candidates for interviews: [statement of the Maximum Subarray Problem] Before going further—and regardless of your coding proﬁciency—we’d like you to spend a few minutes and take a stab at this question. From Wikipedia: The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images. ... Grenander derived an algorithm that solves the one-dimensional problem in O(n2) time, improving the brute force running time of O(n3). Jay Kadane of Carnegie Mellon University soon after designed an O(n)-time algorithm for the one-dimensional problem,[1] which is clearly as fast as possible. The same O(n)-time algorithm was later automatically derived by algebraic manipulation of the brute-force algorithm using the Bird–Meertens formalism.[2] 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 (as opposed to the way candidates are actually forced to prove their ability to "solve" them: by binge-cramming on dozens and dozens of problems like these for weeks on end, so that they have at least a 50 percent change of passing your "filter") -- the you're either very naive, or deliberately kidding yourself.

lacker 7y ago
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.
- mercutio2 7y ago
  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.
- TheCoelacanth 7y ago
  The approach you just described is textbook dynamic programming.
  - lacker 7y ago
    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.
commandlinefan 7y ago
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.
- mlthoughts2018 7y ago
  binary search is very widely misimplemented, - https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues 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.”
  - luc4sdreyer 7y ago
    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.
    - mlthoughts2018 7y ago
      It seems you’re deliberately not trying to understand.
      - luc4sdreyer 7y ago
        I assure you I'm being sincere.
z3t4 7y ago
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
enriquto 7y ago
> 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.
- tropicalia 7y ago
  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.
- lordnacho 7y ago
  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?
zinclozenge 7y ago
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.
- shados 7y ago
  > 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.
  - neeleshs 7y ago
    100% agree. It's just an "are you willing to put in the work?" filter.
  - notatgoogle2 7y ago
    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.
lordnacho 7y ago
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.
- rofo1 7y ago
  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.
  - lordnacho 7y ago
    https://www.nomachetejuggling.com/2014/06/24/the-worst-programming-interview-question/ https://www.nomachetejuggling.com/2014/06/24/the-worst-progr...
  - wnmurphy 7y ago
    > 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.
  - goatinaboat 7y ago
    In real life development, if you do have a circular linked list unintentionally, what can you do other than terminate the program?
- jiveturkey 7y ago
  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.
  - 7y ago
sweeneyrod 7y ago
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.
- tropicalia 7y ago
  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."
- zinclozenge 7y ago
  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.
gjm11 7y ago
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.
- chapium 7y ago
  Maximum subarray is a typical problem solved by a dynamic programming algorithm.
  - lacker 7y ago
    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.
chaoxu 7y ago
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".
mlcrypto 7y ago
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.
wy35 7y ago
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.

lacker 7y ago

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.

mercutio2 7y ago
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.
TheCoelacanth 7y ago
The approach you just described is textbook dynamic programming.
- lacker 7y ago
  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.

commandlinefan 7y ago

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.

mlthoughts2018 7y ago
binary search is very widely misimplemented, - https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Implementation_issues 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.”
- luc4sdreyer 7y ago
  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.
  - mlthoughts2018 7y ago
    It seems you’re deliberately not trying to understand.
    - luc4sdreyer 7y ago
      I assure you I'm being sincere.

z3t4 7y ago

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

enriquto 7y ago

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

tropicalia 7y ago
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.
lordnacho 7y ago
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?

zinclozenge 7y ago

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.

shados 7y ago
> 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.
- neeleshs 7y ago
  100% agree. It's just an "are you willing to put in the work?" filter.
- notatgoogle2 7y ago
  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.

lordnacho 7y ago

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.

rofo1 7y ago
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.
- lordnacho 7y ago
  https://www.nomachetejuggling.com/2014/06/24/the-worst-programming-interview-question/ https://www.nomachetejuggling.com/2014/06/24/the-worst-progr...
- wnmurphy 7y ago
  > 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.
- goatinaboat 7y ago
  In real life development, if you do have a circular linked list unintentionally, what can you do other than terminate the program?
jiveturkey 7y ago
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.
- 7y ago

sweeneyrod 7y ago

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.

tropicalia 7y ago
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."
zinclozenge 7y ago
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.

gjm11 7y ago

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.

chapium 7y ago
Maximum subarray is a typical problem solved by a dynamic programming algorithm.
- lacker 7y ago
  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.

chaoxu 7y ago

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

mlcrypto 7y ago

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.

wy35 7y ago

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.