8 ms·

I feel like a lot of leetcode grinders don't actually understand big O. Sure, they will produce the correct answers to your questions like a well-oiled Chinese

by umvi 4y ago

I feel like a lot of leetcode grinders don't actually understand big O. Sure, they will produce the correct answers to your questions like a well-oiled Chinese Room, but they lack true understanding. It's almost mechanical: "O(1) is faster/better than O(n) which is faster/better than O(n^2)" etc. O(1) is hashmap, O(n) is a for loop, O(n^2) is a nested for loop, etc. So if an O(1) solution exists, the candidate will almost certainly converge on it. Yet the part not being understood is that big-O is just an upper bound that you may never see unless your datasets grow to huge sizes. Sometimes an O(n) implementation is actually better or faster than an O(1) implementation or sometimes O(n^2) is better/preferable than O(n). It depends on a lot of things - the size of the data being handled, the expected scaling of the data, who is going to be maintaining the code, etc. A straightforward, highly readable O(n^2) function that operates on small datasets is almost certainly preferable to an unholy O(n) incantation that is unreadable but technically scales better.

PheonixPharts 4y ago
> well-oiled Chinese Room Wow, this is really the perfect description of the general understanding of algorithms and computational complexity in the post-leet code era. I've found that far less people in software understand and are curious about algorithms than there were 15 years ago, despite the fact that almost everyone studies them now for interviews. I wonder how many people asking questions about computational complexity could tell you what the pumping lemma is, or how a regular language differs from pushdown automata. Or, more important, if they could answer the question "what is Big Omega for this problem?" or if they are really asking "what is big theta?". I'm still tempted sometimes to refresh on recurrence equations to provide the actual answer for these things rather than just applying some heuristic. Of course, in my experience, doing something like that would get you a failing score since they wouldn't know what you're doing and therefore assume you are wrong and an idiot "I can't believe that guy didn't even understand Big O".
- eastbound 4y ago
  > I've found that far less people in software understand and are curious about algorithms than there were 15 years ago, despite the fact that almost everyone studies them now for interviews. It may explain why no-one succeeds my interview test, but then I wonder what I should test on if I want someone correctly smart. My interview test is simply to find a string in a string and return true. It takes two for and one if, everyone fails, I generally stop them after one hour when there are booleans scattered everywhere. The way I give the exercise is “Please program a .contains(), without using .indexOf(), and no need to optimize anything, I’m not looking for anything fancy.” A 49 years old java programmer even complained that the test isn’t fair because it’s stressful to program in front of people, so now I take the habit of sitting in the next room, but then people try to overdo it and deal with UTF-8 before having the basic algo working. I’m pulling my hair wondering what’s this parallel world I’m in, or whether I’m introducing a bias which makes everyone fail (2 interviewees per month for 5 months).
  - Gunax 4y ago
    If they are over-complicating it, then you are not communicating the problem well. Maybe change the problem to an array of ints. It's the same solution but you will not have anyone asking about UTF and text direction.
    - justinlloyd 4y ago
      > “Please program a .contains(), without using .indexOf(), and no need to optimize anything, I’m not looking for anything fancy.” If that is the statement that was given to me, I would clarify the interviewer is not looking for optimal run-time or anything fancy like handling UTF-8 or right-to-left -- because an interviewer often says "nothing fancy" and then will nitpick the fact the code you wrote on the whiteboard doesn't follow precise PEP-8 standards or use idiomatic Ruby or doesn't adhere to the latest C++-23 syntax -- and then I would write a total of six or seven lines of code C code (variable declarations, return statement, etc), which would be two for-loops and an if-statement. I could probably get that down to just the for-loops if I want to be "fancy" and bury the conditional in the for-loop test itself. I think the real problem is, we tend, in an interview situation, to overthink what the interviewer is asking for at times. I see this in a lot of take home tests people do when applying to companies, then ask me if they have done enough before submitting to the company they are interviewing with. That said, I've dealt with interviewers that give the take home test, or the white board test, and then complain that the candidate didn't go far enough by adding on un-asked for stuff. "Going the extra mile" as they say. The crux of the problem is the vagaries of interviewing style.
      - weaksauce 4y ago
        I think a lot could be mitigated if interviewers supplied a take home test and a different example take home test with an answer that showed the format of what they were actually looking for with depth/complexity/testing/etc.
  - PheonixPharts 4y ago
    > A 49 years old java programmer even complained that the test isn’t fair because it’s stressful to program in front of people, so now I take the habit of sitting in the next room Whether programmers like it or not, live coding has become a standard for interviews these days. I can see anyone still unfamiliar with this doing poorly, I used to do awful at these until I realized this is just part of the game, but it's not unreasonable to expect candidates to be able to do whiteboard/live coding. However, you just sitting in the other room, tells me you also have a lot to learn about the structure of live coding interviews. Every major Big Co. that does these has a very well established flow, including providing helpful clues to the candidate. Most companies provide training to all interviewers to make sure this process is smooth, repeatable and fair to candidates. Common tips are to: first make sure the candidate understands the question, make sure they are thinking out loud the entire time. You don't let the candidate go too far down the wrong path. Most important you have a list of anticipated questions with stock answers to help stuck candidates, as well as a list of stock prompts to help them get on the right track if they are lost. For example, in your challenge, if a candidate is stuck you might ask as simpler subproblem "so how would you find out if a sting contained the letter 'a'?" and if a candidate starts heading down the wrong path, prompt with "hmmm... I think I see where you're going, but I recommend you back up a bit and rethink this part here" It sounds like you're in a small shop so I highly recommend you enlist a few friends (especially some that have done interviewing at large companies) to help you work out the kinks in the interview itself.
