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
-2
votes
0answers
8 views

Need help on stack related question

Ran into a problem, anyone can help?
1
vote
0answers
23 views

How to map structured grid data onto a regular grid efficiently?

Context: First of all, my data: I am working with 3D data shaped onto a structured grid made of hexahedrons with for each 8 vertices and 12 edges. The data I'm working on is cell data (and not point ...
0
votes
1answer
36 views

What is the difference between python list and c++ vector?

I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
17
votes
8answers
4k views

Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
2
votes
1answer
45 views

Efficiently storing and modifying a reorderable data structure in a database

I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each ...
1
vote
1answer
37 views

Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order ...
2
votes
1answer
46 views

Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
0
votes
1answer
32 views

Augmenting AVL tree to calculate sum of subtree

Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function calculateSum(key), which receives a key of a node and returns the sum ...
1
vote
0answers
54 views

Is there a known way to make an efficient, compact, and fully persistent stack or queue?

In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
0
votes
1answer
14 views

Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time

I wonder what is the best data structure I can use in order to achieve the following: Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ ...
2
votes
1answer
29 views

Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept

Originally posted in Stack Overflow but was told to post here. Context: I am doing a PCA on a $M \times N \, (N \gg M)$ matrix with some invalid values located in the matrix. I cannot infer these ...
0
votes
1answer
10 views

Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
1
vote
0answers
27 views

Set data structure for data too large to fit into memory

I'm trying to solve the following exercise: Given N data items and memory that can hold M/B blocks of size B. Describe a data structure that needs at most N/B blocks of external memory and allows ...
0
votes
1answer
13 views

Binomial trees in binomial heap with 27 elements

How many binomial trees are in a binomial heap with 27 elements and how would you find this number?
0
votes
1answer
30 views

Use tree in-order traversal to determine whether a BST or Heap

Given these in-order traversal lists: 1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19 2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17 I need to determine whether each one of those lists represent a valid BST ...
-3
votes
0answers
29 views

Is the correct way to carry out a quick sort algorithm?

I have a question regarding the quicksort algorithm where the first element is the pivot. I'm still new at this and have been a little confused whether I'm going at this in the right direction. Is ...
2
votes
2answers
45 views

Implementing Queue operations in $\Theta(1)$

We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 ...
1
vote
0answers
31 views

How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
2
votes
2answers
50 views

Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
0
votes
0answers
11 views

What is the insertion algorithm for an AVL tree with balance constraint of 2?

What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
2
votes
1answer
54 views

How to represent sums of piecewise quadratic functions for efficient optimisation?

I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
1
vote
0answers
60 views

Trees with duplicate nodes and path cancellations

I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
0
votes
0answers
26 views

Finding minimal degree for a B-Tree

We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5). We are asked: "What is the minimal t we can choose?" ($t$ is the minimal degree, in ...
2
votes
1answer
74 views

What does Lambda Calculus teach us about data?

In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing? Some context: as a software developer, I ...
2
votes
2answers
84 views

Managing an hotel using AVL trees - Data Structures

I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$ and it can be occupied or not. Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, ...
0
votes
1answer
25 views

Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
0
votes
1answer
22 views

Prove that AVL tree has this kind of property with Fibonacci sequence

Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$) and has a height of $h$ this property is true: $n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence: $F(0) =0, F(1)=...
2
votes
1answer
46 views

Algorithm for splitting an array into k sub-arrays

We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized ...
1
vote
2answers
34 views

Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent. More ...
0
votes
0answers
20 views

Best way to find and store difference between two strings

I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
1
vote
1answer
29 views

Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined. The question is ...
1
vote
1answer
39 views

Finding a closed formula for recurrence relation

I'm trying to find a closed formula for the below recurrence relation: For the first one, $n$ is some power of 2 $$T(n) = \begin{cases} 4 & \text{if $n=1$} \\ 2T(\frac{n}{2}) +4 & \text{...
2
votes
0answers
58 views

Is this dynamic graph problem solvable?

