Re:The Imposter's Handbook
by barrkel on Wednesday August 24, 2016 @01:59PM
(#12353933)
I work on a product that does reconciliation for finance: that basically means comparing two lists. Each list could have a hundred items, or ten million. When there's that much variance in n, it matters what the O(n) is for any code that has to touch this data.
Worst-case list comparison for two lists of length m and n respectively, is O(mn). For 10 million in each list, that's a bigger number than you can reasonably expect to iterate through using brute force. So brute force won't do: it is imperative that you understand how everything that touches all the data scales.
"Not doing obviously stupid shit" means understanding the implementation of data structures and how they scale, understanding how nested loops multiply runtime, how recursion levels multiply runtime. It turns out there's actually a 1:1 correspondence between knowing big-Oh and not doing obviously stupid shit.
That's why it's one of our in-person coding questions: after the candidate has written up a solution to the problem, they need to be able to analyze what they wrote and understand how it scales to different n. If they don't have an intuitive understanding of the performance of code, the chances are they'll do obviously stupid shit.
(Personally, I learned about big-Oh long before I went to college, and I believe it's probably the single most useful thing to learn in CS, right up there with compiler theory (my previous job was a compiler engineer, so I may be biased). With best practices / design patterns etc., it's extremely hard to substitute for experience; I see juniors misapplying software design concepts on a weekly basis.)
Worst-case list comparison for two lists of length m and n respectively, is O(mn). For 10 million in each list, that's a bigger number than you can reasonably expect to iterate through using brute force. So brute force won't do: it is imperative that you understand how everything that touches all the data scales.
"Not doing obviously stupid shit" means understanding the implementation of data structures and how they scale, understanding how nested loops multiply runtime, how recursion levels multiply runtime. It turns out there's actually a 1:1 correspondence between knowing big-Oh and not doing obviously stupid shit.
That's why it's one of our in-person coding questions: after the candidate has written up a solution to the problem, they need to be able to analyze what they wrote and understand how it scales to different n. If they don't have an intuitive understanding of the performance of code, the chances are they'll do obviously stupid shit.
(Personally, I learned about big-Oh long before I went to college, and I believe it's probably the single most useful thing to learn in CS, right up there with compiler theory (my previous job was a compiler engineer, so I may be biased). With best practices / design patterns etc., it's extremely hard to substitute for experience; I see juniors misapplying software design concepts on a weekly basis.)