# Questions tagged [data-structures]

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

2,184 questions
Filter by
Sorted by
Tagged with
1 vote
40 views

### Best online algorithm for a monotone priority queue that has equal amount of deletion and insertions

I got an executor thread that is given jobs to execute at certain timestamp. So this means my problem is online. While there are cases when the new job has a timestamp in the past, we can easily test ...
27 views

### Trie minimization when order doesn't matter

How would I ensure I obtain a minimal trie when the order of elements is not important (ie - "abdc" is equivalent to "cbad" for my purposes)? To be clear, minimal means the least ...
33 views

### Top K Most Frequent Elements and Bucket Sorting Intuition

Link to Problem: https://leetcode.com/problems/top-k-frequent-elements/description/ Bucket Sort Solution: https://leetcode.com/problems/top-k-frequent-elements/solutions/5032156/beats-96-39-of-users-...
32 views

### Approximate Set Intersection datastructure

I'm working on a project involving set-like data structures. For one of the algorithms I am using that does a merge-like operation on two of these structures I can take a very big shortcut if I know ...
8 views

### How can I optimize the performance of a large React application with multiple state updates?

I'm working on a large React application that has several components with frequent state updates. I've noticed that the performance is starting to degrade, especially when there are multiple ...
97 views

### Detect if an interval is fully covered by union of previous intervals in sequence

Given a sequence of intervals $I_1, I_2, \ldots$, is there an efficient way to detect whether some interval $I_i$ is completely contained in the union of the preceding intervals $I_1, \ldots, I_{i-1}$?...
• 163
61 views

### Given an AVL tree of size n, is it possible to split the tree into 'k' equal sized search-trees in less than O(n) time?

The question first asked to split the AVL tree of size n into k equal sized search trees(k devides n) in O(n) time, and I solved this by moving all the AVL tree values into an array, and from there ...
• 23
68 views

### Data structure that supports adding to evenly spaced indices

I need an array-like data structure that stores integers and supports fast addition to multiple evenly spaced elements on given interval. Formally, if $n$ is length of the array, it has to support ...
• 51
1 vote
102 views

### Using XOR operation, a MOD operation compute a function f(n)

I had a difficult assignment in my Data Structures and Algorithms class. We need to implement a program that computes a function f(n) based on the following known values of n and f(n): n : 9689 ...
63 views

### Efficient data structure for multidimensional lookup

I'm doing a search problem over 18-tuples of non-negative integers. Some tuples are GOOD and some tuples are BAD, and I'm trying to list all of the GOOD tuples exactly once. It turns out that if a ...
• 768
19 views

### Time complexity of optimal index

Consider a data structure that stores a set of $n$ objects, where each object is a map of arbitrary key-value pair. The data structure maintains a reverse lookup table, where for each key-value pair, ...
• 133
1 vote
52 views

### Efficient data structure for fast Insertions, lookups, and union operations on sets

I need data structure that is able to perform the following operations efficiently: Insert a new element into a set. Lookup element in set. Compute the union of two sets. Union operation should ...
98 views

### How to Determining the Big O Complexity of a Recursive Function?

I'm struggling to determine the correct time complexity of a recursive function from an exam question. The function definition is as follows: fun (n) { ...
14 views

### Datastore supporting TTL with range queries

We have a data access pattern in which we need to get users added in the time range say timestamp-1 to timestamp-2 and we don't want to keep older data say max 1 day, so DB should have an inbuilt ...
• 101
25 views

### How to do different cases of Union Find?

Here is the question: I understand that the absolute parents are 1, 3, 0, and 8, respectively, but I'm not sure how to do union here. Could someone help me understand how to do this?
37 views

### Efficient ordered single-writer multi-reader list with "add" and "bring to front" operations

I'm looking to implement a collection that needs to support only two operations: AddOrUpdate: Insert item into collection if it doesn't exist; otherwise, move it from whatever the current position is ...
• 133
62 views

### DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
• 123
42 views

### Online Pareto Front data structure for sparse high dimensional space

Problem I'm looking for a data structure to incrementally maintain a Pareto Front consisting of tuples in the high-dimensional space $(\mathbb{R} \cup \{\pm \infty\})^K$, with the number of dimensions ...
• 121
1 vote
28 views

### Datastructures for finding unifiable terms

I am looking for a datastructure that supports the following operations: Add a term Remove a term Return a pair of unifiable terms if one exists. Ideally, 3 would be as close as possible to ...
• 111
49 views

### Splitting a binomial heap into 3n/8 and 5n/8 binomial heap whereas 8 divides n with O(log(n)) time

I ran into this exercise that says: With a given binomial heap with n elements and n is divisible by 8, split the heap into 2 binomial heaps, one with 3n/8 elements and the other with 5n/8 elements. ...
21 views

### Unique Tree using Inorder & Postorder traversals

This question appeared in my data structures examination : You are given that GDCBFAHEJ is an in-order traversal and GCDBHJAEF is a post-order traversal. Either build the unique tree for which these ...
148 views

### Why finding the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

How we can prove that the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time? Is this useful that worst running time for comparison based sorting is >= longest path ...
180 views

### Why $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences [duplicate]

How we can prove that $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences of $n$ elements each into one sorted sequence? I tried to prove it with binary decision tree, ...
39 views

### Want to plot rectangles given their width,height and the cartesian origin (0,0)

The info I am given : block_ID, block_width, block_height as well as how the cuts between the rectangles are(horizontal or vertical); for example two rectangles can be joined by a horizontal cut or a ...
• 11
76 views

### Examples of algorithms best their class that require cyclical data structures

I remember that the Roc Lang website claimed that their choice to forbid any form of cyclic data structures prohibited their customer to implement some of the best in their class algorithms, id est ...
• 99
1 vote
31 views

### Data structure to keep track of cache hit ratio?

In a web application, I use a map as a simple in-memory cache/lookup. A key is a string, say A and maps to an integer value, say ...
• 231
1 vote
46 views

### Update priority of existing item in a minmax heap

Say you have a double ended priority queue in the form of a minmax heap as described here. What is the most efficient algorithm to update the priority of an existing item? Assume that I explicitly ...
• 133
28 views

### Page miss in 2Q Cache Replacement

I am studying about 2Q Cache Replacement Policy and i came across this post. They have worked out an example with the following page keys [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] and cache memory of 5 ...
182 views

### Improving a ranking system with "best rank"

I've implemented a ranking system (based on a score), using a Map<Player,Score> and an improved BST<Score, Set<Player>>. So now I can compute "rank of a player" in O(log(n))...
• 143
143 views

### Recursive formula for height of BST

Let $H(n)$ be the average height of a BST with nodes from ${1,...,n}$. I think that $$H(n) = \frac{1}{n}\sum_{i = 0}^{n-1}\left[\text{max}(H(i), H(n-1 -i)) + 1\right]$$ But I don't know how to prove ...
230 views

### How to optimize algorithm to solve the following time series problem?

I am working on a project and came across the following problem I have to solve. Imagine we have a time series data Ts which is an array of pair, say each element ...
1 vote
113 views

### How many comparative sorting algorithms are there?

I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
• 51
1 vote
61 views

### Amortized analysis of dynamic array insertion

I learned the amortized analysis of Prof Demaine's 6.006 videos. The Erik's thesis was, If we reallocate memory by doubling capacity => $$1 +2+4 + 8 + 16 +..+n = \theta(2^{lgn}) = \theta(n)$$ From ...
767 views

### Time complexity to remove an item from the heap

Given an array of size $n$ that has the item of the heap. To remove an arbitrary element from the heap we would need $O(n)$ to find the element and then $O(logn)$ to reheapify if I am commrect, which ...
• 505
73 views

### Kd-trees excluding some splitting dimensions

I have a 12-dimensional state-space and would like to use a kd-tree to partition my data, so that nearest neighbour operations can be performed quickly. Unfortunately I have the issue that three of ...
• 143
120 views

### A data structure for an allocation-free dynamic sample rate buffer

I'm looking for a data structure that would allow storing samples (in O(1)) from a data stream in a fixed-size buffer while the stream length isn't known in advance. Once the buffer size is exhausted ...
26 views

### Use case for string matching in a 2 by n grid

In a 2 by n grid there is a character in each cell. A path can start at any cell and then you can move to right or down. This way each path will denote a string written by characters on cells visited ...
1 vote
71 views

### Optimal Data structure for queries involved rectangles and cartesian coordinates

What data structure would be optimal in terms of time and space for the following usecase: Given information about rectangles in the form of- {rectangle_id,left_bottom_corner_x, ...
• 11
62 views

### Help understand Z order curve range searching

After "speaking" with ChatGPT, I decided to test Z Order Curve. The code interleaves 2D data, then search for range x: [2..4], y: [2..4] Programming code using C/C++ should be as follows: <...
• 105
1 vote
97 views

### Could a compiler/static analysis infer the best abstract data type?

I initially brought this up on the Swift Forums, and it was suggested that this might be a thing better suited for CS SE. So here goes: I had this thought that the compiler already has enough ...
• 111
1 vote
96 views

### Succint data structure for storing n numbers using a mask-based partition

I've a set $N$ of $n$ distinct numbers of $d$-bits each; call them words ($1\leq n\leq 2^d$, with $d\geq 1$). I want to store $N$ using as least space as possible, by partitioning $N$ and factoring ...
• 529
405 views

### Prove that the number of comparisons between elements in binary heap build is at most (2n-2)

Question Prove that the number of comparisons between elements in binary heap build is at most $2n-2$. $n$ is the total number of the nodes. Pseudocode ...
• 143
33 views

### A probabilistic data structure based on flipping bits with probability $\frac{1}{2^x}$ for counting

How does this data structure work and what is its application? ...
1 vote
65 views

### Finding the pair of nodes with maximum distance in an arbitrary rooted tree

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, ...
1 vote
72 views

### Does a sorted sequence from in-order traversal imply a binary tree is a BST?

An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the ...
1 vote
108 views

### Memory-efficient representation of keys over a huge domain

I don't know if the title of the question is accurated or not, but I was thinking of the following problem: I have a set of numbers, let's call them identifiers. Each identifier is stored on a 64-bit ...
• 529
11 views

### In SSTables, why is it possible to group records and compress them?

I am currently reading 'Designing Data Intensive Applications' by Kleppman. In the SSTables and LSM Trees section, it is mentioned that one of the advantage of SSTables is: "Since read requests ...
88 views

### Optimal graph data structure for set of points that allows dynamic updates

We aim to optimize the execution of a specific task. Consider a set, P, containing N 2D points. A new query point, p1, is introduced, and the objective is to identify the nearest point in P to p1. If ...
1 vote
129 views

### I want to start preparing for a job interviews for which i want to get a decent at solving DSA problems

How to learn DSA if you are already working as a software engineer and have decent knowledge about development. Only thing that makes me procratinate is going over theories behind different data ...
• 119