What algorithms should every developer know?
[+153] [34] dotnetdev
[2009-01-15 02:26:29]
[ algorithm ]
[ http://stackoverflow.com/questions/445425/what-algorithms-should-every-developer-know ] [DELETED]

I know there is a thread about what every developer should know but this is really a list of topics, such as xml, software licensing, various important distinctions (e.g. value/reference types), and many general topics (xml etc being important as they are used in code to construct xml documents etc).

Anyway, as I am working on some of those topics above, what algorithms should every dev know? I ask because many job interviews involve a short practical test which involves implementing a common algorithm (like a linked list, ok this isn't an algorithm but something every dev should know how to code). I already have a class library with some basic, common algorithms but I want to expand on it to include complex and rare algorithms not really well known in computer science.

It would be very welcomed if you could provide algorithms asked for in tests when you applied for jobs at dev shops or large companies like Microsoft/Google.

I hear a lot about A*, Dijkstra and the travelling salesman problem so I will learn about these. I understand the 8 basic sort algorithms (although probably can't remember all the subtle differences). Also, to compliment this activity, I am reading data structures and algorithms with C# (my main language I use to write code).

Any suggestions guys?

bu.edu/wcp/Papers/TEth/TEthHerb.htm "The HL Model in Book III shows Aristotle's inexact algorithm for a happy life through choices of actions and feelings "up to us" alone or with "partners in deliberation" we enlist on major issues (1112b 8-12) to help one fashion one's moral character." - Akusete
(1) Dikstra should be Dijkstra. - tuinstoel
There are some interesting answers to a similar questions over here: stackoverflow.com/questions/328799/… - splattne
(2) should be community wiki - SilentGhost
lather. rinse. repeat. - Steven A. Lowe
Fisher–Yates shuffle (the modern algorithm) en.wikipedia.org/wiki/… - Eran Medan
[+38] [2009-01-16 09:47:05] Fabian Steeg

Besides knowing particular algorithms, it might also be useful to practice general algorithmic techniques like:

A nice place to apply these to different new problems are the TopCoder algorithm competitions [6] and practice rooms [7].

[1] http://en.wikipedia.org/wiki/Proof_by_exhaustion
[2] http://en.wikipedia.org/wiki/Recursion
[3] http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
[4] http://en.wikipedia.org/wiki/Memoization
[5] http://en.wikipedia.org/wiki/Dynamic_programming
[6] http://www.topcoder.com/wiki/display/tc/How+To+Compete+in+Algorithm+Competitions
[7] http://www.topcoder.com/wiki/display/tc/Practicing+in+the+TopCoder+Arena

(1) as far as programming is concerned, memoization and dynamic programming are the same thing - Graphics Noob
(4) Hm, it is my understanding that memoization optimizes a recursive solution but is still a recursive top-down solution, while dynamic programming does a sort of bottom-up simulation of the recursive solution by filling a table. - Fabian Steeg
I've seen both described as dynamic programming - I think (but am not certain) that includes some algorithms textbooks. Also, memoization is often done for iteration-with-explicit-queue algorithms. A lot of classic "AI" searches take this form. One reason for an explicit queue is that it may be a FIFO queue, LIFO stack, priority queue or whatever, giving different search orders. There are named variations of the memoization technique, such as Zobrist hashing within minimax, alpha-beta and similar game "tree" (strictly digraph) search methods, e.g. for chess. - Steve314
None of the items on your list is considered to be an algorithm. Examples for algorithms: BFS, DFS, ways to traverse binary-trees (pre/post/in-order), different types of sorting: quick-sort, merge-sort, bubble-sort, etc... "Divide and conquer " and "Dynamic programming" are considered as "families of algorithms" while memoization is a Technic used in Dynamic programming in order to save computation-time. - alfasin
1
[+32] [2009-08-08 17:50:50] Juliet

At a bare minimum, every developer should know how to:

• Implement a binary search on a sorted array.
• Implement a singly linked list from scratch, and know how to determine whether a singly-linked list contains a cycle in O(n) time.
• Merge two sorted arrays into another sorted array. Assuming a developer knows that, they should be able to implement a merge sort from scratch.
• Implement a bubble sort.
• Solve the FizzBuzz problem. Seriously.
• Insert, lookup, and delete an item into a binary tree. (Note: shouldn't be concerned about keeping the tree balanced or not.)
• Implement a hashtable with O(1) (or very nearly O(1)) lookup, insert, and deletes.
• Construct an array of fibs from 0 to n in O(n) time.
• Construct an array of primes from 0 to n using Sieve of Eratosthenes.
• Implement a depth-first search of a binary tree.
• Implement a breadth-first search of binary tree.

None of these are particular difficult for a competent developer, even if you've never implemented them before.

And while its not a requirement, I think its important for developers to know:

• A smidgen about graph data structures, even if they never use them a lot in practice. Developers should familiarize themselves with Dijkstra's algorithm, Prim's algoritm, and Kruskal's algorithm.
• How to solve Knight's Tour and 8-Queens puzzle.
• How to write a basic minimax function.
• Given a particular arrangement of a chess board, determine whether a king is checkmated.
• How to find the best poker hand in a set of 5 or more cards.

(14) "Implement a bubble sort." - for crying out loud! No! No! No! - Mitch Wheat
+1 These are all problems that we had to solve for homework in my high school Turbo Pascal class. Seriously, if you can't solve the FizzBuzz problem go take your Coms/fine arts degree and apply for a nice position in the service industry. - Repo Man
(4) Why not a bubble sort? It's not that it's a good algorithm, it's that a competent developer should understand the concepts involved and therefore be able to do it. - Gravity
(7) I disagree this is a bare minimum each developer should know. I'm sure most developers won't know how to implement a tenth of that from scratch (without reference). If I ever need to "Construct an array of primes from 0 to n using Sieve of Eratosthenes", I'll look it up on Google, but I see no point knowing it for the sake of knowing it. - Laurent
2
[+30] [2009-01-15 03:29:30] Bill the Lizard

There are three categories of algorithms that you'll get a lot of use out of.

• Sorting
• Searching
• Inserting and removing from various data structures

If you understand several of each of these you'll have the basics down. This might not be a popular idea, but I think that these are the only three that everyone must know. Anything beyond these three is going to depend on what area you're interested in. Game programmers are going to learn a lot of algorithms in graph theory, but a Web developer might not find much use for them, for one example.

3
[+20] [2009-01-15 02:47:59] Epitaph

I think, the ability to come up with different ways to solve a particular problem (i.e. building your own algoirithms, no matter how simple/trivial it may be) is a more important skill to have (and harder to develop).

Remember, you can't always know all the possible algorithms that may be asked in an interview. But, what you will be tested on is how efficiently you can think on your feet when given a complex problem. However, knowing and understanding a lot of algorithms can help in developing this skill.

(1) I think learning and implementing existing algorithms is an important skill as well. If you can't learn an algorithm and provide an implementation within a reasonable amount of time (say, two or three days for A*), your usefulness is lessened in my eyes. - strager
(1) @strager: I agree. And, I have mentioned that in the last line of my answer. - Epitaph
(3) @Pat, Not what I meant. I mean, reading up on an algorithm and implementing it. If, for example, a candidate had no knowledge on how quicksort works, a good candidate would be able to research the subject and code an implementation relatively quickly (and nicely), and probably teach the interviewer. - strager
I got it now, and it makes complete sense. - Epitaph
4
[+17] [2009-01-15 03:29:28] paxdiablo

Two I've used for interview purposes:

• Given an array of 100 numbers, work out how to calculate the min, max and average.
• Given an array of 9 values representing a Tic Tac Toe game (or Noughts and Crosses, depending on where you're from) where the values are -1, 0 or 1, figure out who, if anyone, has won.

Yes, I realize these are very simple and we could all knock them off very quickly, but I'm not testing for the end product and I don't want them sitting down for two hours trying to nut out something complicated.

I want to see the process followed to arrive at a result (so I get them to white-board the entire thing, explaining as they go). It's more to see if they have problem solving ability. That's far more important than knowing the algorithms off the top of their head.

I really don't care if they can code up a bubble sort (it's a crappy sort algorithm for large data sets anyway and, if you need some sort code, you'll be using something built in to the language, pulled out of Wikipedia or found with Google, not writing your own - I'm not going to be happy paying you to re-invent the wheel).

The problem with asking someone to come up with a complicated algorithm is that they won't be doing that on the job. Most code is very simple stuff so you may as well just ask them to code up a for-loop. By all means ask them about algorithms and see what they know. For example, ask them how they would sort an array. I wouldn't hire anyone who coded up a bubble sort (or even a quick sort, for that matter). I would consider hiring them if they knew that different sort algorithms have different properties depending on the data set.

The best response in my view to a question like "Can you implement an array in Perl which uses a string as an index?" is not "Yes". It's either "Perl already has those, they're called associative arrays" or "No, but I know how to find code that's freely available to use on the net". Of course, if they come up with an O(n) or O(1) sort algorithm, I'll hire them on the spot :-).

As an aside, one guy answered the Tic Tac Toe question by transferring the board to the center of a 7-by-7 matrix (with the outer squares set to 0), then looping on the inner squares, checking for three of the same value in every direction to "simplify the algorithm" as he put it (not needing to worry about crossing over the boundaries of the array). Something like (and I kid you not, the amount of comments was the same as shown here):

``````int board[7][7];
for (col = 2; col < 5; col++) {
for (row = 2; row < 5; row++) {
board[row][col] = 0
}
}
board[2][2] = arr[0];
board[2][3] = arr[1];
board[2][4] = arr[2];
board[3][2] = arr[3];
board[3][3] = arr[4];
board[3][4] = arr[5];
board[4][2] = arr[6];
board[4][3] = arr[7];
board[4][4] = arr[8];
for (col = 2; col < 5; col++) {
for (row = 2; row < 5; row++) {
for (coldir = -1; coldir < 2; coldir++) {
for (rowdir = -1; rowdir < 2; rowdir++) {
if ((coldir != 0) || (rowdir != 0)) {
sum = 0;
for (i = 0; i < 3; i++) {
sum = sum + board[row+i*rowdir][col+i*coldir];
}
if (sum == -3) return -1;
if (sum ==  3) return  1;
}
}
}
}
}
return 0;
``````

It was an innovative approach but way too complicated compared to the 8 if-statements that most people came up with. Still I gave him a chance to explain his reasoning and, in his "Thanks but no thanks" letter, I let him know why he didn't get the job (this code was just one of the reasons) so hopefully, he's improved himself and is now gainfully employed.

And, before anyone asks, the 8 if statements are:

``````if ((arr[0] != 0) && (arr[0] == arr[1]) && (arr[0] == arr[2])) return arr[0];
if ((arr[3] != 0) && (arr[3] == arr[4]) && (arr[3] == arr[5])) return arr[3];
if ((arr[6] != 0) && (arr[6] == arr[7]) && (arr[6] == arr[8])) return arr[6];
if ((arr[0] != 0) && (arr[0] == arr[3]) && (arr[0] == arr[6])) return arr[0];
if ((arr[1] != 0) && (arr[1] == arr[4]) && (arr[1] == arr[7])) return arr[1];
if ((arr[2] != 0) && (arr[2] == arr[5]) && (arr[2] == arr[8])) return arr[2];
if ((arr[0] != 0) && (arr[0] == arr[4]) && (arr[0] == arr[8])) return arr[0];
if ((arr[6] != 0) && (arr[6] == arr[4]) && (arr[6] == arr[2])) return arr[6];
return 0;
``````

But you knew that already, I'm sure.

To generalize it, we can also use this pseudo-code:

``````const SIZE=3

// cells_array is a sized SIZE*SIZE array

function cell(x,y)
return(cells_array(x+y*SIZE))

function get_winner(z)
result=0
if abs(z)=SIZE then result=sign(z)
return(result)

for i = 0 to SIZE-1
sumrow=0; sumcol=0; sumd1=0; sumd2=0
for j = 0 to SIZE-1
sumrow=sumrow+cell(i,j)
sumcol=sumcol+cell(j,i)
if (i==0) then // We only need diagonals calculated once!
sumd1=sumd1+cell(j+j)
sumd2=sumd2+cell(j+SIZE-j-1)
winner=0
if (winner==0) then winner=get_winner(sumrow)
if (winner==0) then winner=get_winner(sumcol)
if (winner==0) && (i==0) then winner=get_winner(sumd1)
if (winner==0) && (i==0) then winner=get_winner(sumd2)
``````

(37) Huh. I'd be pretty unimpressed with the 8 if statements, after all, I would assume a solution that could be adapted intuitively adapted to NxN games. Figuring out a boolean formula for a tic tac toe game isn't very impressive at all. - Chad Okere
(26) Then you probably won't be working for me, Chad :-). If you suggest that I may want a more extensible algorithm, that's fine (and I would have said "no, just tic tac toe"). If you decide unilaterally to implement a more complicated one, you're well outside the specs and wasting my time and money - paxdiablo
And, on top of that, you missed the whole point of my answer. I want to see your problem solving ability, I don't care how simple the answer is, I want to see your brain in action. Which of those solutions do you think runs faster? Which is easier to maintain? - paxdiablo
I would question each choice you made and ask you to justify it (in a non-confrontational way). I would suggest improvements and see how you take them on board. And "unimprovements" to see how you handle telling the boss he's wrong. The possibilities are endless. - paxdiablo
You should never hire someone who codes up a bubble-sort! Period! - Mitch Wheat
(34) @Pax: I'm also unimpressed with the 8 if statements. The fact you think that is acceptable means I probably wouldn't want to work for you ;) I've had to maintain code like that, and it suks. - Mitch Wheat
(14) Why do you think I'd want to work for you? An important part of problem solving ability is the ability to come up with good solutions, not just any solutions. Good solutions are adaptable, extensible, and easily readable. Your if-statement design is none of those. - Chad Okere
(2) The first method for solving TTT for me was to iterate through each row and column and check if they all matched. (By your structure, the absolute value of the sum would be 3 if a player has won.) Diagonals are handled in another iteration similarly. Changing the stop point allows for expandability. - strager
(3) yeah, seeing 8 chained if statements would be a major deal-breaker for me. Aside from being inflexible (to which YAGNI might apply), it doesn't express intent in an obvious way. - Jimmy
Okay, one at a time. @Mitch, I hope you're not suggesting that the first example is more maintainable than the second. Or do you have another solution in mind? - paxdiablo
@Jimmy, adding a 2-line comment should be more than enough to explain intent and that was the best submitted from the interviewees. I think you misunderstand YAGNI - it's the full blown 7x7 matrix solution that violates YAGNI since ALL you need is a solution for tictactoe, not something extensible. - paxdiablo
@Chad, I think you missed my smiley. I agree with your "good solutions" comment but NOT that they are adaptable or extensible. Good solutions solve the problem at hand. I already stated that the code was to never be used for anything else, so making it adaptable is a waste of time and money. YAGNI. - paxdiablo
(2) And anyway, this discussion validates my answer - the intent of the tests is to see how interviewees handle the problem solving process and these are the sorts of arguments I'd expect to see in the interview, which would show that people had the required nous. (cont) - paxdiablo
(1) (cont) Ability to tell the boss he's wrong is also important, but so is the ability to back down - he's paying the bills after all and, if he decides he doesn't want extensibility, that's it. You can always find employment elsewhere :-). - paxdiablo
If you showed me the if statement solution on your job interview - my next question would be "ok, nice and simple - however we have a challenging mode in a game where tic tac toe is extended to a 30x30 matrix, how would you extend your solution now?" - Keyframe
(2) @Keyframe, I wouldn't extend that solution, I'd come up with another one. But that's my point. TicTacToe is a 3x3 game and, if you'd read the comments before yours, you would have seen that was part of the interview process, stating that there would be no extension of the algorithm. - paxdiablo
(2) The act of asking the question (will it be extended) would certainly have earned you points but not unilaterally deciding that it should, above and beyond the spec. - paxdiablo
I took a few pseudocode shortcuts and my syntax is rusty, but forgiving those faults... how would this solution fare in your interview? I spent about 5 minutes on it, and it would take about 10 more to make it runnable. (forgive the lack of formatting in a comment) map { \$oh=\$oh*2+(\$_>0) } @arr; map { \$ex=\$ex*2+(\$_<0) } @arr; @win = { 0b111000000, 0b000111000, 0b000000111, 0b100100100, 0b010010010, 0b001001001, 0b100010001, 0b001010100 }; map { if(\$oh&\$_==\$_){return 1} } @win; map { if(\$ex&\$_==\$_){return -1} } @win; return 0; - Sparr
(16) @paxdiablo Unfortunately we've all been burnt by the scenario where the spec 'definitely won't change', and then next week it changes. As long as the effort involved is not significantly greater, it's pretty hard to argue against a more extensible solution. Let the poor programmers enjoy their work! - Kirk Broadhurst
(1) fwiw i'd agree that those 8 if statements are NOT a good idea regardless of how certain the requirements are that the dimensions and the rules will stay the same. i'll be more direct: that code gives me the shivers. - Epaga
(1) "if they come up with an O(n) or O(1) sort algorithm" What? Comparison-based sort is Ω(n log n), non-comparison-based sort is Ω(n), how can you have O(1)? Or am I missing the joke again? - KennyTM
@Kenny, there's a smiley :-) at the end of that sentence so, yes, you missed the joke. I was saying that if they delivered a O(1)/O(n) sort algorithm during the interview, I'd hire them on the spot (and ensure the work-for-hire clause about my company owning all IP was in the contract) regardless of the quality or otherwise of their code. - paxdiablo
On a related note, I'd say that array shifting solution was someone that's used to working with something like APL. In APL there are ops for shifting and comparing matrices. See for example this implementation of conways game of life in APL that works completely by shifting and comparing matrices: kallokain.blogspot.com/2009/06/conways-game-of-life-in-apl.html Now, the odds of running into an APL programmer are probably pretty slim, but someone that's worked with GPU programming would probably come up with a similar solution. - Orclev
(2) I wouldn't work for you. If 8 if-statements seem 'good' then you can't see repetition in code and rely on copy-paste. Pseudocode `for x in [[0,1,2],[3,4,5],[6,7,8],[0,3,6]...]: if b[x[0]] != 0 && b[x[0]] == b[x[1]] && b[x[1]] == b[x[2]]: return b[x[0]]; return 0` is much easier to write, read and modify. If you make a single mistake in a number in 8 conditional statements it means you have to read the whole thing again. - sdcvvc
Does the 8 if statements screams "use bitwise", or is it just me ? :) - alfasin
5

