An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
1599
votes
16answers
214k views
Plain English explanation of Big O
What is a plain English explanation of Big O? With as little formal definition as possible and simple mathematics.
1150
votes
22answers
107k views
How to pair socks from a pile efficiently?
Yesterday I was pairing the socks from the clean laundry, and figured out the way I was doing it is not very efficient. I was doing a naive search — picking one sock and "iterating" the pile in ...
670
votes
26answers
163k views
How to create a GUID / UUID in Javascript?
I'm trying to create globally-unique identifiers in Javascript. I'm not sure what routines are available on all browsers, how "random" and seeded the built-in random number generator is, etc..
The ...
467
votes
13answers
32k views
Algorithm improvement for Coca-Cola can shape recognition
One of the most interesting projects I've worked in the past couple years as I was still a student, was a final project about image processing. The goal was to develop a system to be able to recognize ...
451
votes
21answers
136k views
What does O(log n) mean exactly?
I am currently learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm ...
425
votes
38answers
90k views
Sorting 1 million 8-digit numbers in 1MB of RAM
I have a computer with 1M of RAM and no other local storage. I must use it to accept 1 million 8-digit decimal numbers over a TCP connection, sort them, and then send the sorted list out over another ...
380
votes
34answers
62k views
Find an integer not among four billion given ones
It is an interview question:
Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB memory. ...
376
votes
6answers
69k views
How to determine whether my calculation of pi is accurate?
I was trying various methods to implement a program that gives the digits of pi sequentially. I tried the Taylor series method, but it proved to converge extremely slowly (when I compared my result ...
372
votes
52answers
61k views
Expand a random range from 1–5 to 1–7
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
What is a simple solution?
What is an effective solution ...
328
votes
6answers
35k views
Ukkonen's suffix tree algorithm in plain English?
I feel a bit thick at this point. I've spent days trying to fully wrap my head around suffix tree construction, but because I don't have a mathematical background, many of the explanations elude me as ...
298
votes
17answers
40k views
What algorithms compute directions from point A to point B on a map?
How do map providers (such as Google or Yahoo! Maps) suggest directions?
I mean, they probably have real-world data in some form, certainly including distances but also perhaps things like driving ...
290
votes
23answers
42k views
Easy interview question got harder: given numbers 1..100, find the missing number(s)
I had an interesting job interview experience a while back. The question started really easy:
Q1: We have a bag containing numbers 1, 2, 3, …, 100. Each number appears exactly once, so there are ...
255
votes
5answers
39k views
Efficiency of purely functional programming
Does anyone know what is the worst possible asymptotic slowdown that can happen when programming purely functionally as opposed to imperatively (i.e. allowing side-effects)?
Clarification from ...
254
votes
16answers
65k views
What is tail-recursion?
Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean?
247
votes
32answers
134k views
How to count the number of set bits in a 32-bit integer?
8 bits representing the number 7 look like this:
00000111
Three bits are set. What are algorithms to determine the number of set bits in a 32-bit integer?
