Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
2,061
questions
0
votes
0
answers
13
views
What data structure has the most succinct proofs and can be modified efficiently?
Question
What data structure has the most succinct proofs and can be modified (insert, update, delete) efficiently?
I have proposed a modification of merkle tree hashing as a potential solution but ...
- 1
0
votes
0
answers
21
views
Improper binary tree: maximum number of external nodes
A binary tree shall be called proper if each node has either zero or two children. If it is not proper, it shall be called improper.
I need to determine the maximum number of external nodes in an ...
- 101
0
votes
1
answer
34
views
Maximum, delete and insert fastest data structure
The runtime to find a min element in max heap is $O(1)$. It takes $O(\log n)$ time to delete an element and $O(\log n)$ time to insert a new element in the heap.
Does there exists a data structure in ...
- 123
0
votes
1
answer
33
views
Is returning pointers to nodes for a list (doubly linked list) implementation a leaky abstraction? and is it bad?
I've been studying closely about the List abstract data type - As I understand it can be implemented with linked-list and/or arrays, and really maybe with any other data types as well.
But to satisfy ...
- 11
1
vote
0
answers
22
views
What's the difference between the two abstract data types collection vs container?
From abstract data types in wiki, I'm reading about two types: collection and container. Can anyone supply a better detailed difference between the difference between the two?
https://en.wikipedia.org/...
- 11
2
votes
1
answer
88
views
Approximating the median of the complement of a set
Given an integer $n$ and a tree set $S$, I would like to find the approximate median $x$ of the integer set $T := \{i \in \mathbb N : i < n \wedge i \notin S\}$. There are no constraints to the ...
- 131
-1
votes
0
answers
21
views
what abstract data type does array belong to if it is a data structure, i.e. in javasript?
if array is just a data structure, I was wondering what abstract data type does it satisfy? When searched online whether Array is an adt or data struct, there are a lot of polarizing answers.
- 11
0
votes
1
answer
47
views
Why is Javacript's Object not a primitive data type?
If javascript's object is just associative array, what makes it non-primitive as they have labeled it? It is certainly already built in. Its not like I'm creating my own concrete implementation of ...
- 11
2
votes
0
answers
39
views
Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?
How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at ...
-4
votes
0
answers
15
views
Take input from the user and convert lowercase letters to uppercase in MMIX
Write an MMIX program that converts each letter to uppercase
converted.
• Take text input from the user.
• Write subprogram to convert the input to upper case.
delve
The thing is I do not know how to ...
1
vote
0
answers
34
views
What is the literature implementation of self-organizing lists?
I'm trying to implement self-organizing lists DS to publish as a public module. Over the course of Algorithms, we learnt that if you add a new element to the list, it should still do the huriectics. ...
- 231
0
votes
0
answers
32
views
What binary search tree to use if probabilities of element query are known apriori?
There is a universal set of integer pairs $(key; outcomes)$, a subset of which is inserted into a binary search tree in $O(\log n)$ time for each key and can be searched by keys. Afterwards a large ...
- 233
0
votes
1
answer
22
views
What is the most efficient way to represent an directed dynamic massive 3D graph?
I know that there are many techniques to represent graphs.
Suppose I have a directed massive 3D graph with 100,000 nodes at maximum.
Suppose the graph looks somewhat like the following:
Suppose each ...
- 153
0
votes
1
answer
22
views
Confusion about B-Tree
In a B-Tree, one of the rules is:
Every node (except the root) is at least half full
But then, in a 4-way B-Tree, we have the following case. Suppose we want to insert $10,20,30,40$ to the tree.
After ...
- 101
0
votes
2
answers
40
views
if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$?
if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$?
what if we also have $f(1)=2$?
0
votes
0
answers
23
views
In two level perfect hashing from CLRS we use m = n at the first level for expected space<=3n. Instead if we choose m = αn can space be decreased
In two level perfect hashing scheme shown in CLRS 3rd edition 11.5, this also has a great explanation here
We set m = n at
the first level and then for secondary hash tables we set mi = n^2. This ...
- 57
-1
votes
0
answers
30
views
What’s this data structure?
Given a series of timestamped values and some calculation can be done on a contiguous range of values. The calculation is composable. For efficiency, we can preemptively cache the calculations on ...
- 99
-1
votes
1
answer
25
views
A question about the graph theory or data structure and algorithms
I would like to ask this question as I am not sure about the answer.
Let $G=(V,E)$ be a connected, undirected graph, and let $x,y\in V$ be two different vertices. Let $A$ be the problem of finding the ...
- 3
1
vote
2
answers
82
views
Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
- 233
2
votes
0
answers
17
views
Proof that state-based (convergent) CRDTs are causally-consistent
Conflict-Free Replicated Datatypes (CRDTs) are a class of distributed data structures where replica states are allowed to temporarily diverge, but will eventually converge (in the absence of network ...
- 253
4
votes
1
answer
61
views
Function which describes an optimal data structure for a bounded number of query operations?
Given an ordered sequence of $n$ elements, you have to choose a family $A$ of subsets of consecutive elements, such that each subset of consecutive elements (not necessairly in $A$) can be represented ...
- 43
2
votes
0
answers
40
views
Enumeration of the vertices in a quad-edge structure
A quad-edge is a well-known data structure used to represent planar subdivisions or polyhedra. https://en.wikipedia.org/wiki/Quad-edge
The procedure to enumerate the edges works by recursively ...
- 6,085
0
votes
1
answer
30
views
Representing graph as a search tree
How do I convert a graph to a search tree? Here's the question-
The problem is that I don't know how to represent interconnections in a graph on a tree. In the diagram A is connected to D, and same ...
- 3
1
vote
1
answer
74
views
What is the proper way to approach a competitive coding problem?
***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/
1) Take the "***Climbing Stairs" Problem for instance: If I was given a problem like this on a test after mastering ...
2
votes
3
answers
68
views
Best Data Structure For Text Processing
Given a sentence like this, and i have the data structure (dictionary of lists):
{'cat': ['feline', 'kitten']}
A feline was recently spotted in the ...
- 121
1
vote
4
answers
54
views
How to index a table for fast intersection?
For example (and this is not my use case), imagine there is a set of 50 000 random natural numbers represented in decimal with 8 digits (in the range 00 000 000 to 99 999 999). We could index the set ...
- 13
0
votes
1
answer
34
views
Randomly build a binary search trees with simple modification
Let $X=x_1,x_2,x_3,\dots,x_n$ be set of $n$ distinct keys. I read this posts about Randomly build binary search trees like this and now I encounter the following question in my mind, suppose we ...
- 1,418
0
votes
1
answer
52
views
Way to call and explain: "potentially infinite set of attributes" in databases
This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms.
Let's say we have a database in which one ...
2
votes
2
answers
168
views
Designing a Data Structure that allows both insertion and extracting a number lower than median in amoritzed O(1) cost?
Consider a data structure that has only two functions. extract_lowerthan_median() and insert(). How can we design it in a way that the amortized cost for both the operation is O(1)?
Using a 2 tree, a ...
- 57
0
votes
1
answer
40
views
Minimizing/Maximizing recursion depth for DFS
The idea for this problem comes from GATE CS 2014 Set-3 Q13.
Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth?
Consider the graph from ...
- 656
0
votes
0
answers
47
views
Can anyone explain how a circular buffer array works?
I'm currently learning about Data Structures and Abstractions and one particular problem has been very confusing to me, and that is the concept of Circular ArrayDeque.
In particular, how can we add or ...
- 101
0
votes
0
answers
33
views
Isomorphism, one-to-one correspondence in Stack
From R C Lacher's slides on Data Structures,
These axioms can be used to prove, among other things, that the stack is unique up to isomorphism: Given any two stacks on the same data type, there is a ...
- 3
4
votes
1
answer
89
views
Optimal algorithmic complexity of "a nonrepetitive stack"?
I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'.
A ...
- 1,319
0
votes
1
answer
116
views
Update a property of all objects in a List/Collection/Array when at least one object satisfies a criteria using a single loop
Here is the puzzle I was asked in an interview
There's a List of Employee objects. Update all the objects in the list to be eligibleForHike if at least one employee exists whose salary is less than x; ...
- 109
1
vote
2
answers
126
views
How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?
Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure ...
- 57
0
votes
1
answer
99
views
Time complexity analysis for Searching in a Hash table
I want to analyse the time complexity for Unsuccesful search using probabilistic method in a Hash table where collisions are resolved by chaining through a doubly linked list. And the doubly linked ...
- 103
0
votes
1
answer
32
views
Is it possible to decode an array stored in strings with constraint satisfaction?
I am currently experimenting on compression algorithms, I am using proven algorithms and I am just trying to see if I can make some things more efficient, so I am very sorry if this is a stupid ...
- 23
1
vote
1
answer
24
views
Dynamic Data Structure for Sliding Window of varying size with Predecessor queries
I was wondering if anyone can point me to a data structure that supports the following operations. Goal is to create a data structure $D$ that stores 64-bit integers and provides the following ...
- 103
0
votes
1
answer
44
views
Are linked lists homogenious or heterogenious containers?
I have always assumed that "Linked List" is something in the lines of
...
- 103
0
votes
0
answers
42
views
If you took the permutations of an array and heapified it, will you always get the same heap?
In other words, if I have 10 arrays each with 10 of the same values but scrambled their order and heapified them all, is it possible to have different results?
- 11
1
vote
2
answers
66
views
Algorithm to find if there exists an assignment such that all equality and inequality constraints are satisfied
I have a problem in a Data Structures course I am taking. The question is as follows:
Given a number of variables $x_1,\dots,x_n$ and given $m$ equality and inequality constraints (in total $m$ ...
- 13
0
votes
0
answers
15
views
Data structure for tracking ordered sub-sequences of data [duplicate]
I'm looking for a data structure to help me solve the following problems:
EDIT: This describes a skyline query.
Given a set of points (x,y), find the subset of points where if you order strictly ...
- 101
3
votes
3
answers
755
views
A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity
Why is Solution 1 faster than Solution 2?
The input passed to both solutions:
...
- 131
1
vote
2
answers
479
views
Data structure to determine number of values less than an integer
Given an array of N integers, there may be a need to perform q queries. A query could be like determining the number of values that are less than an integer k. Which data structure could be used to ...
- 19
0
votes
2
answers
123
views
Best data structures to store overlapping intervals?
I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand.
Sample Input-1:
...
0
votes
0
answers
29
views
Slot implementation of LRU cache
Usually LRU cache is implemented with double linked list to fast remove oldest visited, push to front, and move from any place to front; also uses map to fast find element by key.
In 64bit systems ...
- 141
1
vote
1
answer
43
views
Data Structure to Support Max Value of Keys Greater than Given Value
I want to support two operations:
Insert a (key, value) pair into the data structure in $O(\log n)$ time. The key can be assumed to be a unique integer.
Given an integer query value $v$, I want to ...
- 113
1
vote
0
answers
36
views
Algorithm to recreate a Splay tree
Let's say I have some splay tree as following:
I want to recrate the exact same Splay tree using insert(key) method. Is there an algorithm that given some Splay ...
- 231
0
votes
0
answers
16
views
What is the depth of the tree after two operations if the tree uses the "Splay" heuristics?
Further to my previous question, I'm now trying to solve the same question but when the Splay action is involved:
It is given that the current tree is a string of $n$ vertices, and a search operation ...
- 231
0
votes
0
answers
25
views
What is the depth of the tree after two operations if the tree uses the "Move to Root" heuristics?
I'm preparing for my finals in "Advance Algorithms". I'm trying to solve the following question:
It is given that the current tree is a string of $n$ vertices, and a search operation is ...
- 231