- sideshowb 4y ago
  > I've found that far less people in software understand and are curious about algorithms than there were 15 years ago Maybe because so many SW job descriptions these days seem to consist of plugging library into framework, and anyone interested in algorithms would be bored? Not saying that's what you're recruiting for, but the industry has expanded massively while I'm guessing the number of algorithm heavy jobs has stayed roughly constant.
- majormajor 4y ago
  > I've found that far less people in software understand and are curious about algorithms than there were 15 years ago, despite the fact that almost everyone studies them now for interviews. I would argue people who prep with LeetCode aren't studying algorithms at all, they're doing something much closer to memorizing. I've seen people who I assume did a bunch of cramming like that because they'll be like "oh this is [xyz]" and throw out a solution in a hurry, and then I ask them to modify it in a non-standard way, and it's almost as if the idea that an off-the-shelf regurgitation of the "normal" solution for a problem not being able to handle a modified scenario is something they've never thought about. Like "oh this is a search problem" -> "what if [something that essentially boils down to the graph potentially having cycles]?" -> [head expodes instead of thinking about, say, tracking what nodes have already been seen]
- closeparen 4y ago
  Well first a lot of software we work on now isn’t pushing performance limits. The long poles in these development projects are requirements and domain understanding. The software that does push technical limits is likely to push IO, storage, and reliability related limits rather than compute. Distributed systems and big data are topics with a lot of interest in the last 15 years! We call them “computers” and algorithms are very important for computation, but many commercial applications these days actually use them in their capacity as telecommunications devices and data storage and retrieval systems, with the actual “computing” part being much less ambitious.
