3 ms·

Couldn’t agree more. I’m saving this post to send to the next person who expresses disapproval that I ask computational complexity questions during my interview

Couldn’t agree more. I’m saving this post to send to the next person who expresses disapproval that I ask computational complexity questions during my interviews.

alisonkisk 6y ago
How has that person not gotten in trouble for writing terribly slow software at work yet?
- hansvm 6y ago
  I've met some developers with a good intuitive understanding of fast vs slow code and who simply don't have the vocabulary (Big-O and whatnot) to perform well in that kind of an interview. If a person really couldn't write fast code though, they could also just never have been assigned anything performance critical, the issues could have been addressed before they had any impact (e.g., in code review), or there could be a host of organizational reasons why despite pushing excessively slow code to production the consequences to any one developer are minor, especially in the short term (I've seen all of the above). Mildly off-topic, most of the accidentally quadratic code I've seen has arisen by building on top of something that wasn't designed to support it via some kind of miscommunication or leaky abstraction (and the rest from building the algorithm never imagining N could grow large enough to matter). E.g., somebody designed a type which could be instantiated with sorted data and then passed to other places with demanding enough performance guarantees to need sorted data, and the type checker would ensure that an unsorted array wasn't accidentally being passed places it shouldn't be. Somebody else saw a sorted data type providing an Add() method and thought that was perfect -- without any exotic performance needs they just blissfully assumed any of the many well-known average-case logarithmic algorithms was used for the implementation. Fast forward a little bit, and suddenly the instantiation of a large sorted data type is taking way too long because...drumroll please...it's bubble sorting! That isn't to say that nobody was blameless per se, but lack of comp sci knowledge wasn't the culprit; it was some combination of poor communication, ambiguous type names, leaky abstractions, not performance testing, not verifying the behavior of the components you're building on, etc....

Couldn’t agree more. I’m saving this post to send to the next person who expresses disapproval that I ask computational complexity questions during my interviews.

alisonkisk 6y ago

How has that person not gotten in trouble for writing terribly slow software at work yet?

hansvm 6y ago
I've met some developers with a good intuitive understanding of fast vs slow code and who simply don't have the vocabulary (Big-O and whatnot) to perform well in that kind of an interview. If a person really couldn't write fast code though, they could also just never have been assigned anything performance critical, the issues could have been addressed before they had any impact (e.g., in code review), or there could be a host of organizational reasons why despite pushing excessively slow code to production the consequences to any one developer are minor, especially in the short term (I've seen all of the above). Mildly off-topic, most of the accidentally quadratic code I've seen has arisen by building on top of something that wasn't designed to support it via some kind of miscommunication or leaky abstraction (and the rest from building the algorithm never imagining N could grow large enough to matter). E.g., somebody designed a type which could be instantiated with sorted data and then passed to other places with demanding enough performance guarantees to need sorted data, and the type checker would ensure that an unsorted array wasn't accidentally being passed places it shouldn't be. Somebody else saw a sorted data type providing an Add() method and thought that was perfect -- without any exotic performance needs they just blissfully assumed any of the many well-known average-case logarithmic algorithms was used for the implementation. Fast forward a little bit, and suddenly the instantiation of a large sorted data type is taking way too long because...drumroll please...it's bubble sorting! That isn't to say that nobody was blameless per se, but lack of comp sci knowledge wasn't the culprit; it was some combination of poor communication, ambiguous type names, leaky abstractions, not performance testing, not verifying the behavior of the components you're building on, etc....