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

better and good and more solution on which platform

Do anyone has idea which platform has better and more solution for book data structure and algorithm in c++ by goodrich in course hero or bartleby
noidea's user avatar
  • 1
-1 votes
1 answer
34 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
23 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
36 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
26 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
169 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
  • 141
0 votes
2 answers
137 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
222 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
106 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
56 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
56 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
53 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
61 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, ...
fat_gladiator17's user avatar
0 votes
0 answers
32 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
  • 101
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
94 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
  • 499
2 votes
1 answer
317 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
32 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
47 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
58 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
107 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
  • 499
0 votes
0 answers
10 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
0 votes
2 answers
97 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
408 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
  • 142
0 votes
1 answer
122 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
25 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
48 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
  • 73
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,193
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
25 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
1 answer
34 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
48 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
15 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
117 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
52 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
34 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
0 votes
0 answers
19 views

Secondary Memory Data Structures and allocation strategies for intermediate query results

Despite a huge amount of literature regarding table representation and indexing in secondary memory (also including database books), I found no information on how relational databases represent ...
jackb's user avatar
  • 101
0 votes
1 answer
38 views

Why Random Access Machine could only have $N \leq 2^{W}$ memory slots? Is it general theorem of informal rule?

Here: $W$ is "bitness" - number of bits in one machine word, that could be stored in memory slots $N$ - number of memory slots (each has bitness equals $W$) My solution: If max length of ...
Nikita Artemenko's user avatar
0 votes
0 answers
23 views

Are these two implementations of Bag different monads?

I am not an expert with functional programming. What I know is that the bag data structure satisfies the definition of a monad. There are two different implementations of Bag: one with linked lists, ...
user442920's user avatar
0 votes
0 answers
27 views

Data structure for detecting duplicate entries efficiently

In search of an efficient data structure to store some sort of list hash that I can compare to a value to obtain a probability of it already being in the list. Perhaps it makes more sense defined as ...
maxy's user avatar
  • 1
0 votes
2 answers
72 views

Use of pointers in linked list

The following code is from GeeksForGeeks ...
Buddy's user avatar
  • 1
1 vote
1 answer
54 views

Memory efficient undo data structure

I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but ...
SmileyCraft's user avatar
0 votes
0 answers
27 views

Approach for the fake data generator that needs to maintain an order and referential integrity

I have a Python data generator capable of generating SQL-like relational data with primary and foreign key relationships, composite keys, and partial keys. Currently, I store this data in-memory using ...
lapots's user avatar
  • 125

1
2 3 4 5
44