7 ms·

> then in the coding exercises you were asked what the O(n) complexity of time/space were I usually ask people to roughly describe what is meant by computation

by tomxor 4y ago

> then in the coding exercises you were asked what the O(n) complexity of time/space were I usually ask people to roughly describe what is meant by computational complexity (sometimes I slot it into the conversation when discussing some code they wrote), or what big O notation is for... assuring them I'm not looking for a formal definition but an understanding and applicability. I probably wouldn't do a great job actually using big O notation to express complexity myself if asked on the spot; however I believe a basic understanding of the underlying concept is invaluable and separates juniors from everyone else. Is this not considered reasonable these days? [edit] To clarify, I think the author was being asked to express their code in big O, I'm just wondering what people think about ask about big O and complexity in general.

semiquaver 4y ago
There’s been a move away from requirements for CS degrees in software development over the last decade or so, but that shouldn’t mean that key concepts like asymptomatic complexity are not needed, only that they are sometimes understood at a more intuitive and less academic level. The author is a senior engineer, I have no doubt that they could describe difference between a linear and polynomial-time algorithm and the potential concerns with the latter even if they might not use that terminology because of a trend against academic-sounding lingo.
returningfory2 4y ago
> Is this not considered reasonable these days? There's currently a backlash against LeetCode style interviews, and I think one part of this backlash is that dismissing anything that feels LeetCodey (like asking about time complexity) is considered reasonable.
- twofornone 4y ago
  I abhor everything leetcode (and suck at their puzzles), but I would call O(n) basic foundational theory. Competence in engineering requires an intuitive understanding of at least time complexity. Given that this is software "engineering", it's probably fine if the candidate isn't familiar with big O specifically but they should at least be able to reason about scaling complexity on an interview, I think.
  - lijogdfljk 4y ago
    Any thoughts on self taught who, i'd think, has a seasoned understanding of time complexity but lacks meaningful mathematical notation background necessary to use Big O fully? Which is to say i have no confidence issues in my working knowledge of Big O. I lead a team, i've developed obsessively for 10 years now and despite my many short comings i don't think understanding trivial complexity - the why of "Why is HashMap faster than BTreeMap on lookup? When is it slower?" etc - is lacking. But, i couldn't use Big O notation to any meaningful complexity with any real confidence. My math background is nil. In general i need to up my interview game, which i think also means i need to up my math game to have a firm understanding of Big O notation itself.. but the complexity is not the issue, for me at least.
armchairhacker 4y ago
Big O is important. I actually have to frequently understand whether my function runs in logarithmic or linear or quadratic or exponential time relative to some value. I can see an issue if you’re asking for a weird big O which really isn’t useful in practice, like “oh, we were expecting this weird algorithm which is O(log log n), not something O(log n)”, or having to calculate the big O of one of those weird algorithms.
- camgunz 4y ago
  It's important but like, it generally boils down to "do you have nested loops" and "are you using a binary tree". A lot of system behavior isn't defined by these kinds of decisions because your N is small. Rather, it's defined by say TCP backoffs or queue sizes, or the broad architecture of the system (must you wait for consensus, do you use Salesforce SObjects as a cache before dumping into Postgres--a real life example--what is your "needs rerendering" trigger). I think it's useful for a programmer to have this kind of basic knowledge of code, but the amount of play it gets in interviews is pretty disproportionate to its importance.
  - dominotw 4y ago
    what about db table scan vs index. that happens all the time.
    - camgunz 4y ago
      I guess this is more of a "do you know about database indexes" question, but I think if it less of a gotcha and more of a jumping off point into a discussion you can take it in a number of directions: - time vs. space tradeoffs - insert vs. select tradeoffs - Oh yeah they're binary trees also, with those implications - What's reasonably distributable (downsides of UUIDs) - at what point might you have query performance issues you can address w/ indexes But like, again practically speaking I think this is just an experience test question. I think I'd prefer something like "on your resume you have Postgres experience dating back 7 years, tell me what you think about it, what its strengths and weaknesses are, and why you would or wouldn't use it". --- Maybe you have thoughts about this too, but I'm also starting to develop some thoughts around whether to consider interviews quizzes/tests or conversations. Thinking about it, I've always approached my interviews (on both sides of the table) as conversations--even questions with simple answers. I guess that's why my answer here is "this should be a discussion about databases" and less "table scans vs. index scans in 30 seconds go". It's totally OK to drill down into specifics and be technical, but this is potentially your first interaction with a new colleague, and you should be collegial, not domineering and inscrutable right? I think we get so worried about hiring a faker that we justify anything to avoid it.
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).

