Skip to main content

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
1 vote
1 answer
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 ...
Giancarlo's user avatar
0 votes
1 answer
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 ...
Sprite123's user avatar
-1 votes
1 answer
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-...
penguin365's user avatar
2 votes
0 answers
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 ...
MacroPolo's user avatar
0 votes
0 answers
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 ...
Salman Mehmood's user avatar
3 votes
3 answers
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}$?...
MattDs17's user avatar
  • 163
2 votes
2 answers
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 ...
Thomas's user avatar
  • 23
5 votes
0 answers
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 ...
Risodu's user avatar
  • 51
1 vote
1 answer
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 ...
Shiyao Ju's user avatar
0 votes
6 answers
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 ...
user326210's user avatar
0 votes
0 answers
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, ...
SOFe's user avatar
  • 133
1 vote
1 answer
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 ...
Euler-Maskerony's user avatar
4 votes
2 answers
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) { ...
deaa aldeen's user avatar
0 votes
0 answers
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 ...
tusharRawat's user avatar
0 votes
1 answer
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?
MotherHorse's user avatar
0 votes
1 answer
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 ...
Bogey's user avatar
  • 133
2 votes
1 answer
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 ...
Michel H's user avatar
  • 123
2 votes
0 answers
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 ...
KarelPeeters's user avatar
1 vote
0 answers
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 ...
manzana's user avatar
  • 111
0 votes
1 answer
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. ...
The Bulletbroof Joker's user avatar
0 votes
1 answer
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 ...
Priyansh Kumar's user avatar
0 votes
2 answers
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 ...
Aleksandra Nowińska's user avatar
4 votes
1 answer
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, ...
Aleksandra Nowińska's user avatar
0 votes
0 answers
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 ...
zero_day's user avatar
-1 votes
1 answer
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 ...
Delfin's user avatar
  • 99
1 vote
1 answer
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 ...
BMBM's user avatar
  • 231
1 vote
0 answers
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 ...
Bogey's user avatar
  • 133
0 votes
0 answers
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 ...
user avatar
4 votes
1 answer
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))...
Nisalon's user avatar
  • 143
0 votes
2 answers
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 ...
user167064's user avatar
3 votes
1 answer
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 ...
askyfullofstars's user avatar
1 vote
0 answers
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). ...
sbh's user avatar
  • 51
1 vote
0 answers
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 ...
Huseyin Okan Demir's user avatar
0 votes
1 answer
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 ...
Avv's user avatar
  • 505
2 votes
1 answer
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 ...
Lord Cat's user avatar
  • 143
3 votes
1 answer
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 ...
Eugene Pankov's user avatar
0 votes
0 answers
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 ...
Iridescent 53's user avatar
1 vote
0 answers
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, ...
zero_day's user avatar
0 votes
0 answers
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: <...
Nick's user avatar
  • 105
1 vote
2 answers
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 ...
Manav's user avatar
  • 111
1 vote
0 answers
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 ...
ABu's user avatar
  • 529
2 votes
1 answer
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 ...
Lior's user avatar
  • 143
0 votes
0 answers
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? ...
Mason Rashford's user avatar
1 vote
1 answer
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)$, ...
Mason Rashford's user avatar
1 vote
1 answer
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 ...
Mason Rashford's user avatar
1 vote
2 answers
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 ...
ABu's user avatar
  • 529
0 votes
0 answers
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 ...
Udeshya D.'s user avatar
2 votes
1 answer
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 ...
Apurv Mishra's user avatar
1 vote
2 answers
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 ...
Hardik Dhuri's user avatar
3 votes
2 answers
419 views

Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
xdaimon's user avatar
  • 53

1
2 3 4 5
44