I was reviewing my notes and stumbled across the implementation of different sorting algorithms.
As I attempted to make sense of the implementation of QuickSort and MergeSort, it occurred to me that although I do programming for a living and consider myself decent at what I do, I have neither the photographic memory nor the sheer brainpower to implement those algorithms without relying on my notes. All I remembered is that some of those algorithms are stable and some are not. Some take O(nlog(n)) or O(n^2) time to complete. Some use more memory than others…
I’d feel like I don’t deserve this kind of job if it weren’t because my position doesn’t require that I use any sorting algorithm other than those found in standard APIs. I mean, how many of you have a programming position where it actually is essential that you can remember or come up with this kind of stuff on your own?
6
Let’s ask Albert and see what he has to say on the subject:
“I don’t need to know everything, I just need to know where to find it, when I need it”
— Albert Einstein, paraphrased
Amen, Brother Albert, Amen.
Once you’ve made a good survey of the essential algorithms in any particular discipline (sort, search, whatever), you can then forget about the implementation details until you actually need the algo, in which case you go look it up or use a preexisting lib. 25 years ago I built a major search system using B*-trees, but today I would need to RTFM in order to use them well.
8
-
It’s not really a matter of memorization. It’s a matter of deeply understanding general classes of algorithms like divide and conquer. If you really understand divide and conquer, then you don’t need to memorize quicksort. You can re-derive it on the spot as needed. Furthermore, the real payoff isn’t even in being able to re-derive quicksort on your own, it’s that you can recognize when a new problem is amenable to a divide and conquer solution.
-
Not all programming jobs are the same. Some jobs need a profound knowledge of algorithms, some need folks who understand type theory, and some just need folks that can scrape data from a web form and move it to a database. Some jobs even need all those skill at once. What kind of job do you want to work at?
4
I think the only time you need to remember it all is when applying for a job when you have to come up with answers on the spot and have no outside resources.
I’ve had coworkers rewrite quicksort and whatnot, but I keep telling them to go back to using the built in sorting functions that are in the language. I do know that depending on what types of projects we work on we do have to remember other algorithms since they’re not usually included in standard libraries, but sorting isn’t one that comes up since it’s usually built into the language.
When we do need to remember those algorithms though, we usually turn to google or a book, and usually it’s not looking for a specific implementation, but what would be the best implementation for our problem.
Just remembering which algorithm is useful in what scenarios, would be more than enough to help during your work. In fact, most programming jobs don’t require the memorization of approach, rather they are interested in your way of recognizing algorithmic pattern when faced with the problem.
As a matter of fact, there is abundance of information in most programming blogs/articles on algorithm topics. Thus, memorizing exact implementation does not carry importance. Most valuable information would be getting basic idea on what type of algorithm’s are available, and what specific problem are they good in solving. Searching for exact implementation once you know what you are looking for is pretty fast.
In summary, it is always better to know what you look for and where are the references – which will guide you to the source.
The exact implementation is not very important. But the principle behind mergesort / quicksort – recursion, partitioning etc, are very basic one and every programmer should understand. These algorithm are actually very simple to describe in words once you understand.
It’s not really a problem of whether you can look it up or whether you can google it, it is whether programmer understand these problem solving techniques and able to apply to other situations.
I’m of two minds on this subject. I know many programmers who don’t know what a sorting algorithm is, but do their job fairly well. I also believe in understanding principles in order to truly understand the domain.
It is hard for me to have an unbiased answer on this subject as I have been programming for so long I have probably forgotten more algorithms that I currently know – but I still know the sorting ones mentioned in this question. I think the thought leaders in Agile (e.g. Ron Jeffries, Alistair Cockburn) have some good ideas near this idea (e.g. Shu-Ha-Ri).
In summary to this rambling answer: Definitely use the API (NIH is a sign of developer immaturity), but always understand the underlying principles. I hope this helps.
Sorting and searching are amazingly important, whether you are a Donald Knuth fan or want to be the next Larry Page. Depending on the business you are in, and the level of competition you can command among your candidates, I would recommend that you include some of the following concepts in the interview.
Sorting
- Sketch of some kind of sorting algorithm.
- List some examples of sorting algorithms.
- Compare/contrast two sorts with different performance characteristics.
- If they don’t mention memory use, ask about it.
Searching
- Name as many search algorithms as you can.
- Compare/contrast two search algorithms.
- Sketch any search other than linear search.
Some might say that requiring the code for these algorithms is overkill unless the job is on a deserted island with no internet connection. Another consideration is that if you have 30 minutes, and you want to ask about anything else, for many candidates, implementing the sort could take a big chunk of your time.
1