I came up with following subproblem while working on another problem. Can someone confirm if its a recognized problem. I have spent months but couldn't make any progress. Design a data structure that ...
0
votes
0answers
22 views

What datastructure does google use to store its search engine indexes?

To the best of my knowledge search engines such as Google index the web using MapReduce amongst many other tools. With my limited experience this would make hash tables the most practical option for ...
3
votes
0answers
14 views

Distance queries on Tree [duplicate]

We are given a tree with n vertices and some of the vertices act as a "hotspot". We have to answer multiple queries of type (a,b,c), which means we have to find the distance to the nearest hotspot ...
2
votes
2answers
70 views

Distance queries on Tree with hotspots

We are given a tree with $n$ vertices and some of the vertices act as a "hotspot". We have to answer multiple queries of type $(a,b,c)$, which means we have to find the distance to the nearest ...
1
vote
2answers
111 views

What's the name of this tree-like data structure?

I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties: It consists of nodes and leaves It has a single root element Both nodes ...
1
vote
1answer
50 views

Data structure and structural relationships

“Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values, they involve important structural relationship between the ...
2
votes
1answer
27 views

What is the difference in time-complexity for sorting these 2-d arrays?

Let $A$ have $n/10$ rows, $10$ columns and $n$ overall elements Let $B$ have 10 rows, $n/10$ columns and $n$ overall elements. It is given that each row is sorted in ascending order, Can you sort ...
0
votes
0answers
15 views

Alternate Range in Van Emde Boas Tree

DISCLAIMER: I initially asked this question of Stack Overflow but that seems like the wrong place in hindsight so I want to ask here as well since this site is more meant for students and their ...
1
vote
1answer
68 views

Bounds on update time in the RMQ problem subject to $O(1)$ query time?

In the static RMQ problem, one has to answer queries about the minimum in a range of a fixed array. A classic variation allows updates of the form $A_i \leftarrow x $. My question is : How fast can ...
0
votes
0answers
16 views

How to reconstruct an existing splay tree by insertion?

I'm trying to figure out the same problem as stated in this question. In brief, I want to reconstruct an existing splay tree (printed on paper) on Splay Tree Visualization by inserting the values in ...
1
vote
0answers
28 views

Matrix multiplication over range in $O(n)$

Let $Q$ denote the number of queries. I have a $25 \times 25$ matrix in each cell of an array of size $n$. Let us denote this array by $A$. It's a special matrix, more specifically, all elements are $...
1
vote
1answer
30 views

Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?

If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)...
2
votes
1answer
156 views

What is the fastest way to merge two B trees?

Given two B-trees of some order $m$ - $T_1,T_2$, such that $y > x$ for every pair $x \in T_1$ and $y \in T_2$. What is the fastest way to create a new tree that is the union of both $T_1,T_2$? My ...
0
votes
0answers
25 views

How to trace Subset from Boolean DP table in the Subset Sum Problem

I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result. My questions are. How did someone conclude that ...
0
votes
0answers
21 views

Benefits of linked lists over forests for disjoint sets

CLRS discusses two specific data structures for disjoint sets: Single linked lists, where each set is represented by a single linked list, and each node has two pointers, one to the list head and ...
1
vote
1answer
66 views

Why is it that Ternary search trees are memory efficient?

I'm trying to figure out why ternary search trees are memory efficient. I have tried to read up on this, but all articles I find only state it's memory efficient compared to tries, but not why. I ...
1
vote
1answer
42 views

Monotonic queues recurrence relation

I'm looking at the following explanation of monotonic queues and their applications in problem solving. Monotonic Queue Summary I have a reasonable understanding of this data structure and the ...
1
vote
1answer
46 views

Is there a way to get O(1) without extra space in the union find algorithm?

Is there a way to get O(1) without extra space in the union find algorithm? Imagine I have 3 sets set1 = {1, 3, 5, 7} set2 = {4,20,25} set3 = {9, 13} Now ...

1
2 3 4 5
34