Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,528
questions
0
votes
1answer
38 views
Is this a misleading or undesirable implementation of a hash map?
I read a C++ implementation of a hash map here.
https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/
Let's say key k1 has a ...
0
votes
0answers
35 views
What is the difference between a Type and an Abstract Type?
In my data structures course we are given definitions for Type and Abstract Type but they confuse me.
A type is a set of values and the operations you can do on them. The set of operations is ...
0
votes
0answers
14 views
Custom building PC [closed]
MacBooks and Chromebooks both have built in antivirus. Is it possible to incorporate that kind of antivirus in a PC custom build? Or do I have to buy mainstream antivirus software?
-1
votes
0answers
34 views
Online algorithm to output the number of good subsegments
Is it possible to do this problem online:
https://codeforces.com/problemset/problem/997/E? All the AC solutions use offline sorting of queries.
Here is the problem statement:
Given a permutation $p$ ...
-2
votes
0answers
34 views
Which statement best describes an Array variable? [closed]
a) Used to represent a group of variables that are of the same data type and that can be referenced using one variable name.
b) Can only be defined in a main method.
c) Not a Data Structure.
d) If ...
4
votes
0answers
86 views
Is there a data structure that can perform range modulo additions and range minimum queries?
It is well-known that the Segment Tree performs range additions and range minimum queries in O(logN) each.
Let each element in the array have value V[i], M[i]. We define a "range modulo add" as the ...
3
votes
1answer
68 views
Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0
Lets consider sequences whose elements are $-1,0,1$.
Subsequence $A[i...j]$ is $good$ if sum of its elements $=0$.
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is $good$.
...
4
votes
1answer
175 views
Search for maximal value smaller than V in an array composed of K linear functions
Sorry for the lack of clarity in the question description.
I have an array composed of length $N$ composed of $K$ linear subarrays. We define a linear subarray as a contiguous subarray of the array $[...
2
votes
1answer
77 views
Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1)
I am struggling with exercise from the old algorithmic exam:
$d$ is const for the whole structure.
Propose a structure for which you can do:
Init(S) //called only 1 time
Insert(x, S):: $ S := S \...
1
vote
1answer
44 views
Find number of awesome substring of a given binary string
A binary string is given to us and we need to find number of awesome substring of that string .Definition of awesome string : A string is awesome if its length is divisible by number of 1's in it.
...
2
votes
0answers
57 views
What's the number of leaves in AVL tree
How can I prove that the number of leaves in a balanced BST is $\Omega (N)$ where $N$ is the number of nodes in the tree?
I tried somehow to prove that an AVL/Fibonacci tree should have $\Omega (N)$ ...
0
votes
1answer
38 views
Usage of stacks and heaps in object-oriented programming. Reasons?
In object oriented programming heaps are used for to store the actual objects. Stacks are used for storing reference-variables to the objects.
What's the concrete reasons for choosing those two ...
0
votes
2answers
60 views
Implement data structure with efficient insert/findKthSmallest operations
I was asked this question by an interviewer. I tried solving it using an array, such that I make sure the array in sorted when I insert. However I don't think this is the best solution. What would be ...
1
vote
1answer
30 views
How to write grammar production rules to describe recursive structures?
I'm trying to describe a data structure by production rules. The structure is recursive; say a list of type $A$ made of elements of type $A$ or $B$.
Writing the grammar, I build this:
$(S \...
2
votes
0answers
17 views
K-nearest along ray in large point cloud
Are there any well-known data structures known that can handle the following (need to scope whether something is possible):
Return the k-closest points to a ray shot through the cloud.
Allows quick ...
1
vote
0answers
34 views
How do I modify Floyd-Warshall to find the shortest path with an odd number of edges?
Given a connected weighted graph $G=(E,V)$, how do I modify Floyd-Warshall to find the shortest path with an odd number of edges?
Floyd-Warshall recurrence
$$ D_{ij}^{k} = min\{ D_{ij}^{k-1}, D_{...
0
votes
1answer
39 views
How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list
How to divide an unsorted list into two equal parts in linear time, where every element in the first part is smaller than every element in the second part
I tried to use QuickSort but in can result ...
0
votes
0answers
17 views
When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for perfmance
When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for performance gain ?
1
vote
1answer
37 views
Splitting a node in B+ tree with odd number of keys
This and several other resources suggest to "Always a node that gets the middle key from bottom splits, should drop one item for a new middle key".
To illustrate with an example.
For 5-way B+-tree,
...
1
vote
0answers
46 views
Branch and scope globally unique identifiers
Say we are working with a Prolog-like system where variables are dynamically created in different branch contexts and scopes, yet these variables are also globally viewable by the system regardless of ...
1
vote
2answers
46 views
Time complexity to sort 100 elements by using selection sort?
What will be time complexity for sorting 100 elements using selection sort answer given is O(1), but selection sort time complexity is O(n^2) in every case so how O(1)?
0
votes
2answers
69 views
is AVL tree is better than heap for sorting purpose?
for sorting n elements what is better to use AVL tree or heap data structure and why? Can someone explain in brief?
0
votes
0answers
47 views
What's the most recent data structure?
I have just discovered the filed of data structure and I am fascinated by it. IS there an encyclopedia of data structures? Or at least do you know any recently constructed data structure that is not ...
1
vote
2answers
72 views
How to solve linear equation with binary tree
I'm working on a school project that takes in a simple linear equation and has to return the value of $x$. The code I have transforms $x + 3 = 3x - 2$ into a binary tree format like so:
...
0
votes
0answers
36 views
Disjoint Set Union-Find Special Case
I was doing reading on weighted quick-union using path compression. I have a clear understanding of why this is $O(1)$ with amortized analysis for union and find operations but do not understand how ...
1
vote
1answer
51 views
O(n) external intersection points?
I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (...
2
votes
2answers
58 views
Data structure to report all axis aligned bounding boxes intersecting an axis aligned query line
I would like to build a Data structure that uses subquadratic space to quickly report a set of AABBs (axis aligned bounding boxes) in 3 dimensional space when it intersects a query line? I am only ...
1
vote
2answers
51 views
Shortest paths from a source in weighted graph with only one negative weighted edge
Of course assuming there aren't any negative cycles.
I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very ...
2
votes
1answer
50 views
Space-efficent storage of a trie as array of integers
I'm trying to efficiently store a list of strings in an array with the following constraints:
All strings consist of 8-bit characters (0..255).
The final trie is static, i.e. once it is built, no ...
1
vote
0answers
43 views
Red-Black tree with index
I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index.
So if I have the function: $\text{insert}(root, value, index)$ it will ...
1
vote
0answers
20 views
For what family of graphs does Dijkstra's algorithm achieve the run-time upper bound
The question is in the title of the post. I am hoping to get some validation regarding my solution.
After some trial and error, my idea is as follows.
Worst case complexity of $\mathcal{O}(E\lg_{}{V}...
1
vote
1answer
54 views
Is there a formal definition of “data structure”?
Data structure is a term that I've heard use I think only somewhat informally in software engineering. Is there a formal definition of it in CS?
1
vote
1answer
31 views
Given a DCEL, how do you identify the unbounded face
I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?.
This correctly identifies all faces, however I'm struggling ...
4
votes
1answer
138 views
Recover permutation from prefix sums, using segment trees?
I encountered the following problem on Codeforces.
An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following ...
3
votes
0answers
111 views
Making an array increasing by modifying elements
I am trying to solve a problem on codeforces. Given an integer array $a_1,\ldots,a_n$, our goal is to find the minimal number of instructions, each of which increments or decrements a single entry, ...
1
vote
1answer
25 views
Does the “dictionary of stacks” ADT have an accepted name?
With a stack, you can push and you can pop. There's also a generalization, let's call it a foo, in which key-value pairs are involved. The idea is that instead of just pushing a value, we push a key-...
3
votes
1answer
45 views
Are all data structures in the von Neumann architecture based on the array, or array-like?
I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
0
votes
1answer
68 views
Complexity of finding 7th smallest element in a min-heap? [duplicate]
I don't know if it's allowed to traverse nodes in a min-heap.
Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus ...
2
votes
0answers
50 views
Efficiently finding all pairs of disjoint sets
Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$.
I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. ...
5
votes
2answers
225 views
checking '<' for two binary numbers in a cnf-formula
I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf:
Lets say n and m are two-digit ...
2
votes
0answers
19 views
Poset data structure to find least element, greater or equal to given
Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$.
Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
2
votes
2answers
35 views
Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
1
vote
0answers
14 views
Where can I find someone that will sit with me and explain the analytics reports from my iPhone and computer? [closed]
This may seem like a dumb question to most people, BUT PLEASE READ THIS!! I AM BEYOND DESPERATE to get rid of a hacker that is digitally stalking me and terrorizing me. I picked your forum because ...
0
votes
1answer
790 views
Difference between Sequential ,Direct and Random acess with their acess time
I'm stuck on a point while reading about these different accessing methods. As per author.
Sequential access
Memory is organized into units of data, called records.Access must be made in a ...
3
votes
0answers
43 views
Forbidden Sequence Dynamic Programming
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
1
vote
1answer
44 views
nested boxes algorithm
I am given a set of 3D boxes {$B_1$, $B_2$...$B_n$} and each box have length, width and height. But these values are interchangeable since I can rotate the box. I need to find out the maximum sequence ...
1
vote
1answer
26 views
Storing $K$ numbers with ordering
Let $S$ be a sequence of $k$ many numbers. The position of the number in the $S$ matters. In the $S$ there are only $j$ many different numbers are there means $S$ contains many duplicates. Position is ...
1
vote
0answers
121 views
Data structure for storing strings
I'm designing a tree data structure to store strings in. One classic solution is prefix tree, but I am looking for a solution that the time to check if the string is in the storage is O(logm*logn) ...
0
votes
1answer
50 views
Perfect Hash Function: How does it cope with lookups outside the set of keys?
I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the ...
1
vote
2answers
151 views
How can I make my algorithm more efficient or Is there a better way to solve the problem
Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you ...