by tomxor 4y ago

semiquaver 4y ago

There’s been a move away from requirements for CS degrees in software development over the last decade or so, but that shouldn’t mean that key concepts like asymptomatic complexity are not needed, only that they are sometimes understood at a more intuitive and less academic level. The author is a senior engineer, I have no doubt that they could describe difference between a linear and polynomial-time algorithm and the potential concerns with the latter even if they might not use that terminology because of a trend against academic-sounding lingo.

returningfory2 4y ago

> Is this not considered reasonable these days? There's currently a backlash against LeetCode style interviews, and I think one part of this backlash is that dismissing anything that feels LeetCodey (like asking about time complexity) is considered reasonable.

twofornone 4y ago
I abhor everything leetcode (and suck at their puzzles), but I would call O(n) basic foundational theory. Competence in engineering requires an intuitive understanding of at least time complexity. Given that this is software "engineering", it's probably fine if the candidate isn't familiar with big O specifically but they should at least be able to reason about scaling complexity on an interview, I think.
- lijogdfljk 4y ago
  Any thoughts on self taught who, i'd think, has a seasoned understanding of time complexity but lacks meaningful mathematical notation background necessary to use Big O fully? Which is to say i have no confidence issues in my working knowledge of Big O. I lead a team, i've developed obsessively for 10 years now and despite my many short comings i don't think understanding trivial complexity - the why of "Why is HashMap faster than BTreeMap on lookup? When is it slower?" etc - is lacking. But, i couldn't use Big O notation to any meaningful complexity with any real confidence. My math background is nil. In general i need to up my interview game, which i think also means i need to up my math game to have a firm understanding of Big O notation itself.. but the complexity is not the issue, for me at least.

armchairhacker 4y ago

Big O is important. I actually have to frequently understand whether my function runs in logarithmic or linear or quadratic or exponential time relative to some value. I can see an issue if you’re asking for a weird big O which really isn’t useful in practice, like “oh, we were expecting this weird algorithm which is O(log log n), not something O(log n)”, or having to calculate the big O of one of those weird algorithms.

camgunz 4y ago
It's important but like, it generally boils down to "do you have nested loops" and "are you using a binary tree". A lot of system behavior isn't defined by these kinds of decisions because your N is small. Rather, it's defined by say TCP backoffs or queue sizes, or the broad architecture of the system (must you wait for consensus, do you use Salesforce SObjects as a cache before dumping into Postgres--a real life example--what is your "needs rerendering" trigger). I think it's useful for a programmer to have this kind of basic knowledge of code, but the amount of play it gets in interviews is pretty disproportionate to its importance.
- dominotw 4y ago
  what about db table scan vs index. that happens all the time.
  - camgunz 4y ago
    I guess this is more of a "do you know about database indexes" question, but I think if it less of a gotcha and more of a jumping off point into a discussion you can take it in a number of directions: - time vs. space tradeoffs - insert vs. select tradeoffs - Oh yeah they're binary trees also, with those implications - What's reasonably distributable (downsides of UUIDs) - at what point might you have query performance issues you can address w/ indexes But like, again practically speaking I think this is just an experience test question. I think I'd prefer something like "on your resume you have Postgres experience dating back 7 years, tell me what you think about it, what its strengths and weaknesses are, and why you would or wouldn't use it". --- Maybe you have thoughts about this too, but I'm also starting to develop some thoughts around whether to consider interviews quizzes/tests or conversations. Thinking about it, I've always approached my interviews (on both sides of the table) as conversations--even questions with simple answers. I guess that's why my answer here is "this should be a discussion about databases" and less "table scans vs. index scans in 30 seconds go". It's totally OK to drill down into specifics and be technical, but this is potentially your first interaction with a new colleague, and you should be collegial, not domineering and inscrutable right? I think we get so worried about hiring a faker that we justify anything to avoid it.

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