5 ms·

> including (time/space) complexity analysis. I think this is one of the most inane things to be asked during an interview. personally, I've never found myself

> including (time/space) complexity analysis. I think this is one of the most inane things to be asked during an interview. personally, I've never found myself in a situation where I truly needed to choose between a vector/map/list/hashmap. Or had to find the O(x^n) and replace it with O(x^2) Obviously it depends on the application, but many jobs are simply maintenance coding: find bug, fix bug, test fix. Often times it makes absolutely no difference whether you use a list or a vector, or else you'll get the paradoxical "vector-is-always-faster" because of locality of reference. In my (admittedly limited ) experience, most of the effort is spent simply making it work, not being bogged down because you used a map instead of a hashmap, or didn't know about some esoteric, bleeding-edge probabilistic data structure.

pessimizer 11y ago
Honestly, I consider an instinct for complexity analysis the most important thing I learned in school, and the thing that I've gotten the most use out of. I don't know what case you're making here: are you saying that high-level architecture is so hard that choosing a map or a hashmap should be a coinflip, or the one you see first? Having had some criteria for making the choice makes my life a lot better when everybody is panicking because something is running like shit and no one understands why.
- digler999 11y ago
  To me it was a bunch of rote memorization, just like a biology course. I never - never - have needed to know how bubblesort/heapsort/mergesort actually work, except to appease interviewers. I'm not saying I'm pro writing-inefficient-code, but if you want to talk big-O during an interview, I"m going to roll my eyes about as much as you asking me who the 19th president was.
  - democracy 11y ago
    I ask such questions at the end of an interview, but mostly to see the sanity/reaction or thinking process - wrong answer would do, rolling eyes - would not :)
- b1449835 11y ago
  Oh shit, my code is O(1), looking at it in the profiler tells me that it's not a bottleneck (it says < 5ms). Yet this single function call somehow takes 78ms in wall time when it should at worst be 1ms (and even that is too much). The reason? JVM classloading/JITing. This quite annoying when you have shortlived applications.
jerf 11y ago
"Or had to find the O(x^n) and replace it with O(x^2)" The other thing that really seals the deal for me as an inferior interview question is that you don't need to have a clue what O(x^n) is to wrap some code in a simple time call, see that the code you think ought to run in microseconds is running in seconds, by visual inspection notice stupid nested loops, and fix it. Self-taught programmers may not be able to say "O of exx to the enn" but that doesn't stop them from fixing it. So... seriously, what good is the question anyhow?
- tomjen3 11y ago
  What if it isn't stupid code? What if it is straight forward and simple and looks correct but is just slow because it has to traverse a list instead of using a hash-table or some other data-structure. You can't get there by intermediate steps, you have to rip out the code that uses it and rewrite it with a hashmap. You can only do that if you know the space complexity and when a hash and a list is appropriate.
  - jerf 11y ago
    "You can only do that if you know the space complexity and when a hash and a list is appropriate." You seem to be confusing "knows how to say 'oh of enn squared'" with "the loop gets slow when I iterate over a lot of things". One is generally a product of education, the other, merely experience. The idea that a thing can only be learned in a classroom is perhaps in the top ten most pernicious ideas in the modern world, and probably one of the more surprising ones to show up in that list. You do not need special courses to discover that your code runs slowly, and as I've seen often enough, having had those special courses does not confer immunity against writing slow code. Now, I am also a believer that formal education has its place, and if you are going to get a formal education in computer science, big-O analysis absolutely must be part of it or you are literally missing out on an entire rather important sub-discipline. But the idea that it's some sort of touchstone between Good and Bad programmers is just ludicrous nonsense. Slow code is slow. There are abundant tools that can be used to figure out why. If you can't work out why your O(n^3) loop is running slowly after a couple of years of practicing the art, you don't need formal education, you need a different job.