Being able to implement basic search algorithms from CS101 like quicksort and the like isn't really all that important, every language has flexible, built-in implementations these days, and I can't remember the last time I had to call one directly. If I need something sorted, I'll store it in a sorted set.

The problem here is that you're not asking what algorithms you should know to make you a better developer you asking what algorithms you should know to make you a better interviewee. And there's no way to know that, because every interviewer will be different, and you can always have bad developers who manage to make it into management. Frankly, I think interviewers who ask CS101 style trivia questions are probably not that bright themselves.

Now, if you really want to be a better programmer, I think the best thing to do is have a broad and deep understanding of what the available libraries can do, first of all. So if I was looking for a java developer I'd want someone who could answer questions about the collections API and how to solve some simple problems by combining them in ways that let them look up information quickly.

(3) Certain organizations are looking for people who have an inherent talent for understanding and innovating on algorithms. Knowing how to implement quicksort isn't quite the test, it's understanding it on a deep level. Knowing why it's good, or where it can be bad. Knowing it's cost in computation and space. Knowing alternate approaches given different constraints. - Mark Renouf
Inherent talent? Where is that defined? - Rhubarb
(3) +1 - These types of questions judge computer science knowledge more than development skills. The two just aren't as closely related as many people would like to believe. I wouldn't be interested in working with anyone who doesn't understand that distinction. - Zach
6
[+10] [2009-01-15 02:36:46] Randolpho

