59

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?

Improve this question
6
  • 13
    You need to remember that a solution exists and when to use it. Then go into the docs and implement it. If you hadn't known about quicksort or mergesort, you'd still be using bubblesort and watch your program go to a crawl and come up with subpar solutions when data increases.
    – Pieter B
    Commented Oct 6, 2012 at 22:42
  • 1
    Apart from the good answers mentioned below, note also that many companies require to (1) know the complexity of such algorithms, (2) be fluent in implementing them on a blackboard.
    – sakisk
    Commented Oct 7, 2012 at 11:00
  • 3
    I'm sure it's important to memorise these algos for the frequent occurrence of Google being offline. :o
    – Lee James
    Commented Oct 11, 2012 at 18:23
  • You need to know their performance, use cases, etc. Knowing how to implement them by heart is something that is only required by tech companies in interviews.
    – sakisk
    Commented Sep 8, 2014 at 11:11
  • @PieterB, I disagree. One does not need to know about 'mergesort' and 'quicksort' to Google 'best performing sorting algorithm'
    – hyankov
    Commented Sep 6, 2017 at 13:23

7 Answers 7

Reset to default
119

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.

Improve this answer
8
  • 5
    This citation is dubious: I am "unable to find any substantive evidence connecting the saying to Einstein".
    – Wok
    Commented Oct 7, 2012 at 11:01
  • 9
    How does that answer the question? He said “I don’t need to know everything”, he did not say “I don’t need to know anything”. Some skills are fundamental, and the whole question was about whether a particular piece of information belonged to the category of fundamental skills or not.
    – Konrad Rudolph
    Commented Oct 7, 2012 at 15:08
  • 1
    To think that the goal is to memorize quicksort is to miss the point of the question. Of course, in the real world, if you needed a generic quicksort, you'd use the library routine or look up the code and copy it. The test is to see if you understand recursion, loop invariants, etc., and asking you to quickly jot down a sort algorithm is just a really simple demonstration of that knowledge. If you aren't capable of re-deriving a 20-line quicksort on the spot, how many things are you routinely doing really inefficiently or incorrectly without even knowing it?
    – Larry Gritz
    Commented Oct 9, 2012 at 20:09
  • 3
    @Larry: I think I have forgotten more than many programmers know about details of algorithms- and Quick sort from scratch is one of them - for a very good reason - I have chosen to read up on high level things and use high level languages rather than stay down in bowls of low level implementation detail. Frankly - I don't care what sort the library routine I am using uses - it can use pixy dust and fairies as far as I am concerned. The Docs will tell the O() for sizing- that is all I need to know.
    – mattnz
    Commented Oct 11, 2012 at 19:55
  • 2
    @mattnz: A somewhat belated followup to your "O() sizing". One thing I learned the hard way was that with a large dataset bad locality of reference can completely overwhelm the O(). You may have an algo that is O(n log n), but if you get a lot of cache misses or (God forbid) you hit the disk, then that n log n will be but a fond memory.
    – Peter Rowell
    Commented Nov 6, 2012 at 17:47
48

  1. 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.

  2. 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?

Improve this answer
4
  • 5
    I do not think it's possible to understand QuickSort without remembering QuickSort. It's not a complicated and arcane thing, it's just two generic ideas combined. The same thing applies to merge-sort, but there you have just one idea :P
    – drxzcl
    Commented Oct 7, 2012 at 20:05
  • I disagree with 2nd point. all jobs are the same, only interviewer changes. this one knows sorting very well and thinks every good programmer must know sorting, because that is all he knows and cares about.
    – IAdapter
    Commented Oct 12, 2012 at 20:50
  • 2
    @IAdapter, surely you jest! I know from my own experience that the knowledge and skills I needed for my first job writing TROFF macros for a shrink-wrap software company are very different from the ones I need for my current job in a computational biology lab.
    – Charles E. Grant
    Commented Oct 13, 2012 at 22:37
  • @CharlesE.Grant most of the time interviwer doesn't check if you got skills you need to do your job (I can't remember last javascript/css question I was asked and I do webapps).
    – IAdapter
    Commented Oct 14, 2012 at 8:06
10

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.

Improve this answer
6

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.

Improve this answer
5

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.

Improve this answer
3

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.

Improve this answer
2

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.

Improve this answer
1
  • I used to think asking people to program on interviews was silly, but you just wouldn't believe the number of people with seemingly fantastic resumes and who answer the "social" questions with flying colors, but who, for the life of them, cannot jot down a correct implementation of 'strcat' or some other simple function. Several times this has saved me from hiring somebody who, if it had not been for the silly coding question, could have caused endless grief and dragged the team down with incompetence.
    – Larry Gritz
    Commented Oct 9, 2012 at 20:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.