4 ms·

University computer science courses focus on the asymptotic performance of algorithms - what is the Big O for large N? That results in such algorithms commonly

University computer science courses focus on the asymptotic performance of algorithms - what is the Big O for large N? That results in such algorithms commonly being the topic of job interviews. But in my actual experience the data sets are far smaller, when we encounter them in the software that the typical person uses - what we used to call "shrink-wrap software" because users purchased it in a shrink-wrapped box at a computer store. Rather than considering the runtime of an algorithm that is sorting one million items, consider the runtime of an algorithm that sorts one hundred thousand completely independent sets of ten items. I've often toyed with the idea of publishing a book called "algorithms for small N".

yeukhon 11y ago
Do people read in 1M elements at once? I think when it comes to consuming big chuck of input stream, the idea is streaming or split into smaller manageable chunks. I find in practice the hardest thing is to use the right technology rather than finding an algorithm.
- MichaelCrawford 11y ago
  There are certain applications where big N is common. Web search, for example. But in typical GUI applications, you get a very small amount of input, then you have to be completely finished dealing with that input, before going on to the next input. While I understand Google's need for people who can deal with asymptotic behavior, five of my six interviews there were for Site Reliability Engineering. I would expect an SRE to look for software bugs, sometimes hardware bugs. Consider that with hundreds of thousands of servers, quite likely at least a few of them have defective memory. I had some ideas for an automated way to find all the defective memory in an entire data center, but no they didn't want to discuss that with me, they wanted me to come up with a certain of scalable algorithm.
  - yeukhon 11y ago
    Well I'd be thrilled to hear your ideas, or tips what to read to get myself into that area (yeah I work as DevOps but still early on in my career). I am not sure if even in the case of Google the engineers are sorting some big N in one iteration, or merely just interview questions. Regardless I think knowing one or two techniques how to sort big array is useful...

yeukhon 11y ago

Do people read in 1M elements at once? I think when it comes to consuming big chuck of input stream, the idea is streaming or split into smaller manageable chunks. I find in practice the hardest thing is to use the right technology rather than finding an algorithm.

MichaelCrawford 11y ago
There are certain applications where big N is common. Web search, for example. But in typical GUI applications, you get a very small amount of input, then you have to be completely finished dealing with that input, before going on to the next input. While I understand Google's need for people who can deal with asymptotic behavior, five of my six interviews there were for Site Reliability Engineering. I would expect an SRE to look for software bugs, sometimes hardware bugs. Consider that with hundreds of thousands of servers, quite likely at least a few of them have defective memory. I had some ideas for an automated way to find all the defective memory in an entire data center, but no they didn't want to discuss that with me, they wanted me to come up with a certain of scalable algorithm.
- yeukhon 11y ago
  Well I'd be thrilled to hear your ideas, or tips what to read to get myself into that area (yeah I work as DevOps but still early on in my career). I am not sure if even in the case of Google the engineers are sorting some big N in one iteration, or merely just interview questions. Regardless I think knowing one or two techniques how to sort big array is useful...