I guess it depends on what you are looking to do. Very few developers actually get to implement the algorithms you use in your example in their daily lives. In truth, they're solved problems.

If you're one of the lucky few actually building fundamental libraries rather than the typical enterprise glue-code, then I would argue that an understanding of the approaches and patterns for algorithms would be a better topic of interest. Stuff like divide and conquer, dynamic programming, greedy, backtracking, genetic.

If you ever get to do something like that, you'll be in a very elite group.

7
[+9] [2009-01-15 03:31:49] Steven A. Lowe

you should know of the existence of several algorithms - hashing functions, hash tables, quicksort, merge-sort, depth-first and breadth-first graph traversal, neural networks, genetic algorithm, genetic programming, recursive descent parsing, etc.

you should reinvent none of them.

+1 - for not reinventing at least in the workplace with deadlines to meet. Reinvent at home for educational purposes:-) - Jay Atkinson
8
[+8] [2009-01-15 03:01:01] Drew Hall

The obvious two:

• Binary Search
• QuickSort

(4) I wouldn't say you have to know them in implementation details. You have to know about them: that they exist, their strengths and weaknesses... - Ray
9
[+7] [2009-01-15 05:51:56] Pukku

You really should not forget the ability to analyze the algorithms you learned or designed yourself, preferably by using standard big O notation (try to master big Theta and friends as well).

