Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
11  
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 Oct 6 '12 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. –  faif Oct 7 '12 at 11:00
2  
I'm sure it's important to memorise these algos for the frequent occurrence of Google being offline. :o –  Lee James Oct 11 '12 at 18:23

7 Answers 7

up vote 95 down vote accepted

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

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.

share|improve this answer
3  
That just makes me feel better about myself! –  Roopesh Shenoy Oct 7 '12 at 9:18
3  
This citation is dubious: I am "unable to find any substantive evidence connecting the saying to Einstein". –  Wok Oct 7 '12 at 11:01
8  
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 Oct 7 '12 at 15:08
2  
@YannisRizos -- thanks for the good edit. Regarding the quote: I know that its provenance has been questioned, and I've seen it phrased a couple of different ways, but the essence of the idea is still valid: remembering minutia is what books and libraries are for. –  Peter Rowell Oct 7 '12 at 22:42
2  
@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 Oct 11 '12 at 19:55

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.

share|improve this answer
  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?

share|improve this answer
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 Oct 7 '12 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 Oct 12 '12 at 20:50
1  
@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 Oct 13 '12 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 Oct 14 '12 at 8:06

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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 Oct 9 '12 at 20:17

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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