Questions tagged [dictionaries]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
2 answers
37 views

Dictionary with sets as keys where lookup can be set intersection

Normally, when working with dictionaries, we expect around O(1) complexity when we go to retrieve a value given the key (and when we insert). I work in Python, but this might apply to any dynamic ...
user avatar
0 votes
0 answers
22 views

Unusual approach to tabulation algorithm

Consider simple tabulation algorithm firstly for Fibonacci numbers. We will use the dictionary as a cache (and Python as example PL): ...
user avatar
  • 101
1 vote
1 answer
84 views

How does the Go language implements maps?

To what extent is the MAP data type implementation language dependant??? If we know that C++ implements maps as Red Black Trees, unordered maps as hash tables, How C++ and alike maps are actually ...
user avatar
  • 140
0 votes
0 answers
55 views

The Most efficient algorithm for a program that returns true if the two strings only differ by one character

We have a list of strings with the same length. Each string only contains a, b and c.(For instance : aabcc) The program gets a string and returns true if the two strings(input and the list of strings) ...
user avatar
1 vote
1 answer
150 views

LZW with dictionary clearing

How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used ...
user avatar
  • 11
1 vote
0 answers
61 views

Why is sparsity useful in dictionary learning?

What is the particular reason for which we use sparse matrix X in dictionary learning equation Y=DX where Y is the signal matrix, D is dictionary and X is the coefficient matrix?
user avatar
  • 123
1 vote
0 answers
20 views

If statement not capturing the conditional I'm seeking [closed]

I'm working on a hw assignment, and my if statement isn't working the way it's intended. This is an ATM machine project. I've already gotten the program to read the csv file and stored it into a ...
user avatar
0 votes
1 answer
314 views

Parallel Algorithm for Data Averaging

I am trying to write an efficient Parallelised algorithm for Data Averaging. By this I mean I have a list of tuples (K, V1, V2, V3) and in the end, I want a dictionary mapping K to the average of all ...
user avatar
2 votes
1 answer
726 views

Remove duplicates from dictionary in a safe and clever way

I have a dictionary that has keys and multiple values per key. Same value can be assigned to multiple keys. For the sake of simplicity, the keys are ints and the ...
user avatar
  • 123
7 votes
1 answer
249 views

Most space-efficient lossy dictionary?

Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)? Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
user avatar
  • 391
1 vote
1 answer
73 views

Determining possible data structures given a set of required operations

This was an interview question that I was told is supposed to be an open ended discussion of the trade-offs. You have a collection of comparable objects and want to be able to do the following: 1. ...
user avatar
  • 111
0 votes
0 answers
57 views

Dictionary matching problem: dictionary size estimation

Suppose we solve dictionary matching problem for $d$ patterns with the Aho-Corasick algorithm. Then our main data structure consists of a trie with $n$ vertices and auxiliary structures. I want to ...
user avatar
3 votes
4 answers
1k views

time efficient key value store for fast lookup

Let's state a collection of key/values. Key is an unsigned integer (0 - 2^32-1). Hense there are comparable. Value is few bytes fixed size. There are 4M items in the collection. Keys are not evenly ...
user avatar
  • 131
2 votes
1 answer
519 views

Algorithms to correct misspelled word?

At present, I am doing a project on Optical Character Recognition (OCR). I am looking forward to improve the results by checking the output words of my OCR code with existing words from a text file. ...
user avatar
  • 309
1 vote
3 answers
516 views

Match dictionary to misspelled word, corner cases

I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word w1, find all matches with the least editing distance from it in the ...
user avatar
14 votes
3 answers
2k views

Memoization without array

In Cormen et al.'s Introduction to algorithms, section 15.3 Elements of dynamic programming explains memoization as follow: A memoized recursive algorithm maintains an entry in a table for the ...
user avatar
  • 311
6 votes
1 answer
623 views

Best data structure for a queue with random reads?

Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads. Imagine an algorithm ...
user avatar
  • 239
0 votes
1 answer
364 views

What happens internally when you remove an object from a treemap

I am wondering what happens if you remove an object in the middle of a treemap. If the treemap would look something like this: So what would happen if you remove the number 30? Because 27 and 34 ...
user avatar
4 votes
2 answers
379 views

Fastest static associative map

Let's say that I wanted to build a key to value associative map where the only requirement was that lookup times were fast. Once built, the associative map would not allow inserts, deletes, or ...
user avatar
  • 1,320
0 votes
1 answer
500 views

Complexity of testing membership in a disjoint set

I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node". I want to look up a node by value. How can I do this? The representations ...
user avatar
  • 113
5 votes
1 answer
1k views

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

Iv'e been struggling a lot with this one. I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which ...
user avatar
3 votes
3 answers
171 views

Data structure choice for a query-update-delete problem