For instance, you could be asked to compare the eight sort functions you learnt. Or to compare a well-known algorithm to something esoteric (which is most probably the one you just developed as an answer to a question that you were presented for the first time). If efficiency is of any essence (instead of, e.g., readability), then you should be able to analyze the algorithmic complexity of each option, and consequently decide on the asymptotically best choice. (In addition to that, you could of course mention that for a small N, something else would work faster, if that's the case.)

+1 Agree! This is the main reason you will be asked about algorithms. It's not only if you know how it works or are able to implement it quickly. It's whether you understand why it works, and where it's strengths and weeknesses are, and in what situations another choice would work better. - Mark Renouf
10
[+6] [2009-01-15 13:23:21] Nifle

I think it's vital for a developer to recognize a bad algorithm.
And for that I really think you need to be familiar with "Big O" [1] notation.

[1] http://www.perlmonks.org/?node_id=573138

11
[+5] [2009-01-15 02:35:34] DrJokepu

I suggest asking them to code some very simple algorithm. Even a very simple algorithm weeds out the incompetent and allow the talented to shine. I've read about this on Joel On Software and actually when I tried it out in real life it worked excellently.

Ask them to code a bubble sort algorithm. Bubble sort is really simple, everyone should be able to do it in a couple of minutes, right? Well, apparently not. Only the fair/good ones and the very good ones will be able to do it, and even though it is just a few lines of code you will see that you will be able to just tell the difference in the skills of the applicants.

This way, you will save a lot of time that can be spent on something more useful, like selling your company to the best applicants.

EDIT: To put it other way, from the perspective of a job seeker, I would just concentrate on the most basic stuff you have learned at university on the Data Structures class, like sorting, handling binary trees, etc. Anything else is not really relevant on a job interview unless of course you are applying for a position in a very specific domain (e.g. if your job would be writing compilers, it doesn't hurt to know a little bit about lexers)

I remember an article on CodingHorror about a very simple problem involving nested loops and to display a message when a number contains a certain "characteristic" - something like if it is prime. Many candidates failed this. Also, some of this stuff is so obscure or not used you forget it. - dotnetdev
-1: This answer doesn't seem to match the question very well at all. Maybe I'm missing something, but this doesn't seem to address what the questioner needs to learn. - S.Lott
Well actually it does. The sort algorithms are fundamental and count. Any fundamental algorithm or data structure like sort methods, trees, travelling salesman problem, anything covered in a technical degree - count. Also, I don't run a company :) - dotnetdev
when is the case that we ever use Bubble sort? Isnt its complexity n^2? Is all developer going to always use whatever sort function that's provided by the language? - ShaChris23
12
[+5] [2009-08-19 10:21:04] David Lehavi

quoting from: Francis Sullivan, "The Joy of Algorithms," Computing in Science and Engineering, vol. 2, no. 1, pp. 2, Jan./Feb. 2000, doi:10.1109/MCSE.2000.10000, these are the "10 algorithms of the century" (this was written in 2000). Does not exactly answer your question, but certainly has some relevance.

the Monte Carlo method or Metropolis algorithm, devised by John von Neumann, Stanislaw Ulam, and Nicholas Metropolis;

the simplex method of linear programming, developed by George Dantzig;

the Krylov Subspace Iteration method, developed by Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos;

the Householder matrix decomposition, developed by Alston Householder;

the Fortran compiler, developed by a team lead by John Backus;

the QR algorithm for eigenvalue calculation, developed by J Francis;

the Quicksort algorithm, developed by Anthony Hoare;

the Fast Fourier Transform, developed by James Cooley and John Tukey;

the Integer Relation Detection Algorithm, developed by Helaman Ferguson and Rodney Forcade; (given N real values XI, is there a nontrivial set of integer coefficients AI so that sum ( 1 <= I <= N ) AI * XI = 0

the fast Multipole algorithm, developed by Leslie Greengard and Vladimir Rokhlin; (to calculate gravitational forces in an N-body problem normally requires N^2 calculations. The fast multipole method uses order N calculations, by approximating the effects of groups of distant particles using multipole expansions)

13
[+4] [2009-01-15 02:33:08] strager

Steve Yegge [1] outlines several important programming-related things to know, including several algorithms and data structures. (Scroll down to "Tech Prep Tips" on the blog post.)

14
[+4] [2009-09-26 13:52:50] Jason Baker

I don't think it's necessarily that important for you to know any algorithms at all. I think it's more important to understand how to analyze algorithms and choose the best one for the given situation. After all, if programming were just about memorizing algorithms and implementing them, any idiot could do it.

15
[+4] [2010-02-28 05:56:10] fastcodejava
• How to do binary search.
• How to traverse a binary tree.
• How validate a binary tree.

16
[+3] [2009-01-15 02:30:27] Paul Beckingham

Lexing and Parsing techniques have been invaluable to me. I realize these aren't algorithms, but knowing how to do this well is extremely useful.

Lexing and parsing aren't algorithms, but recursive descent LL and LR(0) state machine certainly are. :) - 280Z28
17
[+3] [2009-01-15 02:33:34] Nick Presta

I don't want to reiterate what has and will be said - sorting, trees, hash maps, etc.

Instead, I will give some practical advise. Know what sort of algorithms you will be using, and learn those in great detail.

For example, most languages will provide a sort algorithm, etc, but it is important that the developer understands how it is implemented within the language and when it is a good/bad time to use it.

18
[+2] [2009-01-15 03:36:21] Norman Ramsey

Interviews I've had at Google tended to focus less on sophisticated algorithms and more on my ability to code simple algorithms cleanly, quickly, and well. I remember being asked such problems as reverse a string, reverse the words of a string (i.e. print the normal words but in the opposite order), and binary search. For all of these it really helps to know your loop invariants as described in David Gries's book The Science of Programming [1]. It's also very good to have a deep understanding of two or three recursive algorithms; it doesn't matter which ones. But you want to be able to recognize when recursion is called for.

The one hard algorithm I got asked was about an algorithm for the stable marriage problem, but we got a bit bollixed up because my interviewer knew the answer he was looking for, but he couldn't quite remember a precise statement of the problem.

If you have it in mind to interview, I suggest you spend at least as much time having a friend ask you to code algorithms at the board as you do learning new algorithms.

19
[+2] [2009-01-15 05:37:32] Barry Wark

There may be a large difference between what a developer should know and what they need to know. For example, most of us can get away knowing a very few data structures and the simplest (even non-optimal) algorithms that operate on those structures. Designers, framework developers, real-time application, OS, AI and game developers, to name just a few, may need to know substantially more. You question may really be aimed at the academic: what are the foundational algorithms of our trade? For the answer to this question, there's no better source than Donald Knuth's "The Art of Computer Programming" [1].

[1] http://www-cs-faculty.stanford.edu/~uno/taocp.html

20
[+2] [2009-01-16 09:06:16] nimrodm

I would suggest studying some Graph Algorithms (shortest path, etc.) and Dynamic Programming Algorithms (closley related).

These are the type of algorithms you usually have to adapt to the specific case (optimization/search problems usually) rather than just call a library function.

There are many problems that are more easily solved if approached using graph theory.

21
[+2] [2009-02-04 08:18:20] Simon

While knowing algorithms is helpful it might also be helpful to have a surf around for the kinds of questions people ask in interviews. This way you can know what an employer will ask and, more importantly, the knowledge they want to see in you. Here are some i found from a quick search.

http://blogs.microsoft.co.il/blogs/sasha/archive/2008/04/02/tales-from-an-interview.aspx http://ayende.com/Blog/archive/2007/08/22/Interviewing-developers.aspx [1] http://www.codinghorror.com/blog/archives/000781.html Note the mention of the Fizz Buzz algorithm. I know of several people who have been asked that in an interview.

And of course a couple of SO answers

Regards

Simon

[1] http://www.codinghorror.com/blog/archives/000781.html

22
[+2] [2009-08-08 17:09:13] Tom Hubbard

Working through the various compression algorithms (deflate, LZW, BZip2, huffman, etc.) will force the learning of most of the standard algorithms.

23
[+2] [2011-01-15 09:04:42] Ankit

Some of the good questions can also be found at http://coders-stop.blogspot.com

24
[+1] [2009-08-08 18:12:34] 280Z28

Work through Project Euler, completing as far as you can. Create your own primality tests, factoring algorithms, etc. with the help of Google/Wiki/Mathworld/Library for the math but coded yourself. The farther you get, the better you'll be. I'd take someone great at analyzing algorithm complexity over someone well-versed in all sorts of specific algorithms, but if you made it even 1/3 of the way through the PE problem set on your own you could walk into most positions - at least the interesting ones where the hunters recognize the difficulty of what you accomplished.

Edit: If you google something for a problem there, and you see it says "Project Euler" on the search results, just skip that link. Cheating won't get you anywhere - you aren't graded, and it's primarily for teaching yourself to seek and solve new, challenging problems.

25
[+1] [2009-08-08 18:22:07] Ray

Among others also State Machine.

26
[+1] [2009-09-26 14:49:07] BnWasteland

I'm awed by the .NET framework. Not being a fanboy... python & ruby are very impressive as well. The thing is, since I started working with .NET, I've never reached for a programming construct that wasn't there. These algortithms are solved problems, and codified and formalized, and handed to you on a silver platter. Enjoy them.

What this all boils down to is that every software endeavor has some essential complexity (essential to the problem at hand), and a set non-essential problems (technical implementation details). Over time, tooling will reduce the non-essential complexity that we have to deal with. Ask any .NET developer who ever wrote against the standard c library.

Software doesn't exist for software's sake outside of universities, and so as professional software developers, we should spend most of our time worrying about the essential problems our software is trying to solve: should we be looking at objects with these criteria, or those criteria, not the non-essential software oriented problems of how do we find objects according to given criteria.

Now that said, a wood carver needs a wide array of knives and chisels. He needs to know how and when to apply each one... TO ACHIEVE A DESIRED EFFECT, but I'm not going to hire a woodcarver just because he has a big toolbox.

(3) Regarding your comment "I've never reached for a programming construct that wasn't there" -- every once in a while you need to whip up your own or fall back on a third-party library. For example: 1) Generic heaps, graphs, and rope data structures are notable omissions. 2) There are no immutable implementations of Stack, Queue, Dictionary, and Set. 3) .NET uses quick-sort as the underlying algorithm for its sorting methods, but you need to roll your own code whenever you need to use the faster radix sort or a least a stable-sorting algorithm. 4) No tagged unions. - Juliet
I don't believe in all of this "essential complexity" stuff. Doesn't it seem that programmers are always claiming that their tools have taken out all of the "non-essential complexity" of programming tasks until someone comes out with better tools? C was once seen as getting rid of non-essential complexity. It manages registers for you! - Gravity
27
[+1] [2011-02-15 05:15:47] J.F. Sebastian
[1] http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare

28
[0] [2009-01-15 03:55:59] Roger Nelson

How about a function to recursively search a directory structure for a file. Extra points:

• If it can search with wild card characters.
• If it can search with regular expression.
• If it implemented as iterator design pattern.
• If it implemented as visitor design pattern.
• If it works with with multiple OS (I.e. Windows and UNIX).

I wouldn't expect and applicant to code this completely in an interview situation (I.e. I wouldn't expect the applicant to know the OS API functions to get directory items, or write a regular expression parser), but at least be able to give a rough pseudo code and explanation of what is involved and/or should be considered.

I was asked to write a trivial function in an interview for MicroSoft years ago, I was a little put off. I don't write code, I think about it and then I compose it, and I never compose code with somebody sitting there waiting for me to do something in a matter of minutes and certainly not with the foreign medium of pen and paper :-)

So, I would not ask an applicant to write code at the interview.

I would rather know what kinds of things interest him/her. What has he/she programmed at previous employment, school projects, or as hobby and what they learned from it.

I would ask an applicant to bring samples of code they've done (sources and executables, or perhaps assign the above problem before-hand)
and explain it to you, describe the techniques that were used, and how it could be enhanced. This way you can see if there is a good understanding of techniques, coding style and communication skills (extra points if (s)he happens to bring documentation/manual :-).