ktRolster 11y ago
Most likely you think about it, though. When you're coding, and you have a triple loop, do you think, "Oh, this is O(n^3). Is n going to be too big here?" It may be something that's so intuitively obvious to you, that you don't even think about it. So you naturally use the hashmap, where someone else might try a list and then start doing a lookup in a loop. Then while that particular instance might not break things, it'll slow things down, so overall the application feels sluggish instead of snappy.
- eecks 11y ago
  I've never ever thought that to myself. Then again my code never has triple loops.
  - Retra 11y ago
    So do you never call anybody else's functions, or do you always verify that they don't do any loops in those calls?
mech4bg 11y ago
I've seen this plenty of times. I've worked both on a trading platform and a large website, and both times encountered many performance issues that were solved with a more appropriate algorithm or data structure. I've even seen this with a list as small as 10 items - a O(n^3) algorithm was making multiple network calls each time; changing it to O(N) alone made a huge improvement in speed.
- jkyle 11y ago
  This does come up a lot. But I think it's more telling if a programmer knows how to profile his program and find the performance bottlenecks, recognize them for what they are, then fix them appropriately than if they can recall a specific optimization for a specific use case on demand.
- kevan 11y ago
  Most of my work on an ecommerce platform doesn't need much attention to algorithmic complexity, but everyone on my team still curses the guy who wrote an O(n^4) algorithm in our checkout pipeline (discounts, promos, shipping, tax, etc). More than a couple items in your cart and you couldn't checkout because the thread would spin forever. I want to work with a team of people who can recognize these things immediately, even if it's not an absolute requirement for the job.
  - im_down_w_otp 11y ago
    That has a lot more to do with mechanical sympathy, and awareness of when you've exchanged cleverness for complexity disguised as cleverness, than it does with knowing the big-O of operations on a datastructure. What you want the person to identify is that they've made your simple iterative checkout process into multiple unbounded tree traversals with no circuit breaker. Knowing that searching the tree is O(log(n)) isn't very helpful when your problem is an inability to identify that you've made (n) an unnecessarily huge problem space.
tomjen3 11y ago
I am sure the RubyGems authors thought the same way until somebody sped the process up dramatically because they could do space-time analysis[0]. [0]: https://news.ycombinator.com/item?id=9195847 https://news.ycombinator.com/item?id=9195847
ken47 11y ago
I've never found myself in a situation where I truly needed to choose between a vector/map/list/hashmap. Or had to find the O(x^n) and replace it with O(x^2) This entirely depends on the kind of product you are working on. When you get to a large scale with any programming project, optimizing computational resources will cut costs, and can often add value to the customer as well.
- rhizome 11y ago
  This is special pleading, though, right? It being relevant to "any" large scale project really just means that projects can get big enough for it to matter, but how many jobs involve this family of software? How many interviews for positions directly related? Very few, I would guess.
  - NotSammyHagar 11y ago
    I find myself having to think about efficiency at least a couple times a week. I'm working on database implementation, and in the query processor we have to consider all the time how to evaluate various things efficiently.
    - rhizome 11y ago
      Taking this at face value, were any of the techniques you use in these tasks directly addressed during your interview there?
- Cakez0r 11y ago
  I would say it starts becoming important for any application that has multiple concurrent users. If it's a single user running it on some device and there's no shared resource (I.E. back end), then chances are it's not going to be an issue.
EpicEng 11y ago
That's fine, as long as you _never_ need to trust said dev to do anything complex. It's fine to have mediocre developers perform mediocre tasks, but if you want more from them someday you may be in trouble.
- digler999 11y ago
  to me, complex, and complex-ITY are entirely different matters. I want a smart programmer who can figure out really complex bugs (something you cant figure out from google/wikipedia). Not someone who memorized the big-O performance tables of 8 different data structures (something you CAN look up on wikipedia ).
  - was_boring 11y ago
    Exactly. I once identified memory leaks in a managed runtime implementation, worked around them, and showed that third party networking libraries from the hardware vendor were causing irrecoverable crashes but I can't spout off runtime complexity of algos. The former saved a multi million dollar contract and my company's reputation, the latter is something I look up when I need it.
  - EpicEng 11y ago
    Optimally, I would like both. I agree that wrote memorization is not a very useful skill, but I'd like to know that they can grasp concepts, and I find it hard to believe that there are a bunch of skilled devs out there with great potential who don't or can't understand algorithmic complexity. Interviewing is hard though, I'm not trying to say that any one question or metric should necessarily rule someone out.
