# Questions tagged [data-structures]

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

361 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
152 views

### Measuring how “balanced” a binary tree is

I have some binary trees, and I'm looking for a metric to quantify how "balanced" a tree is. I don't have a rigorous definition for "balanceness", but my intuition suggests it's a measure of how close ...
23 views

### How to chose the condition for expand in hash-table?

How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the ...
412 views

### Graph data structures - Why is topological sorting so efficient?

Topological sorting on a graph seems like an immensely powerful operation: No matter whether the algorithm ends in success or failure, we obtain an important information about the topology of the ...
16 views

### Counting Number of Points Satisfying given Equation

I am given set of points S. I need to find the count of four vertices (A, B, C, D) satsfying the equation AB + CD = BC + AD, morever, the vertices should be pairwise distinct. Here, A, B, C, D ...
71 views

### Minimum changes to be made to get Max-flow between each pair of vertices in an undirected graph

I was asked the following problem in an interview: Let M be a N X N matrix, such that: ...
91 views

### What is the representation of a tree in a heap called?

Often a binary tree is represented in a particular implicit data structure packed into an array whereby the left and right children of t[x] are found at ...
337 views

### Online algorithm to find shortest subarray containing all k-elements

We have given array of $n$ integers in the range $[1, k]$. We want to design algorithm that can modify the array and also find the length of the shortest subarray containing at least one of each ...
80 views

### Generate an AST from an indefinite grammar and logic

As said in the title, I have to generate an AST from a grammar and logic (or a"syntax" if you prefer). This grammar and syntax are both indefinite in the program, meaning that it is the user (a ...
193 views

### Proof of Fenwick Tree's correctness

Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure ...
246 views

### Linear probing number of probe sequences

According to Cormen book,number of probe sequences possible in linear probing if hash function is given as $h(k,i) =( h' (k) + i)$ $\text % m$ is m if h'(k) = k modulo 5 and m = 10, then how can ...
71 views

### How to select cuckoo filter parameters?

If I want a cuckoo filter to hold a dataset with N entries with a target false positive rate of ϵ, how do I select the sizes for the table, bucket, and fingerprint parameters?
100 views

### why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states Let H be class of hash ...
8k views

### Order of a leaf node in B+ Tree

Going with the definition, that order of a B+ tree is the maximum number of children a node can have. What is exactly meant by the order of a leaf node? As per my understanding order of a leaf node ...
349 views

### I'm looking for best algorithms to compare two Circular Linked List?

I'm looking for best algorithms to compare two Circular Linked List? For example : List 1 = 1-3-5 List 2 = 3-5-1 I want to compare "same" or "not same" but need fast algorithm.
61 views

### How to assign the increasing keys to the nodes of a complete binary tree on n nodes in inorder?

I'm looking at the Multiplicative Binary Search and come across this. It's the preparation you need to do for you to use the Multiplicative binary search procedure. I somehow do not know how to do ...
24 views

### Accounting value of Splay trees?

In Splay trees, by definition - the required element x - rises to the root of the tree, using the operations: zig, zig-zig, zig-zag. And the formula zig of the step is this: ...
9 views

### Is there a special name for a queue that works with groups of elements

I have a data type that accepts and returns byte arrays. However, the input is from a network callback or loading a huge file in piecemeal and the output is CRLF-terminated lines. The internal storage ...
43 views

334 views

### Is the ratio between a bloom filter intersection and a bloom filter union equal to that of their original sets?

Given two sets, S1 and S2, and their corresponding bloom filters, BF1 and BF2, is there a way to prove that |BF1 ∩ BF2|/|BF1 ∪ BF2| = |S1 ∩ S2|/|S1 ∪ S2| (we can assume both bloom filters are ...
547 views

### Using rotate to balance a red-black tree?

You have a Black-Red Tree of height h that has two childs: Left child is a full binary tree of height h-1 Right child ...
40 views

### Naming for (memory near optimal) datastructres

Assume that we wish to solve some problem that has a information theoretic memory lower bound of $\mathcal B$ bits. In computer science, there are a few classes for data structures which are close to ...
36 views

### How to store topic-to-topic relationships efficiently and accurately with two huge tables?

I am scanning Wikipedia's DB and retrieving topics (page names, mostly) and their relationships. I want to use it later to create a visual map. A topic table stores the id and the label of each topic....
535 views

### Complexity of set oprations in algorithm

I am designing a graph algorithm. Some steps of the algorithm, are set operations (union, difference, intersection, set-membership). Can I assume them as $~ \mathcal{O}(1)$ operations? Have someone ...
289 views

### Trie end-of-word node

I read about TRIE data-structure and is slightly confused about detecting end-of-word. Why do we create another node to detect end-of-word? why cant same node be used it. For example, we have to ...
83 views

### Improvement on djikstra's algorithm for shortest paths

We all know about the djikstra's algorithm for computing single source shortest path and the complexity for the same as O(m log n) ( m being the number of edges and n the number of vertices ), this ...
37 views

166 views

### What data structure is best suited for nested values and count of values?

I have incoming stream of data which has following values. Country, City, State Along with maximum number of unique values to store (e.g. 50,22,12). I need to design a system which will keep count of ...
270 views

### Binary Indexed Tree(Fenwick Tree) - Range update and point Query

With the help of TopCoder Tutorial and this post, I was able to understand the basic idea of how basic the cumulative frequency sum is stored in the left subtree of a BIT node.I was successfully able ...
2k views

### Merging two binary heaps in linear time

Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time. I've been having some difficulty in solving ...
190 views

### why are integers considered as an ADT?

According to the definition of ADT on wikipedia , it is given that ADT is a mathematical model for data types , And as per wikipedia, definition of mathematical model says that it is composed of ...
93 views

### Respresting data when I have to move back and forth

I am having data where I would be given customers and there priorities. The priority would be food type and there flavours. In total there are N food type and 2 flavour (spicy and non spicy) so in ...
47 views

### Data structure to store a large power-law graph with constantly updated structure

I am looking for data structures to store power-law (hence mostly sparse, but few dense too) graphs whose structure is continuously being modified, including new vertices being added and edge weights ...