Hot answers tagged

23 votes

When are adjacency lists or matrices the better choice?

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph. In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes. ...
user avatar
  • 9,612
10 votes
Accepted

What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm
user avatar
  • 1,086
10 votes
Accepted

Skip List randomization complexity

According to the hint, the number of elements in the levels beyond the first is expected to be $$ n \cdot (1/2 + 1/4 + \cdots + 1/2^k). $$ Presumably, $k \approx \log n$, though as we will see, this ...
user avatar
9 votes
Accepted

The fastest algorithm for intersection of two sorted lists?

Hwang and Lin's Algorithm (A simple algorithm for merging two disjoint linearly-ordered sets (1972) by F. K. Hwang , S. Lin) is the reference on how to merge (or intersect) ordered lists of unequal ...
user avatar
  • 1,254
8 votes
Accepted

The origin of list data structure

Knuth gives a good overview on the history of lists and linked data structures. From The Art of Computer Programming, Volume I, Section 2.6: Linked memory techniques were really born when A. Newell,...
user avatar
8 votes
Accepted

Sorting a large list of test scores

This is a very easy question, assuming all scores are integers. Here is the simplest algorithm in plain words. We will initiate count, an integer array of 100 ...
user avatar
  • 34.1k
7 votes
Accepted

Finding number not in list with wildcards

Reduce from SAT. Consider a CNF formula $\phi = C_1 \land C_2 \land \ldots \land C_m$ over a set of variables $\{x_i\}_{i=1}^n$. Construct an instance of your problem as follows: For each clause $C_i$...
user avatar
  • 2,190
6 votes
Accepted

Description of lists with functions in LISP

In PL theory, this is known as (a variant of) the Church-encoding of pairs. The idea is the following: assume for the moment you only have a language with primitive booleans (true, false, if-then-...
user avatar
  • 14.2k
6 votes
Accepted

Find out duplicate number between 1 to N numbers

Here is the question: You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once). Find the number which appears twice. ...
user avatar
6 votes
Accepted

Given a RxC grid, how to generate N 2D points randomly such that no 3 points are collinear?

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime. Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose ...
user avatar
  • 111
6 votes
Accepted

How to best maintain a sorted list from a stream of integers?

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree ...
user avatar
  • 141k
5 votes

How can I get O(1) prepend on a random-access list?

A deque with growing arrays provides the operations you need in (amortized) constant time. Reversing a deque is simple, you don't move data around, you just switch the meaning of ...
user avatar
  • 5,910
5 votes
Accepted

Lambda calculus lists construction explanation

There are several ways to define lists in lambda calculus. You can find them here. Your definition doesn't seem to fit exactly in any of those (please, check that). Anyway, I'll try to answer to your ...
user avatar
  • 630
5 votes

What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

Unfortunately I can't just comment but I have to post it as an answer. Anyway, you could try to use a min-heap on your unsorted array, you should be able to get a time complexity of O(n+k*logn).
user avatar
5 votes
Accepted

Time complexity to check if there is an edge between two nodes in an adjacency list

In an adjacency list each vertex $u \in V$ is associated with a list of adjacent vertices. Given a graph $G=(V,E)$, in order to check if the edge $(u,v) \in E$ you need to check whether $v \in \text{...
user avatar
  • 1,615
4 votes

Efficiently finding duplicates in lists of numbers

Use any efficient set data structure, based e.g. on hashtables or balanced search trees. Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will ...
user avatar
  • 70.9k
4 votes
Accepted

Why does linear search have $\frac{n}{2}$ comparisons on average?

It's neither ${(n^2+3n)}/{(2n+2)}$ nor $n/2$. In fact, the question itself doesn't make much sense at all. In order to be able to talk about the average running time of an algorithm, you have to fix a ...
user avatar
  • 4,132
4 votes
Accepted

How to use structural induction to prove law on lists

You'll want a helper lemma to make this endeavor more digestible. Notations for map and subs: I'm going to condense the ...
user avatar
  • 1,107
4 votes
Accepted

Fastest way to search a word in a word list?

Trie might help, it stores your "word list" like this: ...
user avatar
  • 888
3 votes

The fastest algorithm for intersection of two sorted lists?

Essentially the same algorithm as you'd use to merge the two lists. In the general case, you can't possibly do better than looking at essentially every element of both lists because, if you don't ...
user avatar
3 votes
Accepted

Find the duplicates in a list of floating point numbers

Sorting The simplest algorithm is to sort your floats, then compare adjacent entries. This will let you find all pairs that are $\le \frac1N$ apart in $O(N \lg N)$ time. Hashing It's also possible ...
user avatar
  • 141k
3 votes
Accepted

Order-preserving update of a sublist of a list of mutable objects in sublinear time

At the time of writing I was not absolutely sure what the problem was. This lead to a more general second answer. See details in discussion at the end of this answer. Apparently, the "idea that does ...
user avatar
  • 19.1k
3 votes
Accepted

Join large list of pairs

You can use a two pass approach: In the first pass, identify all the different strings appearing in your input. (This can be done in various ways, e.g. hashing, trie, BST) For the second pass ...
user avatar
  • 6,519
3 votes

counting arithmetic progressions $a, a+r, a+2r$ in a list

Given that the OP is rather unprecise as to the kind of numbers he is considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to ...
user avatar
  • 19.1k
3 votes

What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

The Quickselect algorithm can do that in O(n) average complexity, it is one of the most often used selection algorithm according to Wikipedia. It is derived from QuickSort and as such suffers from a ...
user avatar
3 votes

Gauss-Jordan using stacks and list

What you want is called indirection. Instead of physically moving the rows/columns, you move their names. Let's say I call row 1 r[0], and row 3 ...
user avatar
  • 12.3k
3 votes

When are adjacency lists or matrices the better choice?

Consider a graph with $N$ nodes and $E$ edges. Ignoring low-order terms, a bit matrix for a graph uses $N^2$ bits no matter how many edges there are. How many bits do you actually need, though? ...
user avatar
  • 18.9k
3 votes
Accepted

Is there a name for the "tree" aproach to listing things?

Your technique is known as exhaustive search (with some pruning). It consists of trying all possibilities. In many cases, the way to implement exhaustive search is using a search tree. There are ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible