15 votes

Why are Red-Black trees so popular?

I've been researching this topic recently as well, so here are my findings, but keep in mind that I am not an expert in data structures! There are some cases where you can't use B-trees at all. One ...
matklad's user avatar
  • 151
8 votes
Accepted

Best data structure for a queue with random reads?

Take any dictionary data structure and link its entries in whichever order suits you. In essence, you retain the $\Theta$-costs from the basic structure. In search trees, this is called threading. It ...
Raphael's user avatar
  • 72.3k
6 votes

Why are Red-Black trees so popular?

Well, this is not an authoritative answer, but whenever I have to code a balanced binary search tree, it's a red-black tree. There are a few reasons for this: 1) Average insertion cost is constant ...
Matt Timmermans's user avatar
6 votes

Fastest static associative map

Here's a way to think about the feature-based approach: you select a set of candidate features, then look for the smallest decision tree that assigns each of the $N$ keys a different index in $[0,N)$ ...
D.W.'s user avatar
  • 158k
5 votes

Memoization without array

There are probably better examples, but here is one, off the top of my head: Let's say you want to check whether the edit distance between two strings $S,T$ is $\le d$, and if it is, compute the edit ...
D.W.'s user avatar
  • 158k
4 votes

What is the advantage of seperate chaining over open addressing?

In addition to what everyone else has said, you can get some of the locality back in a separate chaining scenario by unrolling the linked list. Assuming a C-esque language, separate chaining might ...
Pseudonym's user avatar
  • 22k
4 votes

How are hash tables O(1) taking into account hashing speed?

The tale that hash tables are amortized $\Theta(1)$ is a lie an oversimplification. This is only true if: - The amount of data to hash per item is trivial compared to the number of Keys and the ...
Johan's user avatar
  • 1,060
3 votes
Accepted

Dictionary with sets as keys where lookup can be set intersection

Unfortunately, no, this isn't achievable (at least not if you want to handle arbitrary sets as keys). The reason is simple: if $N$ denotes the number of elements in a key set, then it takes $O(N)$ ...
D.W.'s user avatar
  • 158k
3 votes

time efficient key value store for fast lookup

Make a table with 2^22 entries to lookup the highest 22 bits of the key. Each entry is responsible for one value on average (but may contain up to 1024). Entry #i in the table, which is responsible ...
gnasher729's user avatar
  • 29.4k
3 votes

Algorithms to correct misspelled word?

Standard OCR software already incorporates this idea: it has a corpus of words, along with their frequency of occurrence, and uses this to correct errors. How does it work? OCR doesn't just output ...
D.W.'s user avatar
  • 158k
3 votes

time efficient key value store for fast lookup

Since the data structure is only created once, you can simply use an array ordered by the key. Each element in the array contains the key-value pair. Sorting the array is ...
BMiner's user avatar
  • 271
3 votes
Accepted

Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $

AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than log(n). Not quite. In ...
Raphael's user avatar
  • 72.3k
3 votes

Memoization without array

I would like to provide 2 examples. 0-1 Knapsack problem In case of the 0-1 Knapsack problem (where W is a capacity of the knapsack and N is an amount of items), sometimes it is better to use the top-...
stemm's user avatar
  • 131
3 votes

How are hash tables O(1) taking into account hashing speed?

Let's start with a simpler question. Consider what is perhaps the simplest data structure in existence, an array. For concreteness, let us imagine an array of integers. How much time does the ...
Yuval Filmus's user avatar
3 votes

Deleting in Bloom Filters

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when ...
Kent Munthe Caspersen's user avatar
2 votes

Data structure choice for a query-update-delete problem

Store your data structure in a red-black tree where the first component of a key (i.e. p in (p,q)) is the key and the values are red-black trees of the second parts of keys with identical first part. ...
jbapple's user avatar
  • 3,340
2 votes

Fastest static associative map

A practical answer to this question is that the fastest lookup is the simplest. Make a flat array of the data items you want to look up, and make sure all your keys are pre-processed (before run time,...
Alan Wolfe's user avatar
  • 1,348
2 votes

time efficient key value store for fast lookup

The minimum possible size for such any such data structure is $\log_2{ 2^{32} \choose 4\times 10^6} \approx 4.6\times10^7$ bits, or around 5.5MB. An array of 4 million 32-bit numbers is only 15.25MB. ...
Pseudonym's user avatar
  • 22k
2 votes

Dictionary with sets as keys where lookup can be set intersection

My understanding: You might have three values in the table with keys (a, b), (a, c), (b, c). When you lookup (d, e, c) you want the values for the keys (a, c) and (b, c) containing a ā€œcā€. First you ...
gnasher729's user avatar
  • 29.4k
1 vote

How does the Go language implements maps?

The Go language implements MAPS as hash tables using 8 buckets https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics The bucket represents 3 bits mask of ...
ShAr's user avatar
  • 138
1 vote

LZW with dictionary clearing

When the compressor clears the dictionary, it emits the clear code. This enables the decompressor to stay in sync: when it sees the clear code, the decompressor clears its own dictionary. In this ...
D.W.'s user avatar
  • 158k
1 vote

Parallel Algorithm for Data Averaging

The role of three values $V_1, V_2$ and $V_3$ isn't clear for me, but anyway: Step 1. Sort the original list in parallel by key $K$ - you'll get a list of records $(K, V_1, V_2, V_2)$, where all the ...
HEKTO's user avatar
  • 3,088
1 vote
Accepted

Remove duplicates from dictionary in a safe and clever way

Your question is very well written. Let me make one requirement even clearer. "Remove duplicate values" means that one value can be assigned to at most one key in the end, as explained in the given ...
John L.'s user avatar
  • 38.8k
1 vote

Most space-efficient lossy dictionary?

Let's see what we can do. Values are random and hence are incompressible, but keys can be sorted and then diffed. So, just sort the data, employ difference compression schema for keys and use binary ...
Bulat's user avatar
  • 1,853
1 vote

Determining possible data structures given a set of required operations

If there is no restriction on execution time or $n$ stays small then a simple unsorted array is always an option. It gives $O(n)$ execution time for all operations except adding an object and removing ...
ratchet freak's user avatar
1 vote

Match dictionary to misspelled word, corner cases

Are we talking about a dictionary containing words of some language? Then there are many, many tricks you can use. Your dictionary may contain 500,000 words, but people don't use that many. And they ...
gnasher729's user avatar
  • 29.4k
1 vote
Accepted

Complexity of testing membership in a disjoint set

There's an easy way to find the node that contains a given value. You have two data structures: a union-find data structure (that keeps track of which nodes are in the same equivalence class), and a ...
D.W.'s user avatar
  • 158k
1 vote

Data structure choice for a query-update-delete problem

Use treaps. They store pairs of values and are heap-ordered w.r.t. one, and BST-ordered w.r.t. the other component. They have expected logarithmic height if the $p$'s are uniformly distributed. ...
Raphael's user avatar
  • 72.3k
1 vote

Which in-memory data structure can accommodate billions of md5 value?

Maybe you can use a binary trie (critbit tree?) that splits in two on each node instead of 256? Of course you get many more nodes, but they are a LOT smaller. An example implementation in Java is here:...
TilmannZ's user avatar
  • 764

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