zahllos 4y ago
My favourite approach to big-O questions to to reply O(exp^n) to everything. When asked I point out that whatever it is, exp^n surely bounds it. This'll go either two ways. The interviewer will reflect on whether it is a least upper bound or not (and whether my statement is right) which makes for an interesting discussion about the other types of Landau notation. Or they'll get angry. Ultimately I'm not convinced based on my own personal experience that many of the people asking the question truly understand either. I see it in a somewhat negative light because I feel it is essentially a cargo culted interview technique - recite a few 0()s, yeah we all did CS degrees, great (or not). If you actually try to get into the weeds... I also don't think understanding big O notation is a great predictor of success of a software engineer. As well to ask if the series 1/n converges versus 1/n^2. What I'd rather see is that they can actually implement a solution. Take an ORM for example - a junior candidate knows how to use it and maybe how to debug it. A senior candidate might know that ORMs often emit very poorly optimised SQL and have some ideas on how to fix it. Example picked arbitrarily, ORMs aren't even my area. Even in my actual area of specialty the number of industry programmers who understand say what an elliptic curve with complex multiplication actually is, or even undergrad group theory, is quite limited. And they don't need to - I mean it is ideal if they do, but you can still implement ecc without much theoretical knowledge. There's also a bunch of "not academic" knowledge on various implementation techniques that academics might not know or care about. Brings me back to my ORM point. I'd much rather the person understands how the tools might fit together and more importantly learns any gaps or asks questions and identifies performance issues in the whole. That's not to say that time and space bounds don't matter. They do. But 99% of my use of this knowledge has been to answer interview questions.
- yobbo 4y ago
  It is an upper bound for something, but not the upper bound for that algorithm.
  - zahllos 4y ago
    Told you it drives people nuts. So big-O implies that the runtime is "dominated" by the term in brackets, or put another way, if I say something is O(n^2) I'm stating that as n->infinity the runtime of the algorithm |R| <= c * n^2, where c is some constant. This is still true of exp^n, since |R| <= cn^2 <= dexp^n. Or at least based on my analysis background I'd expect this behaviour. It is of course a little pointless to say the algorithm is O(exp^n), but that's a different issue. It is still an asymptotic upper bound. I just checked my copy of Sipser. Example 7.3 on page 249 if you care. They give an example that f_1 is O(n^3) and state it is O(n^4) also, since n^4 is also an (asymptotic bound) bound. But this is not the point. I have no formal computer science education at all (my background is mathematics, some logic if that counts, but I've never studied algorithms) but many interviewers insist on this one specific area of CS, and yet if you attempt to engage them on the meaning of the things then unless you are very lucky they will a) make some excuse about how they'd have to check, their degree is a while ago, or b) they're actually only reciting also. I'm strongly of the view this is a massively cargo-culted interview question of questionable to no value for most software engineering jobs, given that interview time is very limited and there are many more important factors to evaluate.
jtagen 4y ago
Upper bound? I thought it was a tight asymptotic lower bound.
- deleted 4y ago
  [deleted]
ThrustVectoring 4y ago
Most of the value of understanding computational complexity of code is that you get a little voice saying "hey, this is probably going to cause issues on larger data sets" after writing something that passes tests and works on small pieces of trial data. A Chinese-Room understanding of O(n^2) vs O(n) and O(1) is plenty for noticing these, and may actually out-perform a more thorough understanding; what you want is to notice things going quadratic as you rush through a code review or slam out a feature, and that is almost entirely reliant on pure pattern recognition.
LigmaYC 4y ago
It depends on if you want to scale the application, but I wouldn't choose the readable O(n^2) over the less readable O(n). I would just attempt to make the O(n) readable.

by umvi 4y ago

PheonixPharts 4y ago

> well-oiled Chinese Room Wow, this is really the perfect description of the general understanding of algorithms and computational complexity in the post-leet code era. I've found that far less people in software understand and are curious about algorithms than there were 15 years ago, despite the fact that almost everyone studies them now for interviews. I wonder how many people asking questions about computational complexity could tell you what the pumping lemma is, or how a regular language differs from pushdown automata. Or, more important, if they could answer the question "what is Big Omega for this problem?" or if they are really asking "what is big theta?". I'm still tempted sometimes to refresh on recurrence equations to provide the actual answer for these things rather than just applying some heuristic. Of course, in my experience, doing something like that would get you a failing score since they wouldn't know what you're doing and therefore assume you are wrong and an idiot "I can't believe that guy didn't even understand Big O".

