Re:How to Rock an Algorithms Interview
by yason on Tuesday September 27, 2011 @01:48AM
(#3042046)
This is ringing true. It somehow illustrates how essential computational complexity is because you're totally fucked up if you have no clue--yet how rarely you actually bump into the question of complexity in real life.
I'm self-taught and I've read and learned about computational complexity several times from various CS books and later Internet since I was maybe fifteen years old. I know how O(1), O(lg n), O(n lg n), O(n), O(n^x), and O(x^n) scale and which kind of algorithms roughly belong to which order of complexity.
However, keyword being several times.
I so rarely bump into these that I don't actively remember if heapsort is lg n or n lg n, or how the best-case, average-case, and worst-case complexities differ exactly between heapsort, quicksort, and mergesort. (I do remember that mergesort had a good worst-case behaviour in comparison to the others, at least quicksort, but I'd really have to check the bounds separately.) To mitigate this, I've guiltily re-learned them several times--I like reading Knuth or other CS books per se, just for fun--but like anything you don't need you do have a hard time remembering.
However, I do recognize them all being lg-something and looking up the various bounds is just a Google search away. Further, I do recognize the complexity orders in the sense that I might prototype something and initially stash items into a linked list but make a mental note that accessing the list can potentially become a bottleneck because it's O(n) so I shall reserve some mind power to change it into some O(lg) tree or ordered array at some point.
But at the other end the truth is that you just have to have some idea about complexity. You generally don't need more than that, and when you do you can just re-study that portion of the subject in detail from a huge number of web pages.
For example, it's useful to recognize the obvious bottlenecks of O(n^x) and O(x^n) but if you do, you don't bump into them anymore. You might bump into O(n) bottlenecks because you left them there yourself, probably on purpose, but since you recognize what linear complexity can do you will generally just change the relevant data structures into O(lg something) and be done with it. And if O(lg something) code becomes a bottleneck, you usually have stupid access patterns elsewhere in the code; I don't remember ever seeing a binary tree alone having become the real bottleneck in any program with the rest of the code being optimal.
What's interesting is that I more often bump into problems with the physical representation of the data structure than the computational complexity. A big naive hash table can cause lots of cache misses unless you deliberately work to align your items withing as few cachelines as possible. The difference between accessing five cachelines rather than five hundred cachelines can be blasting. I know this kind of optimization wouldn't scale towards n⇒∞ generally but it can have a big
effect on real-world programs.
I'm self-taught and I've read and learned about computational complexity several times from various CS books and later Internet since I was maybe fifteen years old. I know how O(1), O(lg n), O(n lg n), O(n), O(n^x), and O(x^n) scale and which kind of algorithms roughly belong to which order of complexity.
However, keyword being several times.
I so rarely bump into these that I don't actively remember if heapsort is lg n or n lg n, or how the best-case, average-case, and worst-case complexities differ exactly between heapsort, quicksort, and mergesort. (I do remember that mergesort had a good worst-case behaviour in comparison to the others, at least quicksort, but I'd really have to check the bounds separately.) To mitigate this, I've guiltily re-learned them several times--I like reading Knuth or other CS books per se, just for fun--but like anything you don't need you do have a hard time remembering.
However, I do recognize them all being lg-something and looking up the various bounds is just a Google search away. Further, I do recognize the complexity orders in the sense that I might prototype something and initially stash items into a linked list but make a mental note that accessing the list can potentially become a bottleneck because it's O(n) so I shall reserve some mind power to change it into some O(lg) tree or ordered array at some point.
But at the other end the truth is that you just have to have some idea about complexity. You generally don't need more than that, and when you do you can just re-study that portion of the subject in detail from a huge number of web pages.
For example, it's useful to recognize the obvious bottlenecks of O(n^x) and O(x^n) but if you do, you don't bump into them anymore. You might bump into O(n) bottlenecks because you left them there yourself, probably on purpose, but since you recognize what linear complexity can do you will generally just change the relevant data structures into O(lg something) and be done with it. And if O(lg something) code becomes a bottleneck, you usually have stupid access patterns elsewhere in the code; I don't remember ever seeing a binary tree alone having become the real bottleneck in any program with the rest of the code being optimal.
What's interesting is that I more often bump into problems with the physical representation of the data structure than the computational complexity. A big naive hash table can cause lots of cache misses unless you deliberately work to align your items withing as few cachelines as possible. The difference between accessing five cachelines rather than five hundred cachelines can be blasting. I know this kind of optimization wouldn't scale towards n⇒∞ generally but it can have a big effect on real-world programs.