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
1 answer
46 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
40 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
26 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
47 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
19 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
147 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
165 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
68 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
28 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
39 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
  • 131
0 votes
0 answers
27 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
173 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
140 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
226 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
111 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
60 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
311 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
58 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
119 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
69 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
39 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
365 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
56 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
65 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
102 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
415 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
0 votes
2 answers
50 views

Will a FIFO buffer eventually stagnate?

Below depicts a FIFO buffer: So the buffer is there for when the speed of data written into the FIFO buffer is faster than the data read. But I don't understand one thing. Wouldn't eventually all the ...
cm64's user avatar
  • 101
0 votes
2 answers
73 views

Why is the push operation in incrementally grown array stack is $O(n^2)$

This is from the Narasimha's data structure book For nth element (n - 1 index), if we want to push an element, create a new array of size n and copy old array to the new, and at the end assign the ...
tbhaxor's user avatar
  • 208
0 votes
1 answer
131 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
Anurag Prasad's user avatar
0 votes
0 answers
26 views

Concurrent datastructure modification

Given sets A, B, C with a parent-child (one to many) relationship between ...
Aedoro's user avatar
  • 101
0 votes
1 answer
59 views

Find a substring length $k$ with maximum occurrences

Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string. We want $O(S)$ time complexity in an average case. I think the solution lies in sophisticated ...
popcorn's user avatar
  • 183
0 votes
1 answer
35 views

Can a trie or DAWG loop?

I am looking at DAWGs, which are compressed tries, like this: It is an acyclic graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure. For example, I am ...
Lance's user avatar
  • 2,223
1 vote
1 answer
59 views

Complexity of non-commutative range multiplication operation

Let $G$ be a non-commutative group, such as $\operatorname{GL}_k(\mathbb F_p)$. Given a list $\vec{a}=(a_1, \cdots, a_n) \in G^n$, we use $(p, q, x)$ to denote the operation that maps $\vec{a}$ to $(...
user779130's user avatar
1 vote
1 answer
26 views

Linked Lists, Ordered Pairs?

I would like to model linked lists using set theory similar to that in Scheme and LISP. There is a set theoretic definition of the ordered pair: $p = \{\{a, 1\}, \{b, 2\}\}$ My question is how does ...
notaorb's user avatar
  • 111
0 votes
2 answers
61 views

Should I concatenate three lists together or use two separate while loops in Python? Which option offers a better runtime complexity?

In the context of adding sparse polynomials, you have two alternative approaches to combine the terms from two separate polynomials. One option is to use the line of code ...
alefvanoon's user avatar
2 votes
1 answer
68 views

Checking equality of self-referential lists

Define that an srlist ("self-referential list") over $X$ consists of a list of elements of $X \sqcup \mathrm{srlist}(X).$ So basically, the items can be primitive values, or further self-...
SocraticMathTutor's user avatar
1 vote
2 answers
57 views

Data Structure for efficient nearest neighbor search using generalized distance?

I have a list of objects that have a defined measure of distance between them and I'm trying to store them in a data structure such that I can easily and quickly query which of the objects is closest ...
Josh Tint's user avatar
0 votes
0 answers
17 views

Mixfix-parser: finding associated tokens on a list

I've been trying to design an in-program programming language. Like any programming language, the input source code must go through various stages: Divide the source code into tokens. (Tokenizer) ...
Microfractal's user avatar
2 votes
0 answers
87 views

Data structure for prefix covering

I have a list $[1, 2, \ldots, T]$. I want to create a collection of subsets, such that: each element belongs to a small number of subsets each prefix is a union of small number of subsets (these ...
ocksumoron's user avatar
0 votes
1 answer
149 views

Why boolean value in Python is 24/28 bytes?

What is the reason for this behavior? Usually, in other programming languages, it is either 4/8 bytes, if I am correct.
kjkjkjkjkj's user avatar
0 votes
0 answers
58 views

Quake Heaps with Heap-Ordered Trees instead of Tournament Trees

In the paper titled Quake Heaps:A Simple Alternative to Fibonacci Heaps, by Timothy Chan He mentions that: The tournament trees require a linear number of extra nodes, but more space- efficient ...
QuantumStatic's user avatar
0 votes
0 answers
36 views

Find submatrix with sum as close to k as possible

What is the efficient algorithm to find a submatrix (must be rectangle) with a sum that is as close as possible to k? Matrix consists only of nonnegative integers. Iterating through all possible ...
qpexxtt's user avatar

1
2 3 4 5
44