# Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

1,528 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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?
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$ ...
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 ...
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 ...
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$. ...
175 views

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. ...
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)$ ...
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 ...
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 ...
30 views

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?
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 ...
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 ...
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, ...
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-...
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 ...
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 ...
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 \}$. ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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 ...