Given is an initial set of n keys. Each key k is of the form (p, q). Note that both p and q are positive. At any given point, there are two possible actions: 1) Query-Delete: Given a value s as ...
user avatar
1 vote
1 answer
229 views

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

For my application, I have to store billions of md5 values, and before storing new md5 I wanna make sure that it doesn't exist already in it. I tried using hash data structure, it worked well but no ...
user avatar
2 votes
2 answers
1k views

O(1) access into an array-like data structure with numerical ranges for keys

Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies... Summary: I have a data structure with probability ranges assigned to the elements, and ...
user avatar
  • 121
1 vote
2 answers
5k views

Data structure with constant time operations

I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value ...
user avatar
2 votes
1 answer
109 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
user avatar
6 votes
3 answers
15k views

What is the advantage of seperate chaining over open addressing?

Hash tables resolve collisions through two mechanisms, separate chaining or open hashing and open addressing or closed hashing. Though the first method uses lists (or other fancier data structure) ...
user avatar
6 votes
1 answer
217 views

Is it possible to implement a dictionary with efficient access according to insertion order?

I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a ...
user avatar
  • 161
1 vote
1 answer
747 views

A many-to-many mapping data structure

What would be a good way representing: i. Given a key, return all the data values associated with that key AND ii. Given a data value, return all the keys that are associated with that data. So far, ...
user avatar
4 votes
1 answer
5k views

Segment trees with insertion/deletion

I have a range query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
user avatar
2 votes
0 answers
107 views

Why can't fractional cascading be used on two unrelated arrays?

According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data. The specific question: A fellow student wants to compactly store ...
user avatar
60 votes
4 answers
18k views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
user avatar
1 vote
1 answer
608 views

Applications of queues [closed]

Let suppose a simple (FIFO) queue, where elements enter at a side and exit at the other side. I know the classical use of queues in everyday life and computer networking. I would like to know more ...
user avatar
  • 435
2 votes
3 answers
47 views

Existence of functions that only tests memberships without revealing any information about the members

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically ...
user avatar
  • 1,676
-2 votes
1 answer
725 views

Find K-th next element in O(log n) time

We want to store a set S of distinct positive integers and support the following operations on S: Insert(a): insert integer a !∈ S into S. Delete(a): delete integer a ∈ S from S. FindNext(a, k), where ...
user avatar
  • 1
0 votes
1 answer
2k views

Selection problem on the union of two ordered dictionaries

Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding the ...
user avatar
  • 9
1 vote
1 answer
594 views

Data structure for range-value-sum

I have to be able to perform insert, delete, range-value-sum, and range-2-max-values with a data structure. Range-value-sum(xl,xr): with a range [xl,xr] (for a range query), it reports the sum of ...
user avatar
  • 101
3 votes
2 answers
1k views

Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency

Here is the description of the data structure I am looking for: Initial Original Data Index | Frequency | 1 3 2 1 3 7 4 2 5 6 Now it should be kept ...
user avatar
3 votes
1 answer
3k views

Are dictionaries and associative arrays the same thing?

With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?
user avatar
  • 167
3 votes
2 answers
521 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
user avatar
8 votes
2 answers
4k views

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

Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity. However, this assumes the lengths of the elements are constant. Computing the hash of an ...
user avatar
  • 357
2 votes
2 answers
2k views

Tree data structure for fast merges [closed]

I need trees that have the following properties: Each node in the tree has two values associated with it - a key and an associated opaque data element. An internal node in the tree has unbounded ...
user avatar
2 votes
1 answer
260 views

Bloom filter variant

I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits ...
user avatar
  • 222
31 votes
5 answers
3k views

Is there an anti-Bloom filter?

A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in ...
user avatar
3 votes
2 answers
522 views

Why should leaf nodes in a red-black tree be black?

From the property of Red-Black Trees we know that: All leaves (NIL) are black. (All leaves are same color as the root.)(Comren et al "Introduction to Algorithms") But what is the reason that we ...
user avatar
2 votes
1 answer
1k views

What is a suitable data structure in this scenario?

I need an efficient data structure for maintaining a set of values. Here, $n_1$ is the number of insertions per unit time; $n_2$ is the number of deletions per unit time; $k$ is the number of searches ...
user avatar
  • 221
9 votes
2 answers
2k views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with operations ...
user avatar
  • 2,977
10 votes
3 answers
5k views

Deleting in Bloom Filters

I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete ...
user avatar
  • 219
3 votes
2 answers
2k views

Data structure for maintaining large space-efficient filtered array

How does one implement a space efficient data structure that satisfies the requirements below? You have a large array You have a filter which tells you which elements in that large array are to be ...
user avatar
  • 155
4 votes
4 answers
504 views

Why do Bloom filters work?

Let's say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a ...
user avatar