Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
2,143
questions
0
votes
0
answers
18
views
Turring Machine Equivalence Proof [closed]
Turing Machine where instead of having a set of final
states F it has:
A designated final state qaccept which exists in Q set of states. Upon being in this state, it halts, and accepts
the input.
A ...
- 1
3
votes
2
answers
371
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 ...
- 53
0
votes
1
answer
30
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 ...
- 101
0
votes
1
answer
34
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 ...
- 128
0
votes
1
answer
88
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 ...
0
votes
0
answers
25
views
Concurrent datastructure modification
Given sets A, B, C with a parent-child (one to many) relationship between ...
- 101
0
votes
1
answer
39
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 ...
- 31
0
votes
1
answer
26
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 ...
- 2,163
1
vote
1
answer
58
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 $(...
- 13
1
vote
1
answer
22
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 ...
- 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 ...
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-...
1
vote
2
answers
40
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 ...
- 13
0
votes
0
answers
13
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)
...
2
votes
0
answers
84
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 ...
- 21
0
votes
1
answer
89
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.
- 19
0
votes
0
answers
46
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 ...
0
votes
0
answers
32
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 ...
- 1
0
votes
0
answers
18
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 ...
- 101
0
votes
1
answer
36
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 ...
0
votes
0
answers
20
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, ...
- 101
0
votes
0
answers
26
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 ...
- 1
0
votes
2
answers
48
views
1
vote
1
answer
44
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 ...
- 175
0
votes
0
answers
22
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 ...
- 125
0
votes
1
answer
42
views
Fast construction of a static KD-tree without duplicates
From what I know, the classic way of constructing a KD-tree is with alternating dimensions and finding median at each level. In my dataset, I have a lot of duplicated points, and I want to incorporate ...
- 127
0
votes
1
answer
31
views
Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting
The following theorem was proven by R.E. Tarjan in 1984:
Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time ...
0
votes
0
answers
41
views
finding the length of the GCD of two strings
Let's say you have two strings: a and b with GCD c. Why is it that ...
- 171
0
votes
0
answers
40
views
Is my mathematical representation of search in binary search tree correct?
You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals <...
- 113
0
votes
1
answer
61
views
Two Questions About Fibonacci Heaps
I am learning about Fibonacci heaps from the following set of notes: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm. There are 2 things that are confusing me.
Firstly, in the ...
- 101
1
vote
1
answer
54
views
Understanding the Internal Stack Frames in a Recursive Function Call
I'm trying to understand how the system's call stack works internally when a
recursive function is called. Specifically, I'm looking at a function that
computes the maximum depth of a binary tree ...
- 113
0
votes
1
answer
45
views
Is this Patricia tree implementation wrong?
I'm reading the chapter Radix Search of the book Algorithms (Robert Sedgwick).
I've made a simple implementation and something isn't behaving as expected.
In program ...
0
votes
2
answers
56
views
AVL tree with balance factor equal to depth
If you were to define an altered AVL tree where the balance factor (the difference between the height of the left and right subtree) of a node must be less than or equal to the depth of the node (in ...
- 3
0
votes
0
answers
18
views
Data structure for arguments in Arrow functions in JS
As per the rules of JS, Arrow functions don't have an argument Object, like a regular function inside JS.
But it is also true, that we can pass arguments to the <...
0
votes
1
answer
68
views
Why does Java's HashSet have an underlying HashMap, not the other way around?
Why does Java's HashSet have an underlying HashMap, not the other way around? HashMap could ...
- 101
0
votes
1
answer
32
views
How to generate all the possible nodes inside a polygon, if the polygon is represented by its vertices
If a polygon is represented by its vertices(latitudes, longitudes), is it possible to find all the possible points or nodes(latitudes, longitudes). If so, what kind of algorithm is used. The polygon ...
- 3
-1
votes
1
answer
48
views
How to calculate average hours worked from bar graph
I want to calculate average hours worked from below bar graph and following this method but I feel this method is not correct to find average working hours
Procedure A:
...
- 99
2
votes
0
answers
117
views
Difficulty in last sentence in proof of "Amortized cost of $\text{Find-Set}$ operation is $O(\alpha(n))$" from CLRS
I was reading the section of Data Structures for Disjoint Sets from the text Introduction to Algorithms by Cormen et. al. I made it through the proof, but I'm not sure I understand the very last ...
- 67
-2
votes
1
answer
54
views
Data Structure for strings on integers
Designing a datastructure which supports the following operations on integers (It can also be visualized as a datastructure on strings, if the alphabets/characters have total ordering)
Operations on ...
- 118
1
vote
1
answer
96
views
Longest Increasing Co-Prime Subsequence?
This is a made up question not seen somewhere so I am not sure if a good solution exists but here it is anyways.
Given an array $ A $ of $ N $ non-negative integers, find the longest non-decreasing ...
- 105
0
votes
0
answers
37
views
Data structure for arithmetic logical queries
Abstract Problem
I'm looking for a data structure that will (1) allow me to make queries of the form A.x - B.x <= 0.1 AND A.y + B.y >= C.y + D.y and (2) allow ...
- 161
1
vote
1
answer
48
views
Disk addressing
I am wondering how disk addresses are accessed from a program. From my understanding, the two main facilities are programmed I/O (instructions) and memory-mapped I/O (simply loads and stores). The ...
- 171
0
votes
1
answer
45
views
Memory (physical addressing)
From my understanding, physical memory (main memory -- DRAM) is addressed differently than disk. This is all a bit of an abstraction to me, and I am hoping to make my understanding more concrete.
...
- 171
2
votes
1
answer
65
views
Creative solving of searching redundant connection in graph
I am trying to solve problem in leetcode:
https://leetcode.com/problems/redundant-connection/description/
*finding redundant connection in undirected graph
And now I am writing a solution, inpired by ...
- 23
7
votes
2
answers
331
views
Queries to count points lying on arbitrary line
Suppose we have $N$ points on $XY$ plane, ie. $(x, y)$ and $x, y \in Z$ and multiple queries where each query is of the form $y = mx + c$ and $m, c \in Z$.
Is it possible to count number of points ...
- 105
2
votes
0
answers
21
views
Log-Structured Filesystem -- why do we need an explicit, scattered inode map?
From OSTEP Chp. 43:
The imap is a structure that takes an inode number
as input and produces the disk address of the most recent version of the inode
This makes sense to me as a solution to the ...
- 171
1
vote
0
answers
40
views
Networks and data flow - graph algorithms for propagating updates from nodes correctly
Suppose I have an acyclic directed graph of Nodes which subscribe to Events. When an Event callback is activated for some Node, the Node's internal update() method is called. Then, because the Node ...
- 837
1
vote
0
answers
29
views
generating solvable puzzles for a Double-Choco puzzle game. efficient data structure and algorithm to be used in? [closed]
I'm working on implementing a puzzle board game called Double-Choco published by Nikoli magazine
Where the board is a 2-dimensional matrix with cells that are either white or gray. The goal is to ...
- 111
0
votes
1
answer
59
views
Data structure for fast look up of ranges, but that allows insertion
At work I'm looking for a data structure that supports the following operations:
$$insert(X, A, B)$$
$$delete(X)$$
$$glb(C)$$
$insert$ adds the range $[A, B)$ into the data structure with value $X$ ...
- 3,790
0
votes
0
answers
54
views
Segment queries over a key-value store
We want to implement a data structure, which can store pairs of $(key, value)$ (where $key$ and $value$ are some numbers) and has the following interface:
Add $(key, value)$ pair to a data structure (...
