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
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 ...
bruh's user avatar
  • 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 ...
xdaimon's user avatar
  • 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 ...
cm64's user avatar
  • 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 ...
tbhaxor's user avatar
  • 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 ...
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
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 ...
popcorn's user avatar
  • 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 ...
Lance's user avatar
  • 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 $(...
user779130's user avatar
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 ...
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
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 ...
Josh Tint's user avatar
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) ...
Microfractal's user avatar
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 ...
ocksumoron's user avatar
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.
kjkjkjkjkj's user avatar
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 ...
QuantumStatic's user avatar
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 ...
qpexxtt's user avatar
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 ...
jackb's user avatar
  • 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 ...
Nikita Artemenko's user avatar
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, ...
user442920's user avatar
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 ...
maxy's user avatar
  • 1
0 votes
2 answers
48 views

Use of pointers in linked list

The following code is from GeeksForGeeks ...
Buddy's user avatar
  • 1
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 ...
SmileyCraft's user avatar
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 ...
lapots's user avatar
  • 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 ...
Valeria's user avatar
  • 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 ...
Proper Illumination's user avatar
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 ...
user129393192's user avatar
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 <...
ilovewt's user avatar
  • 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 ...
Ethan Chan's user avatar
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 ...
ilovewt's user avatar
  • 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 ...
sleekster's user avatar
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 ...
Remeraze's user avatar
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 <...
Karan Bakshi's user avatar
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 ...
Sergey's user avatar
  • 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 ...
Senthil's user avatar
-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: ...
user_1234's user avatar
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 ...
Hugh Mann's user avatar
-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 ...
Vk1's user avatar
  • 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 ...
bihariforces's user avatar
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 ...
geofflittle's user avatar
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 ...
user129393192's user avatar
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. ...
user129393192's user avatar
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 ...
bazylevnik0's user avatar
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 ...
bihariforces's user avatar
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 ...
user129393192's user avatar
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 ...
Mike Battaglia's user avatar
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 ...
Muhammad Z's user avatar
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$ ...
Jake's user avatar
  • 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 (...
Vladislav Bezhentsev's user avatar

1
2 3 4 5
43