3 ms·

The emphasis placed on big-O in interviews is weird though. Accidentally quadratic code happens, sure, but the way the industry uses it as an interviewing shibb

The emphasis placed on big-O in interviews is weird though. Accidentally quadratic code happens, sure, but the way the industry uses it as an interviewing shibboleth makes it feel like this is a safety critical issue; as if at some point a developer used an O(n log n) algorithm when an O(n) algorithm existed and people died. Complexity can be insidious, and it can lead to annoying bugs you only discover in pathological data cases, but it is in no way as important in software development as correctness. Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. Your O(log n) recursive tree traversal is beautifully efficient. Too bad it stack overflows with trivial tree depths.

rdw 5y ago
> Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. In my experience, these are not actually that different. Even in straightforward web development on smallish data sets, it's pretty easy to write something that runs "fast on my machine" but is so slow on production-sized data that it is effectively infinite.
- jameshart 5y ago
  Yes, as I say, clearly it happens. But when it does the results are no worse than any other bug. And it’s far more common, and more dangerous, in my experience, to see a loop that assumes it must eventually reach a terminal condition that isn’t actually guaranteed. I just don’t think the risk of hiring someone who misestimates the time complexity of an algorithm is sufficiently great that it’s worth explicitly filtering for. Why is this the one piece of hard won experience or academic knowledge that we need a candidate to have before they join our company, given that it’s something that can be taught in a single CS101 lecture, and in practical terms, something I can explain to a competent developer in about ten minutes?
ryandrake 5y ago
Even weirder: A lot of companies who are obsessed with big-O and algorithm complexity don't ask candidates even basic questions that require them to think across many orders of magnitude, in terms of time and storage. I'd argue that being flexible enough and able to visualize things across, say, ten orders of magnitude, is a more critical programming skill than knowing big-O. Even basic questions: Answer with either the word nanoseconds, microseconds, or milliseconds: What's the order-of-magnitude latency of CPU cache lookup? Reading 1MB from spinning disk? Reading 1MB from memory? A round trip packet to a server 1km away? A GPU clearing a 4K screen? A mutex lock? Answer with kilobytes, megabytes, or gigabytes: What's the order-of-magnitude size of a digitized photo? A song? A movie? A graphics frame buffer? Wikipedia? Google's homepage? A typical bootloader? A Windows app executable file? A typical CPU L1 cache? L2 cache? Too many junior developers can only answer a few of these, even with the answers having three orders of magnitude granularity! But we constantly ask them to belt out the best and worst case big-O complexity of a binary tree.
- lijogdfljk 5y ago
  Yea, thank you. I run backend interviews for my company and while i do want someone to understand the basics of complexity, i am far more interested in how they think about, as you put it, orders. I want them to group data in a simple DB call, not call the DB in a loop - avoiding network. I want them to make 2 DB calls if a join explodes the rows and thus a single call ends up much larger than 2 calls. I want them to understand why iterating a large hashmap can be much, much worse than a data structure more suited for sequential access, etc. Ironically i suck at Big O notation itself. So maybe i under value it.
- MonaroVXR 5y ago
  I'm going to ask a stupid question, but how would you find the answers about these questions? (It's bad question, but I'm aiming at L1 and L2 cache) Which programming language is low level that need that kind of understanding? (Obviously all of them, but I still need the answer)

rdw 5y ago

> Code that runs slow over pathological input is nowhere near as dangerous as code that goes into an infinite loop over pathological input. In my experience, these are not actually that different. Even in straightforward web development on smallish data sets, it's pretty easy to write something that runs "fast on my machine" but is so slow on production-sized data that it is effectively infinite.

jameshart 5y ago
Yes, as I say, clearly it happens. But when it does the results are no worse than any other bug. And it’s far more common, and more dangerous, in my experience, to see a loop that assumes it must eventually reach a terminal condition that isn’t actually guaranteed. I just don’t think the risk of hiring someone who misestimates the time complexity of an algorithm is sufficiently great that it’s worth explicitly filtering for. Why is this the one piece of hard won experience or academic knowledge that we need a candidate to have before they join our company, given that it’s something that can be taught in a single CS101 lecture, and in practical terms, something I can explain to a competent developer in about ten minutes?

ryandrake 5y ago

Even weirder: A lot of companies who are obsessed with big-O and algorithm complexity don't ask candidates even basic questions that require them to think across many orders of magnitude, in terms of time and storage. I'd argue that being flexible enough and able to visualize things across, say, ten orders of magnitude, is a more critical programming skill than knowing big-O. Even basic questions: Answer with either the word nanoseconds, microseconds, or milliseconds: What's the order-of-magnitude latency of CPU cache lookup? Reading 1MB from spinning disk? Reading 1MB from memory? A round trip packet to a server 1km away? A GPU clearing a 4K screen? A mutex lock? Answer with kilobytes, megabytes, or gigabytes: What's the order-of-magnitude size of a digitized photo? A song? A movie? A graphics frame buffer? Wikipedia? Google's homepage? A typical bootloader? A Windows app executable file? A typical CPU L1 cache? L2 cache? Too many junior developers can only answer a few of these, even with the answers having three orders of magnitude granularity! But we constantly ask them to belt out the best and worst case big-O complexity of a binary tree.

lijogdfljk 5y ago
Yea, thank you. I run backend interviews for my company and while i do want someone to understand the basics of complexity, i am far more interested in how they think about, as you put it, orders. I want them to group data in a simple DB call, not call the DB in a loop - avoiding network. I want them to make 2 DB calls if a join explodes the rows and thus a single call ends up much larger than 2 calls. I want them to understand why iterating a large hashmap can be much, much worse than a data structure more suited for sequential access, etc. Ironically i suck at Big O notation itself. So maybe i under value it.
MonaroVXR 5y ago
I'm going to ask a stupid question, but how would you find the answers about these questions? (It's bad question, but I'm aiming at L1 and L2 cache) Which programming language is low level that need that kind of understanding? (Obviously all of them, but I still need the answer)