eastbound 4y ago
> I've found that far less people in software understand and are curious about algorithms than there were 15 years ago, despite the fact that almost everyone studies them now for interviews. It may explain why no-one succeeds my interview test, but then I wonder what I should test on if I want someone correctly smart. My interview test is simply to find a string in a string and return true. It takes two for and one if, everyone fails, I generally stop them after one hour when there are booleans scattered everywhere. The way I give the exercise is “Please program a .contains(), without using .indexOf(), and no need to optimize anything, I’m not looking for anything fancy.” A 49 years old java programmer even complained that the test isn’t fair because it’s stressful to program in front of people, so now I take the habit of sitting in the next room, but then people try to overdo it and deal with UTF-8 before having the basic algo working. I’m pulling my hair wondering what’s this parallel world I’m in, or whether I’m introducing a bias which makes everyone fail (2 interviewees per month for 5 months).
- Gunax 4y ago
  If they are over-complicating it, then you are not communicating the problem well. Maybe change the problem to an array of ints. It's the same solution but you will not have anyone asking about UTF and text direction.
  - justinlloyd 4y ago
    > “Please program a .contains(), without using .indexOf(), and no need to optimize anything, I’m not looking for anything fancy.” If that is the statement that was given to me, I would clarify the interviewer is not looking for optimal run-time or anything fancy like handling UTF-8 or right-to-left -- because an interviewer often says "nothing fancy" and then will nitpick the fact the code you wrote on the whiteboard doesn't follow precise PEP-8 standards or use idiomatic Ruby or doesn't adhere to the latest C++-23 syntax -- and then I would write a total of six or seven lines of code C code (variable declarations, return statement, etc), which would be two for-loops and an if-statement. I could probably get that down to just the for-loops if I want to be "fancy" and bury the conditional in the for-loop test itself. I think the real problem is, we tend, in an interview situation, to overthink what the interviewer is asking for at times. I see this in a lot of take home tests people do when applying to companies, then ask me if they have done enough before submitting to the company they are interviewing with. That said, I've dealt with interviewers that give the take home test, or the white board test, and then complain that the candidate didn't go far enough by adding on un-asked for stuff. "Going the extra mile" as they say. The crux of the problem is the vagaries of interviewing style.
    - weaksauce 4y ago
      I think a lot could be mitigated if interviewers supplied a take home test and a different example take home test with an answer that showed the format of what they were actually looking for with depth/complexity/testing/etc.
- PheonixPharts 4y ago
  > A 49 years old java programmer even complained that the test isn’t fair because it’s stressful to program in front of people, so now I take the habit of sitting in the next room Whether programmers like it or not, live coding has become a standard for interviews these days. I can see anyone still unfamiliar with this doing poorly, I used to do awful at these until I realized this is just part of the game, but it's not unreasonable to expect candidates to be able to do whiteboard/live coding. However, you just sitting in the other room, tells me you also have a lot to learn about the structure of live coding interviews. Every major Big Co. that does these has a very well established flow, including providing helpful clues to the candidate. Most companies provide training to all interviewers to make sure this process is smooth, repeatable and fair to candidates. Common tips are to: first make sure the candidate understands the question, make sure they are thinking out loud the entire time. You don't let the candidate go too far down the wrong path. Most important you have a list of anticipated questions with stock answers to help stuck candidates, as well as a list of stock prompts to help them get on the right track if they are lost. For example, in your challenge, if a candidate is stuck you might ask as simpler subproblem "so how would you find out if a sting contained the letter 'a'?" and if a candidate starts heading down the wrong path, prompt with "hmmm... I think I see where you're going, but I recommend you back up a bit and rethink this part here" It sounds like you're in a small shop so I highly recommend you enlist a few friends (especially some that have done interviewing at large companies) to help you work out the kinks in the interview itself.
sideshowb 4y ago
> I've found that far less people in software understand and are curious about algorithms than there were 15 years ago Maybe because so many SW job descriptions these days seem to consist of plugging library into framework, and anyone interested in algorithms would be bored? Not saying that's what you're recruiting for, but the industry has expanded massively while I'm guessing the number of algorithm heavy jobs has stayed roughly constant.
majormajor 4y ago
> I've found that far less people in software understand and are curious about algorithms than there were 15 years ago, despite the fact that almost everyone studies them now for interviews. I would argue people who prep with LeetCode aren't studying algorithms at all, they're doing something much closer to memorizing. I've seen people who I assume did a bunch of cramming like that because they'll be like "oh this is [xyz]" and throw out a solution in a hurry, and then I ask them to modify it in a non-standard way, and it's almost as if the idea that an off-the-shelf regurgitation of the "normal" solution for a problem not being able to handle a modified scenario is something they've never thought about. Like "oh this is a search problem" -> "what if [something that essentially boils down to the graph potentially having cycles]?" -> [head expodes instead of thinking about, say, tracking what nodes have already been seen]
closeparen 4y ago
Well first a lot of software we work on now isn’t pushing performance limits. The long poles in these development projects are requirements and domain understanding. The software that does push technical limits is likely to push IO, storage, and reliability related limits rather than compute. Distributed systems and big data are topics with a lot of interest in the last 15 years! We call them “computers” and algorithms are very important for computation, but many commercial applications these days actually use them in their capacity as telecommunications devices and data storage and retrieval systems, with the actual “computing” part being much less ambitious.