- FLUX-YOU 11y ago
  That's not really fair, people don't grow unless they're challenged. Some people really do never advance past a certain point, but a lot of people write someone off as mediocre when they're just still in the process of gaining skill. Also, they only assess ONCE, which is pretty bad if we're trying to establish how good you are forever and always.
munchbunny 11y ago
I think it's easy enough to ask for this skill if the job would require the interviewee to apply this skill. If your job is mostly frontend, yeah, you probably won't need to worry about this problem. But if you're hiring somebody to work on graphics? You better be doing complexity estimates in your sleep.
sklogic 11y ago
That guy in Google who screwed up Android thought just like you. Now, as the number of text messages stored on your phone grows, the entire system slows down. Such a pity that cretin was not screened out on an interview!
plasticchris 11y ago
This can happen even on small systems. I once replaced a O(n^4) with O(n^2*ln(n)) on an embedded target which made a minutes long user facing process take seconds. The catch is that the original used a good algorithm, but made an implementation error which I caught in profiling. So complexity analysis is good, but the only way to get better at something is to measure it.
nathanaldensr 11y ago
Here's how you should reply: "Sorry, I don't have those complexities memorized. When I really need to look them up (which is nearly never), I refer to bigocheatsheet.com."
robryan 11y ago
You should have an intuitive idea around complexity and when it makes sense to optimise. I don't think though you need to know that for example fastsortx is n log n in the best case off the top of your head in an interview situation. You should be able to reason your way through why it is faster than some other sort though.
- nsxwolf 11y ago
  What the heck is fastsortx? This is another problem I have. I study all these algorithm books then when I get to the interview they ask something that either isn't in the books or they've come up with some nickname for it and expect me to know it.
  - democracy 11y ago
    Even Google doesn't know...
  - rhaps0dy 11y ago
    It's probably a placeholder. Same as writing <sort algorithm>.
democracy 11y ago
That's how I failed my Google interview - they said they expect programmers for any position to have good knowledge of algorithms, yeah, well... :) Frankly I don't like trivia-style interviews.
b1449835 11y ago
Because in most cases n is a very low number. If you only have 10 elements the algorithm doesn't matter.
collyw 11y ago
Exactly. Performance issues happen. Most of them can be solved by re-indexing a database or adding caching. If I really need speed at the algorithm level I can look it up.

pessimizer 11y ago

Honestly, I consider an instinct for complexity analysis the most important thing I learned in school, and the thing that I've gotten the most use out of. I don't know what case you're making here: are you saying that high-level architecture is so hard that choosing a map or a hashmap should be a coinflip, or the one you see first? Having had some criteria for making the choice makes my life a lot better when everybody is panicking because something is running like shit and no one understands why.

digler999 11y ago
To me it was a bunch of rote memorization, just like a biology course. I never - never - have needed to know how bubblesort/heapsort/mergesort actually work, except to appease interviewers. I'm not saying I'm pro writing-inefficient-code, but if you want to talk big-O during an interview, I"m going to roll my eyes about as much as you asking me who the 19th president was.
- democracy 11y ago
  I ask such questions at the end of an interview, but mostly to see the sanity/reaction or thinking process - wrong answer would do, rolling eyes - would not :)
b1449835 11y ago
Oh shit, my code is O(1), looking at it in the profiler tells me that it's not a bottleneck (it says < 5ms). Yet this single function call somehow takes 78ms in wall time when it should at worst be 1ms (and even that is too much). The reason? JVM classloading/JITing. This quite annoying when you have shortlived applications.

jerf 11y ago

"Or had to find the O(x^n) and replace it with O(x^2)" The other thing that really seals the deal for me as an inferior interview question is that you don't need to have a clue what O(x^n) is to wrap some code in a simple time call, see that the code you think ought to run in microseconds is running in seconds, by visual inspection notice stupid nested loops, and fix it. Self-taught programmers may not be able to say "O of exx to the enn" but that doesn't stop them from fixing it. So... seriously, what good is the question anyhow?

