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 ...