zahllos 4y ago

My favourite approach to big-O questions to to reply O(exp^n) to everything. When asked I point out that whatever it is, exp^n surely bounds it. This'll go either two ways. The interviewer will reflect on whether it is a least upper bound or not (and whether my statement is right) which makes for an interesting discussion about the other types of Landau notation. Or they'll get angry. Ultimately I'm not convinced based on my own personal experience that many of the people asking the question truly understand either. I see it in a somewhat negative light because I feel it is essentially a cargo culted interview technique - recite a few 0()s, yeah we all did CS degrees, great (or not). If you actually try to get into the weeds... I also don't think understanding big O notation is a great predictor of success of a software engineer. As well to ask if the series 1/n converges versus 1/n^2. What I'd rather see is that they can actually implement a solution. Take an ORM for example - a junior candidate knows how to use it and maybe how to debug it. A senior candidate might know that ORMs often emit very poorly optimised SQL and have some ideas on how to fix it. Example picked arbitrarily, ORMs aren't even my area. Even in my actual area of specialty the number of industry programmers who understand say what an elliptic curve with complex multiplication actually is, or even undergrad group theory, is quite limited. And they don't need to - I mean it is ideal if they do, but you can still implement ecc without much theoretical knowledge. There's also a bunch of "not academic" knowledge on various implementation techniques that academics might not know or care about. Brings me back to my ORM point. I'd much rather the person understands how the tools might fit together and more importantly learns any gaps or asks questions and identifies performance issues in the whole. That's not to say that time and space bounds don't matter. They do. But 99% of my use of this knowledge has been to answer interview questions.

yobbo 4y ago
It is an upper bound for something, but not the upper bound for that algorithm.
- zahllos 4y ago
  Told you it drives people nuts. So big-O implies that the runtime is "dominated" by the term in brackets, or put another way, if I say something is O(n^2) I'm stating that as n->infinity the runtime of the algorithm |R| <= c * n^2, where c is some constant. This is still true of exp^n, since |R| <= cn^2 <= dexp^n. Or at least based on my analysis background I'd expect this behaviour. It is of course a little pointless to say the algorithm is O(exp^n), but that's a different issue. It is still an asymptotic upper bound. I just checked my copy of Sipser. Example 7.3 on page 249 if you care. They give an example that f_1 is O(n^3) and state it is O(n^4) also, since n^4 is also an (asymptotic bound) bound. But this is not the point. I have no formal computer science education at all (my background is mathematics, some logic if that counts, but I've never studied algorithms) but many interviewers insist on this one specific area of CS, and yet if you attempt to engage them on the meaning of the things then unless you are very lucky they will a) make some excuse about how they'd have to check, their degree is a while ago, or b) they're actually only reciting also. I'm strongly of the view this is a massively cargo-culted interview question of questionable to no value for most software engineering jobs, given that interview time is very limited and there are many more important factors to evaluate.

jtagen 4y ago

Upper bound? I thought it was a tight asymptotic lower bound.

deleted 4y ago
[deleted]

ThrustVectoring 4y ago

Most of the value of understanding computational complexity of code is that you get a little voice saying "hey, this is probably going to cause issues on larger data sets" after writing something that passes tests and works on small pieces of trial data. A Chinese-Room understanding of O(n^2) vs O(n) and O(1) is plenty for noticing these, and may actually out-perform a more thorough understanding; what you want is to notice things going quadratic as you rush through a code review or slam out a feature, and that is almost entirely reliant on pure pattern recognition.

LigmaYC 4y ago

It depends on if you want to scale the application, but I wouldn't choose the readable O(n^2) over the less readable O(n). I would just attempt to make the O(n) readable.