tomjen3 11y ago
What if it isn't stupid code? What if it is straight forward and simple and looks correct but is just slow because it has to traverse a list instead of using a hash-table or some other data-structure. You can't get there by intermediate steps, you have to rip out the code that uses it and rewrite it with a hashmap. You can only do that if you know the space complexity and when a hash and a list is appropriate.
- jerf 11y ago
  "You can only do that if you know the space complexity and when a hash and a list is appropriate." You seem to be confusing "knows how to say 'oh of enn squared'" with "the loop gets slow when I iterate over a lot of things". One is generally a product of education, the other, merely experience. The idea that a thing can only be learned in a classroom is perhaps in the top ten most pernicious ideas in the modern world, and probably one of the more surprising ones to show up in that list. You do not need special courses to discover that your code runs slowly, and as I've seen often enough, having had those special courses does not confer immunity against writing slow code. Now, I am also a believer that formal education has its place, and if you are going to get a formal education in computer science, big-O analysis absolutely must be part of it or you are literally missing out on an entire rather important sub-discipline. But the idea that it's some sort of touchstone between Good and Bad programmers is just ludicrous nonsense. Slow code is slow. There are abundant tools that can be used to figure out why. If you can't work out why your O(n^3) loop is running slowly after a couple of years of practicing the art, you don't need formal education, you need a different job.

ktRolster 11y ago

Most likely you think about it, though. When you're coding, and you have a triple loop, do you think, "Oh, this is O(n^3). Is n going to be too big here?" It may be something that's so intuitively obvious to you, that you don't even think about it. So you naturally use the hashmap, where someone else might try a list and then start doing a lookup in a loop. Then while that particular instance might not break things, it'll slow things down, so overall the application feels sluggish instead of snappy.

eecks 11y ago
I've never ever thought that to myself. Then again my code never has triple loops.
- Retra 11y ago
  So do you never call anybody else's functions, or do you always verify that they don't do any loops in those calls?

mech4bg 11y ago

I've seen this plenty of times. I've worked both on a trading platform and a large website, and both times encountered many performance issues that were solved with a more appropriate algorithm or data structure. I've even seen this with a list as small as 10 items - a O(n^3) algorithm was making multiple network calls each time; changing it to O(N) alone made a huge improvement in speed.

jkyle 11y ago
This does come up a lot. But I think it's more telling if a programmer knows how to profile his program and find the performance bottlenecks, recognize them for what they are, then fix them appropriately than if they can recall a specific optimization for a specific use case on demand.
kevan 11y ago
Most of my work on an ecommerce platform doesn't need much attention to algorithmic complexity, but everyone on my team still curses the guy who wrote an O(n^4) algorithm in our checkout pipeline (discounts, promos, shipping, tax, etc). More than a couple items in your cart and you couldn't checkout because the thread would spin forever. I want to work with a team of people who can recognize these things immediately, even if it's not an absolute requirement for the job.
- im_down_w_otp 11y ago
  That has a lot more to do with mechanical sympathy, and awareness of when you've exchanged cleverness for complexity disguised as cleverness, than it does with knowing the big-O of operations on a datastructure. What you want the person to identify is that they've made your simple iterative checkout process into multiple unbounded tree traversals with no circuit breaker. Knowing that searching the tree is O(log(n)) isn't very helpful when your problem is an inability to identify that you've made (n) an unnecessarily huge problem space.

tomjen3 11y ago

I am sure the RubyGems authors thought the same way until somebody sped the process up dramatically because they could do space-time analysis[0]. [0]: https://news.ycombinator.com/item?id=9195847 https://news.ycombinator.com/item?id=9195847

ken47 11y ago

I've never found myself in a situation where I truly needed to choose between a vector/map/list/hashmap. Or had to find the O(x^n) and replace it with O(x^2) This entirely depends on the kind of product you are working on. When you get to a large scale with any programming project, optimizing computational resources will cut costs, and can often add value to the customer as well.

