Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [data-structures]

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

0
votes
2answers
15 views

Augmenting a tree such that we preserve the insertion operation optimal runtime

Suppose we are given a red-black tree with $n$ vertices with distinct keys and we want to store, as addition information in each vertex $v$, the biggest key out of the keys that are smaller than $v$ (...
-1
votes
0answers
19 views

How to re-color a red-black tree with a specific property

Let us consider a red-black tree in which for every path from the root to a leaf of minimal depth, there is exactly one red-colored vertex in it. How should we re-color the tree so that, after the re-...
-1
votes
1answer
29 views

Mergable heap with no key knowledge cannot EXTRACT-MIN in $o(\log n)$ amortized time

We are looking into Fibonacci heaps in class at the moment, but I am stuck with this problem. Let $H$ be a mergable heap structure, by which is meant a data structure, where each element has a key, ...
0
votes
1answer
30 views

Using Union find to check whether there is a cycle in a graph

I'm trying to learn about DSU, and I came across a point stating if two vertices belong to the same sub-set, then a cycle exists. In terms of implementation of DSU, I'm unable to make sense of this. ...
1
vote
2answers
68 views

Efficient data structure for storing integers in a range?

Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ ...
1
vote
2answers
67 views

What does $O(\alpha(n))$ amortized time mean?

DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect. from a set of consectutive integers like $S = \{1,2,3,5,6\}$ Provide a data structure and an algorithm for ...
0
votes
0answers
11 views

Store multiple table in a single linked list [closed]

Design a data structure that stores number of rows and columns in a given table.It stores meta information of table.We can have multiple table and they must store in single linked list.Information of ...
0
votes
1answer
29 views

Number of possible min heaps

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is -------------- According to me, the answer should be 48. The first element 1 is fixed as root. The ...
0
votes
1answer
40 views

Short Fibonacci Heap

Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then ...
2
votes
1answer
34 views

How to generate random adjacency matrix with given number of components in graph

I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph. For example, if I wanted to generate a graph of 50 ...
3
votes
1answer
34 views

Fenwick Tree/ Binary Index Tree Interval location

I have an array of positive numbers, and when calculating the cumulative sum of this array, want to know which interval a given point will lie in. I have done this by searching linearly through an ...
1
vote
2answers
50 views

Build a balanced binary tree from list in linear time

I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in ...
2
votes
1answer
25 views

Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes

I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{...
0
votes
0answers
23 views

Find no of acyclic paths of any length in a directed graph from a single source given that every node has at most 4 in/out degree

let A,B,C be nodes of directed graph with edges A->B,B->A,A->C,C->A,B->C,C->B then no of paths will be 5 that is A,A->B,A->C,A->B->C,A->C->B If i apply dfs and increase counter for every node i ...
2
votes
2answers
53 views

An algorithm to efficiently insert a list of elements into a binary heap (at once)

I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a ...
0
votes
0answers
20 views

Two-dimensional Range Minimum Query under a constraint

So, I have trouble understanding and solving the following question: You are given a 2D array. Design an algorithm that, given two coordinates (each with two indexes ofc), returns the minimum in the ...
0
votes
0answers
13 views

What would be the line by line analaysis and construction function T[n] with Big Oh notation? [duplicate]

What would be the line by line analaysis and construction function T[n] with Big Oh notation? Thanks a lot.
1
vote
2answers
55 views

Algorithm/data structure to quickly check if an integer is a member of any [lower, upper] interval

Are there any existing algorithms/strategies to test if an integer value is within the bounds of any of a list of intervals, where each interval is denoted by a [min, max] pair? The naive approach is ...
0
votes
0answers
61 views

How many maximum height AVL trees given height?

I am having some trouble finding a recursive formula for finding the number of maximum height AVL trees of height h. Height 0 has 1, height 1 has 2, height 2 has 4, height 3 has 8, etc. is that ...
2
votes
1answer
65 views

What is an efficient data structure for prefix matching?

I'm looking for an data structure that supports efficient random prefix matching queries (pattern) over a previously known set of words (dictionary). The dictionary is expected to contain about 10,000 ...
1
vote
1answer
12 views

Simple algorithm to generate a linear extension from partial order set

I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.
2
votes
1answer
24 views

Using bit arrays to solve crossword puzzles

I have read this paper and currently I am trying to implement this variation of crossword solving algorithm. First of all I come up with lexicon and seriously I cannot understand the data structure ...
1
vote
1answer
39 views

An algorithm to drop low-priority items from a heap-based priority queue

I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap ...
0
votes
0answers
28 views

Storing binary tree with arbitrarily sized nodes without linked-list or large 32-bit pointers

So you can store a binary tree without pointers using a 1-D array: Binary Trees can be represented using 1-D array in memory(Fig 1).The rule to store binary tree in array are : The values of ...
1
vote
1answer
31 views

heap pop creates unbalanced tree?

say you have a min-heap. Popping removes the root and replaces it with the value of one of the leaves and then heapifies. couldnt this last heapify result in an unbalanced tree? is there something ...
0
votes
0answers
38 views

Minimum number queries on matrix

As part of a solution to an earlier question, I am interested in the following problem. I have a 2-D matrix $M$. I want to preprocess it in linear time so that I can answer queries of the following ...
1
vote
0answers
20 views

Elegant or readable way to store tree by user [closed]

Sorry if my title or question is unclear. I lack the vocabulary to formulate it properly. I've got a classical tree structure with several layers. I have to manage authorization for each user, as not ...
3
votes
1answer
77 views

Replace queries on string

Let's define a replace query on some string $s$. Consider a string $s$ of length $n$ over alphabet $C = \{ c_{0}, c_{1}, c_{2}, \dots, c_{k}\}$. Also consider $l, r \in \{0, 1, 2, \dots, n - 1\}, l \...
1
vote
1answer
30 views

Path of maximum value with bounded cost in DAG

Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is ...
2
votes
2answers
73 views

How do I know which direction I should rotate a node in an AVL Tree?

I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL ...
1
vote
0answers
21 views

Solve a 2D grid which is already connected

You are given a 2d grid where each grid item has a value of 1 or 0, you can only move horizontally or vertically and if both blocks have value of 1. You are also given a starting index, the output ...
1
vote
1answer
120 views

Sorting lower bounds for almost sorted array

Can't find a good way to tackle the problem. Would appreciate any help. $A$ is an $n$ items array from an ordered set, in which every item is at most $\log n $ indices away from its position in the ...
2
votes
1answer
85 views

Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
0
votes
0answers
14 views

Trie or no Trie for 1,000 page document or searchable BigInt dataset

Tries seem to be good at storing and querying small strings, like keys to a dictionary. What I would like to know is if there is anything better for storing large strings such as a 1,000 page ...
1
vote
0answers
20 views

How to find all numbers that there distance from given point are less or equall to integer n? [closed]

Given a set of numbers $D$ and some number $k$ I want to find all numbers that are in $D$ such that the distance between $k$ and any found number is less or equal to integer $n$? Example: suppose we ...
1
vote
0answers
27 views

Probability lower bound on a double cycle on two vertices in random cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
0
votes
1answer
45 views

Dynamic Programming Problem on Tree

Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had ...
2
votes
1answer
136 views

Checking the validity of a pyramid of dominoes

I came across this question in a coding interview and couldn't figure out a good solution. You are given 6 dominoes. A domino has 2 halves each with a number of spots. You are building a 3-level ...
1
vote
1answer
24 views

Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time

When studying about splay trees, I found the following statement: Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. ...
2
votes
2answers
303 views

Is there a name for this priority queue data structure?

While watching a sports tournament, I noticed that the tournament tree looks a lot like a heap. I came up with the following data structure: A complete binary tree where the leaves are elements of ...
3
votes
2answers
132 views

Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

There are two operations as follows: insert(num): insert num into the data structure. find(sum): return a pair(a, b) ...
0
votes
1answer
62 views

My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?

My whole life I thought a collision is a situation that occurs when two distinct pieces of data have the same hash value. Everything looks a little bit different now: A few days ago we had to ...
0
votes
0answers
30 views

Data Structure which maintains spacing for similar elements

I want a queue like data structure in which a new element inserted has to be some elements away from a related element. While reading from this data structure, related elements should only be read ...
2
votes
2answers
40 views

What is the term for two file formats that describe the same amount of information?

I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not ...
0
votes
0answers
32 views

Quick access to top element of subsets of elements

I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a ...
15
votes
2answers
2k views

What is this data structure/concept where a plot of points defines a partition to a space

I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem. Basically it's a plot of points, and the ...
0
votes
0answers
16 views

Adaptive radix tree for storing Hash vs HAMT

Is there any disadvantage to using Adaptive radix tree to store hash of key like it is done in HAMT and Ctrie Would it be slower? Would it use more memory?
0
votes
0answers
22 views

Pseudocode for Userdefined Data Types

In the pseudocode guide for my syllabus, an example of a record data type is given as below: ...
2
votes
0answers
41 views

Probability of a double cycle in cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
0
votes
0answers
17 views

How to sort a woven shuffled stack

Say you have sort of a "woven shuffling situation" going on, sort of like this. Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...