I would like to give them the opportunity to demonstrate their problem solving skill and their passion for programming.

29
[0] [2009-01-15 05:10:19] pngaz

The circular/ring buffer for simple producer-consumer multi-threading. The Google-query (( circular ring buffer C++ )) fetches many hits, but once you get the idea of the in-and-out subscripts you just refry this basic concept to fit the particular requirement. For low-level situations it does of course help to use power-of-two sizing so that the & operator can do the modulo-buffersize operations.

30
[0] [2009-01-15 18:31:02] dotnetdev

Good suggestions. Big O notation is something I already know, but also a valid suggestion.

Keep em coming! Great stuff.

BTW, this question is not just to make me a better interviewee but ultimately a better developer, which is my long term goal. This question came up as I applied for a job and I was expected to know the following algorithms (it was a standard .NET developer on the web app side - ASP.NET):

Markov Chain Monte Carlo Stochastic Processes Statistical Analysis Optimisation Algorithms Discrete Mathematics Algebraic Structures Combinatorics

This was a graduate position. I guess the company wanted someone who knew all of this because of the nature of their projects?

Thanks Guys!

31
[0] [2009-01-16 10:01:00] BBetances

The Hodge Conjecture would be a good place to start.

32
[0] [2009-01-16 10:12:40] High Performance Mark

Hmm

I'd specialise on what Drew suggested

-- Binary Search of a good library, on-line or paper

-- Quick Sort of what you find

After 30 years programming, I've forgotten most of the stuff that I ever knew, and place ever greater reliance on being able to find a good algorithm quickly. On the plus side, I've built up a library of code which tackles most of the basic problems, and many of the not so basic ones, in my domain.

33
[0] [2009-08-08 18:00:45] Larry Watanabe

What algorithms should any developer know? As many as possible!

Given that, you should just learn new algorithms and methods for solving problems in whatever area you are working on at the moment. If you just learn algorithms for the sake of learning algorithms, you won't remember or understand them well. It's always best to combine theory and practical application for the most effective learning.

Besides knowing algorithms -- you should know how to invent new ones! Someone had to come up with the algorithm originally, so it is possible to always come up with an algorithm for a problem (if it is solvable). Maybe one day it will be your algorithms that others are learning to get a job at Google or Yahoo or whatever replaces it.

34