Questions tagged [algorithm]
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.
119,855
questions
5358
votes
43
answers
821k
views
What is a plain English explanation of "Big O" notation?
I'd prefer as little formal definition as possible and simple mathematics.
- 61.6k
4887
votes
62
answers
3.5m
views
How do I check if an array includes a value in JavaScript?
What is the most concise and efficient way to find out if a JavaScript array contains a value?
This is the only way I know to do it:
function contains(a, obj) {
for (var i = 0; i < a.length; i++...
- 74.3k
4180
votes
38
answers
438k
views
How can I 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 ...
- 176k
2707
votes
32
answers
1.6m
views
What does O(log n) mean exactly?
I am 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 ...
- 106k
2063
votes
14
answers
1.0m
views
What is the optimal algorithm for the game 2048?
I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make "bigger" tiles. After each move, a new tile appears at random empty position ...
- 19.6k
2043
votes
29
answers
602k
views
What is tail recursion?
Whilst starting to learn lisp, I've come across the term tail-recursive. What does it mean exactly?
1900
votes
23
answers
239k
views
Image Processing: Algorithm Improvement for 'Coca-Cola Can' Recognition
One of the most interesting projects I've worked on in the past couple of years was a project about image processing. The goal was to develop a system to be able to recognize Coca-Cola 'cans' (note ...
- 41k
1670
votes
22
answers
292k
views
What is the best algorithm for overriding GetHashCode?
In .NET, the GetHashCode method is used in a lot of places throughout the .NET base class libraries. Implementing it properly is especially important to find items quickly in a collection or when ...
- 49k
1444
votes
58
answers
2.1m
views
Removing duplicates in lists
How can I check if a list has any duplicates and return a new list without duplicates?
- 20.2k
1275
votes
49
answers
322k
views
Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
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 100 ...
- 378k
1223
votes
7
answers
205k
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 ...
- 33.9k
1153
votes
49
answers
1.2m
views
Calculate distance between two latitude-longitude points? (Haversine formula)
How do I calculate the distance between two points specified by latitude and longitude?
For clarification, I'd like the distance in kilometers; the points use the WGS84 system and I'd like to ...
- 15.1k
1084
votes
10
answers
284k
views
What is tail call optimization?
Very simply, what is tail-call optimization?
More specifically, what are some small code snippets where it could be applied, and where not, with an explanation of why?
- 13k
1037
votes
10
answers
873k
views
How can I find the time complexity of an algorithm?
I have gone through Google and Stack Overflow search, but nowhere I was able to find a clear and straightforward explanation for how to calculate time complexity.
What do I know already?
Say for code ...
- 47.1k
1008
votes
66
answers
639k
views
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 the algorithms to determine the number of set bits in a 32-bit integer?
976
votes
24
answers
525k
views
Big O, how do you calculate/approximate it?
Most people with a degree in CS will certainly know what Big O stands for.
It helps us to measure how well an algorithm scales.
But I'm curious, how do you calculate or approximate the complexity of ...
- 18.2k
860
votes
19
answers
475k
views
How can building a heap be O(n) time complexity?
Can someone help explain how can building a heap be O(n) complexity?
Inserting an item into a heap is O(log n), and the insert is repeated n/2 times (the remainder are leaves, and can't violate the ...
- 17.6k
839
votes
41
answers
1.1m
views
How do I generate all permutations of a list?
How do I generate all the permutations of a list? For example:
permutations([])
[]
permutations([1])
[1]
permutations([1, 2])
[1, 2]
[2, 1]
permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, ...
- 13.4k
793
votes
6
answers
124k
views
How do I 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 ...
- 6,555
761
votes
36
answers
214k
views
Sorting 1 million 8-decimal-digit numbers with 1 MB of RAM
I have a computer with 1 MB 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 ...
724
votes
38
answers
123k
views
Generate an integer that is not among four billion given ones
I have been given this 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 ...
717
votes
78
answers
224k
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.
716
votes
31
answers
384k
views
How to check if a number is a power of 2
Today I needed a simple algorithm for checking if a number is a power of 2.
The algorithm needs to be:
Simple
Correct for any ulong value.
I came up with this simple algorithm:
private bool ...
- 41k
705
votes
30
answers
321k
views
How do I create a URL shortener? [closed]
I want to create a URL shortener service where you can write a long URL into an input field and the service shortens the URL to "http://www.example.org/abcdef".
Instead of "abcdef" there can be any ...
- 31.1k
656
votes
13
answers
277k
views
What is the difference between a generative and a discriminative algorithm? [closed]
What is the difference between a generative and a
discriminative algorithm?
- 52.3k
654
votes
33
answers
637k
views
How do you compare float and double while accounting for precision loss?
What would be the most efficient way to compare two double or two float values?
Simply doing this is not correct:
bool CompareDoubles1 (double A, double B)
{
return A == B;
}
But something like:
...
- 6,581
642
votes
77
answers
555k
views
Algorithm to return all combinations of k elements from n
I want to write a function that takes an array of letters as an argument and a number of those letters to select.
Say you provide an array of 8 letters and want to select 3 letters from that. Then ...
626
votes
19
answers
725k
views
How to replace all occurrences of a character in string?
What is the effective way to replace all occurrences of a character with another character in std::string?
- 6,892
591
votes
28
answers
556k
views
How do you detect Credit card type based on number?
I'm trying to figure out how to detect the type of credit card based purely on its number. Does anyone know of a definitive, reliable way to find this?
- 7,708
577
votes
13
answers
181k
views
Why does Java's hashCode() in String use 31 as a multiplier?
Per the Java documentation, the hash code for a String object is computed as:
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
using int arithmetic, where s[i] is the
ith character of the string,...
- 8,780
576
votes
12
answers
223k
views
Algorithm to detect overlapping periods [duplicate]
I've to detect if two time periods are overlapping.
Every period has a start date and an end date.
I need to detect if my first time period (A) is overlapping with another one(B/C).
In my case, if ...
- 19.6k
575
votes
5
answers
372k
views
A simple explanation of Naive Bayes Classification [closed]
I am finding it hard to understand the process of Naive Bayes, and I was wondering if someone could explain it with a simple step by step process in English. I understand it takes comparisons by times ...
- 5,887
573
votes
15
answers
139k
views
What is the most efficient/elegant way to parse a flat table into a tree?
Assume you have a flat table that stores an ordered tree hierarchy:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 ...
- 333k
569
votes
53
answers
995k
views
Best way to reverse a string
I've just had to write a string reverse function in C# 2.0 (i.e. LINQ not available) and came up with this:
public string Reverse(string text)
{
char[] cArray = text.ToCharArray();
string ...
- 65.4k
567
votes
18
answers
136k
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 ...
- 31.7k
555
votes
30
answers
607k
views
Check if all elements in a list are identical
I need a function which takes in a list and outputs True if all elements in the input list evaluate as equal to each other using the standard equality operator and False otherwise.
I feel it would be ...
- 49.8k
553
votes
13
answers
223k
views
Why do we check up to the square root of a number to determine if the number is prime?
To test whether a number is prime or not, why do we have to test whether it is divisible only up to the square root of that number?
- 6,475
519
votes
8
answers
125k
views
What is Constant Amortized Time?
What is meant by "Constant Amortized Time" when talking about time complexity of an algorithm?
- 6,137
505
votes
14
answers
317k
views
What is an NP-complete in computer science? [closed]
What is an NP-complete problem? Why is it such an important topic in computer science?
505
votes
5
answers
109k
views
What's the Hi/Lo algorithm?
What's the Hi/Lo algorithm?
I've found this in the NHibernate documentation (it's one method to generate unique keys, section 5.1.4.2), but I haven't found a good explanation of how it works.
I know ...
- 5,053
472
votes
29
answers
215k
views
How to detect a loop in a linked list?
Say you have a linked list structure in Java. It's made up of Nodes:
class Node {
Node next;
// some user data
}
and each Node points to the next node, except for the last Node, which has ...
- 22.2k
469
votes
15
answers
357k
views
What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]
I understand the differences between DFS and BFS, but I'm interested to know what factors to consider when choosing DFS vs BFS.
Things like avoiding DFS for very deep trees, etc.
- 4,779
466
votes
18
answers
101k
views
How does the Google "Did you mean?" Algorithm work? [closed]
I've been developing an internal website for a portfolio management tool. There is a lot of text data, company names etc. I've been really impressed with some search engines ability to very quickly ...
- 13.8k
463
votes
20
answers
385k
views
How to implement a queue using two stacks?
Suppose we have two stacks and no other temporary variable.
Is to possible to "construct" a queue data structure using only the two stacks?
- 15.2k
461
votes
57
answers
691k
views
Generating all permutations of a given string
What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?
- 65.5k
452
votes
14
answers
398k
views
Best algorithm for detecting cycles in a directed graph [closed]
Is there an efficient algorithm for detecting cycles within a directed graph?
I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency ...
- 4,783
445
votes
10
answers
287k
views
What is stability in sorting algorithms and why is it important?
I'm very curious, why stability is or is not important in sorting algorithms?
- 53.4k
445
votes
12
answers
353k
views
Image comparison - fast algorithm
I'm looking to create a base table of images and then compare any new images against that to determine if the new image is an exact (or close) duplicate of the base.
For example: if you want to ...
- 23k
439
votes
13
answers
157k
views
Why do we use Base64?
Wikipedia says
Base64 encoding schemes are commonly used when there is a need to encode binary data that needs be stored and transferred over media that are designed to deal with textual data. This ...
- 91.3k
438
votes
5
answers
365k
views
Difference between Big-O and Little-O Notation
What is the difference between Big-O notation O(n) and Little-O notation o(n)?
- 7,231