Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

Filter by
Sorted by
Tagged with
71
votes
4answers
25k views

(When) is hash table lookup O(1)?

It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...
19
votes
1answer
2k views

What classes of data structures can be made persistent?

Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. ...
25
votes
2answers
3k views

Efficient map data structure supporting approximate lookup

I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
92
votes
5answers
9k views

What are the reasons to learn different algorithms / data structures serving the same purpose?

I have been wondering about this question since I was an undergraduate student. It is a general question but I will elaborate with examples below. I have seen a lot of algorithms - for example, for ...
41
votes
2answers
8k views

Efficient data structures for building a fast spell checker

I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to ...
30
votes
2answers
7k views

Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes. Of course, when we talk about red-black trees*(see ...
25
votes
2answers
5k views

Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time? GetElement(k): Return the $k$th element of the list. InsertAfter(x,y): Insert ...
24
votes
3answers
11k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
22
votes
1answer
4k views

AVL trees are not weight-balanced?

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees. This question is to ask the same question, but for AVL trees. The question is, ...
18
votes
5answers
2k views

For what kind of data are hash table operations O(1)?

From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there ...
46
votes
9answers
11k views

Does there exist a priority queue with $O(1)$ extracts?

There are a great many data structures that implement the priority-queue interface: Insert: insert an element into the structure Get-Min: return the smallest element in the structure Extract-Min: ...
0
votes
1answer
3k views

Number of Different AVL Tree

I studying the related question. https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node but it's not so general. In-fact, We want to know ...
14
votes
2answers
5k views

Proving a binary tree has at most $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary tree with $n$ nodes has at most $\left\lceil \frac{n}{2} \right\rceil$ leaves. How would I go about doing this with induction? For people who were following in the ...
2
votes
4answers
2k views

minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ? $M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) ...
9
votes
2answers
1k 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 ...
4
votes
2answers
3k views

How to query and update ranges of arrays?

I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array. Decrease elements in range $[L,R]$ by $X$. Count the number of negative elements in range $[L,R]$. ...
58
votes
4answers
46k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
11
votes
3answers
2k views

Algorithm books on a range of topics

I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. ...
11
votes
2answers
2k views

Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms ...
9
votes
1answer
1k views

What is the most efficient algorithm and data structure for maintaining connected component information on a dynamic graph?

Say I have an undirected finite sparse graph, and need to be able to run the following queries efficiently: $IsConnected(N_1, N_2)$ - returns $T$ if there is a path between $N_1$ and $N_2$, otherwise ...
5
votes
1answer
1k views

How to compute amoritized cost for a dynamic array?

I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method. Let A of size m be an array of n elements. When $n = m$, then we create a new ...
3
votes
1answer
2k views

Find k maximum numbers from a heap of size n in O(klog(k)) time

I have a binary heap with $n$ elements. I want to get the $k$ largest elements in this heap, in $O(k \log k)$ time. How do I do it? (Calling deletemax $k$ times yields a $O(k \log n)$ complexity. ...
31
votes
2answers
19k views

What is the difference between radix trees and Patricia tries?

I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a ...
10
votes
1answer
14k views

Proof that a randomly built binary search tree has logarithmic height

How do you prove that the expected height of a randomly built binary search tree with $n$ nodes is $O(\log n)$? There is a proof in CLRS Introduction to Algorithms (chapter 12.4), but I don't ...
16
votes
3answers
36k views

Increase-key and decrease-key in a binary min-heap

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
10
votes
3answers
9k views

Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$

Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
9
votes
3answers
43k views

Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

In my Java class, we are learning about complexity of different types of collections. Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
9
votes
1answer
5k views

Range update + range query with binary indexed trees

I am trying to understand how binary indexed trees (fenwick trees) can be modified to handle both range queries and range updates. I found the following sources: http://kartikkukreja.wordpress.com/...
28
votes
1answer
1k views

Is there a 'string stack' data structure that supports these string operations?

I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
14
votes
2answers
4k views

Representing Negative and Complex Numbers Using Lambda Calculus

Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?
11
votes
2answers
2k views

Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration

I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations. Clojure provides persistent Vector,...
13
votes
1answer
2k views

Is there a data-structure for semilattices similar to a tree data-structure?

If we regard a tree as a partial ordered set, it becomes a special case of a join-semilattice. For a join-semilattice, we want to be able to compute the (unique) least upper bound of two elements (...
3
votes
1answer
253 views

state of the art of subset, set containment and partial match queries

The subset query problem is defined as: Given a list D of size N where the entries are subsets of a universe with ...
15
votes
3answers
1k views

How to approach Dynamic graph related problems

I asked this question at generic stackoverflow and I was directed here. It will be great if some one can explain how to approach partial or fully dynamic graph problems in general. For example: ...
9
votes
1answer
7k views

How do I construct a doubly connected edge list given a set of line segments?

For a given planar graph $G(V,E)$ embedded in the plane, defined by a set of line segments $E= \left \{ e_1,...,e_m \right \} $, each segment $e_i$ is represented by its endpoints $\left \{ L_i,R_i \...
7
votes
1answer
2k views

What are the main ideas used in a Fenwick tree? [duplicate]

While I was solving a programming competition question, I came across a technique advertised as suitable for the solution. A so called Fenwick tree (a.k.a binary indexed tree) was at the heart of this ...
6
votes
4answers
2k views

Algorithm Request: “Shortest non-existing substring over given alphabet”

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
5
votes
4answers
13k views

Which data structure to use for accessing min/max in constant-time?

I need a data structure which can include millions of elements, minimum and maximum must be accesable in constant time and inserting and erasing element time complexity must be better than linear.
4
votes
2answers
283 views

Is there any data structure that can't be represented or described inside a computer?

We all know that, at least theoretically, there are several possible models of computation, varying in structure. Strictly speaking, there are several (not just one) models of computation that exist ...
3
votes
2answers
484 views

Why can't we use a hash tables for collision resolving in hash tables?

To prevent collisions, hash tables with open addressing use a methodology to chain the contents. Why can't we use another hash table allocated to each slot of the primary hash table?
8
votes
2answers
4k views

A median of an AVL. How to take advantage of the AVL?

Here is the source of my question. Given a self-balancing tree (AVL), code a method that returns the median. (Median: the numerical value separating the higher half of a data sample from ...
6
votes
1answer
530 views

Data structure for a static set of sets

I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, \ldots\}...
5
votes
1answer
775 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 ...
4
votes
2answers
3k views

k-ordered array problem

An array $A[1...n]$ is said to be k-ordered if $$A[i - k] \leq A[i] \leq A[i + k]$$ for all $i$ such that $k < i \leq n - k$. For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ ...
3
votes
4answers
3k views

How are binary trees represented on disk

Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen. But what ...
3
votes
1answer
319 views

Delete a consecutive range of leaves from a binary tree

Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values). I want to delete a consecutive interval of ...
6
votes
2answers
706 views

What is the connection between data structures and data types?

I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have ...
5
votes
3answers
1k views

Finding the $k$th largest element in an evolving query data structure

Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element ...
5
votes
1answer
314 views

Data structure for selection of K elements and taking sum

The problem: We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times: We can select exactly $Z$ ...
4
votes
1answer
337 views

Hash-Table in Practice

I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n }{d}$, where $k$ is the number ...