# Tag Info

### 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. ...
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
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 ...
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 ...
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,...
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 ...
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$...
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-...
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. ...
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 ...
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 ...

### 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 ...
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 ...

### 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).