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.
1424
votes
16answers
189k 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.
1127
votes
22answers
106k 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 ...
632
votes
25answers
155k 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 ...
453
votes
13answers
31k 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 ...
417
votes
38answers
89k 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 ...
371
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. ...
365
votes
6answers
68k 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 ...
364
votes
52answers
59k 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 ...
358
votes
21answers
109k 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 ...
322
votes
5answers
33k 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 ...
294
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 ...
279
votes
23answers
40k 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 ...
251
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 ...
243
votes
16answers
63k views
What is tail-recursion?
Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean?
240
votes
31answers
130k 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?