rhizome 11y ago
This is special pleading, though, right? It being relevant to "any" large scale project really just means that projects can get big enough for it to matter, but how many jobs involve this family of software? How many interviews for positions directly related? Very few, I would guess.
- NotSammyHagar 11y ago
  I find myself having to think about efficiency at least a couple times a week. I'm working on database implementation, and in the query processor we have to consider all the time how to evaluate various things efficiently.
  - rhizome 11y ago
    Taking this at face value, were any of the techniques you use in these tasks directly addressed during your interview there?
Cakez0r 11y ago
I would say it starts becoming important for any application that has multiple concurrent users. If it's a single user running it on some device and there's no shared resource (I.E. back end), then chances are it's not going to be an issue.

EpicEng 11y ago

That's fine, as long as you _never_ need to trust said dev to do anything complex. It's fine to have mediocre developers perform mediocre tasks, but if you want more from them someday you may be in trouble.

digler999 11y ago
to me, complex, and complex-ITY are entirely different matters. I want a smart programmer who can figure out really complex bugs (something you cant figure out from google/wikipedia). Not someone who memorized the big-O performance tables of 8 different data structures (something you CAN look up on wikipedia ).
- was_boring 11y ago
  Exactly. I once identified memory leaks in a managed runtime implementation, worked around them, and showed that third party networking libraries from the hardware vendor were causing irrecoverable crashes but I can't spout off runtime complexity of algos. The former saved a multi million dollar contract and my company's reputation, the latter is something I look up when I need it.
- EpicEng 11y ago
  Optimally, I would like both. I agree that wrote memorization is not a very useful skill, but I'd like to know that they can grasp concepts, and I find it hard to believe that there are a bunch of skilled devs out there with great potential who don't or can't understand algorithmic complexity. Interviewing is hard though, I'm not trying to say that any one question or metric should necessarily rule someone out.
FLUX-YOU 11y ago
That's not really fair, people don't grow unless they're challenged. Some people really do never advance past a certain point, but a lot of people write someone off as mediocre when they're just still in the process of gaining skill. Also, they only assess ONCE, which is pretty bad if we're trying to establish how good you are forever and always.

munchbunny 11y ago

I think it's easy enough to ask for this skill if the job would require the interviewee to apply this skill. If your job is mostly frontend, yeah, you probably won't need to worry about this problem. But if you're hiring somebody to work on graphics? You better be doing complexity estimates in your sleep.

sklogic 11y ago

That guy in Google who screwed up Android thought just like you. Now, as the number of text messages stored on your phone grows, the entire system slows down. Such a pity that cretin was not screened out on an interview!

plasticchris 11y ago

This can happen even on small systems. I once replaced a O(n^4) with O(n^2*ln(n)) on an embedded target which made a minutes long user facing process take seconds. The catch is that the original used a good algorithm, but made an implementation error which I caught in profiling. So complexity analysis is good, but the only way to get better at something is to measure it.

nathanaldensr 11y ago

Here's how you should reply: "Sorry, I don't have those complexities memorized. When I really need to look them up (which is nearly never), I refer to bigocheatsheet.com."

robryan 11y ago

You should have an intuitive idea around complexity and when it makes sense to optimise. I don't think though you need to know that for example fastsortx is n log n in the best case off the top of your head in an interview situation. You should be able to reason your way through why it is faster than some other sort though.

nsxwolf 11y ago
What the heck is fastsortx? This is another problem I have. I study all these algorithm books then when I get to the interview they ask something that either isn't in the books or they've come up with some nickname for it and expect me to know it.
- democracy 11y ago
  Even Google doesn't know...
- rhaps0dy 11y ago
  It's probably a placeholder. Same as writing <sort algorithm>.

democracy 11y ago

That's how I failed my Google interview - they said they expect programmers for any position to have good knowledge of algorithms, yeah, well... :) Frankly I don't like trivia-style interviews.

b1449835 11y ago

Because in most cases n is a very low number. If you only have 10 elements the algorithm doesn't matter.

collyw 11y ago

Exactly. Performance issues happen. Most of them can be solved by re-indexing a database or adding caching. If I really need speed at the algorithm level I can look it up.