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
16
votes
8answers
3k 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 ...
1
vote
1answer
19 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
35 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 ...
2
votes
1answer
2k views

Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
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
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 ...
4
votes
3answers
5k views

how is data in a tree stored in memory?

I am not so familiar with trees. How is a tree stored in memory? what is the data structure type used for storing it? As a string?linked list? stack (!)? Or is there some kind of data storage model ...
0
votes
1answer
54 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
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
55 views

Priority Queue - When Prioritizing Take Place?

In a Priority Queue we first enqueue according to the priority given to the element? Or we enqueue just like a queue but dequeue high the highest priority element first? Or both ways are acceptable?
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 ...
1
vote
1answer
86 views

Find number of triples that sum up to zero in query-intervals

My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array. For each query, we ...
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
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 ...
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?
-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 ...
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 ...
4
votes
1answer
55 views

How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
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 ...
0
votes
3answers
83 views

Formal definition of the Dynamic Array - what is the Dynamic Array

I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points. ...
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 ...
0
votes
1answer
142 views

How to delete an element from a B-tree

There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree. For example, given the following tree, how would we delete 26 and ...
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 ...
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 ...
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
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 ...
-2
votes
2answers
696 views

Algorithm for checking if all subarrays have an unique element

How to check if all subarrays of the array contain at least one unique element for NlogN complexity, where N is the length of the array? For example: 3 1 2 1 2 5 6...
0
votes
1answer
289 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
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
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
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
53 views

Name for type of actions that only care for outcome

There is a definition for kind of actions that only care for outcome. Classic example for such an action is remove from ...
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 ...
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 ...
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
448 views

Maximizing book picked using two stacks

There are two stacks $S_1$ and $S_2$ of books. Each book in stack has a weight. You are given a net weight $W$ of books that can be picked. You have to maximize the number of books that can be picked. ...
0
votes
1answer
21 views

Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST)

I have some propositions regarding BSTs , please can someone confirm whether they are true or false: Question : 1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$ 2.We wish ...
0
votes
1answer
26 views

Dynamic array updated by adding arithmetic progressions

I have an array $a_1, a_2, \dots, a_n$. After $O(n)$ preprocessing, I want to be able to compute each of the following in amortized $O(\log n)$: Given $l,r,b,d$, for each $i \in \{l,\ldots,r\}$, ...
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 ...
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
21 views

Constructing a data structure supporting prioritized key lookup

so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps. Here is the problem description (pseudo formal): I want to have a structure $T = \{ \hat{...
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 - ...
2
votes
1answer
23 views

Data structure for or-lookups over bit-field associations maps

For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality. Slightly more formally, I have a set of associations $k_i \mapsto v_i$ where $k_i \in \mathcal{...
7
votes
2answers
7k views

Why in a min priority queue (heap based) it is called “decrease-key” and not just “set-key”?

When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to ...
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
2 3 4 5
33