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
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 ...