# Questions tagged [data-structures]

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

1,696 questions
Filter by
Sorted by
Tagged with
22 views

### Solution to T(n) = 2T(n/2) + log n

So my recursive equation is T(n) = 2T(n/2) + log n I used the master theorem and I find that a = 2, b =2 and d = 1. which is case 2. So the solution should be O(n^1 log n) which is O(n log n) I looked ...
32 views

### What do you call a data structure containing multiple lists?

I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know ...
28 views

### Product Sum of Special Arrays

Can someone please explain why this is correct: ...
33 views

### k-th smallest element in sliding segment

Consider an array $a[1\ldots n]$ and another array $l = a$ (initial value). At each turn we may add next element to array $l$, or remove first element from array $l$. F.e. after first iteration it ...
22 views

### How isolate the last bit work on teory Binary Indexed Trees

I'm learning about the Binary Indexed Trees, and I understand how it works, but I'm interested in the theory that there is behind! In particular, I don't understand what is meant the following ...
23 views

### What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?

I'm learning some Data Structures and I cannot figure out the difference between the Balanced BST and the AVL Tree. From my understanding, an AVL tree is a balanced tree with the height difference <...
24 views

### sum selected nodes of a set in $\log n$ time

Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation ...
29 views

### The following time complexity is right for the given algorirthm

Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ...
25 views

### Approach / data structure to wait for N tasks to complete in arbitrary order

My system needs to wait for the completion of N tasks and terminate when all are completed. The work items are passed in as an immutable array and the execution of these items are handled externally ...
22 views

### LOUDS Succinct Tree Representation

I am trying to make my Trie tree structure as compact as possible. While searching about this I came across to "Level order Unary Degree Sequence " i.e. LOUDS representations using bit ...
138 views

### maximum spanning tree in a complete graph

Given a complete graph how do I find maximum weight spanning tree. where $weight(u, v) = \sum_{i=1}^{k} |w_{i,u} - w_{i,v}|$ assuming $k \lt 7$ and $n \le 500000$. $n$ number of nodes $weight(u,v)$ ...
78 views

### Word Wrap Algorithm and Datastructure that supports modifications of text and window size

I'm trying to find or create an algorithm for efficiently displaying text that is word wrapped. All the algorithms (if they an even be called that) for word wrapping presume a given lot of text and ...
2k views

### Why is the inverted index called so and not simply index?

In my notes is represented like this: From wikipedia: In computer science, an inverted index (also referred to as a postings file or inverted file) is a database index storing a mapping from content,...
64 views

### Closest point in embedded simplicial complex

Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded ...
25 views

### Intuition behind the Reversal Algorithm [ Rotation of Array ]

I know that the below program uses Reversal algorithm to rotate an array's elements to k positions to the right. But how does the Reversal algorithm works? It seems kinda magic to see. Can somebody ...
21 views

### Range sum query - tree representation efficiency

I was reading about possible solutions to the well known problem: Given array A with length N create a structure that enables ...
57 views

### What does it mean that B-tree leaves carry no information?

According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.". What does it mean that they carry no information? ...
50 views

### Logarithmic Time — O(log n) in Python

Hi , I am new to Data Structure and trying to get some clarifications. Following shows an example Logarithmic Time — O(log n) in Python. ...
15 views

### Various implementations of adjacency list representation of a Graph

Just started learning about graph and it's various representations (matrix and adjacency list). Now I found that the adjacency list representation can be implemented in various ways: Array of arrays (...
36 views

### Why does the formula floor((i-1)/2) find the parent node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with parent ...
37 views

### Data structure that allows accessing elements by index and delete them in O(logn)

I need to take an kth index element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would ...
15 views

### How to convert recursive language grammar tree into automaton for optimal parsing?

So I have a definition of a sort of grammar for a programming language. Some aspects are recursive (like nesting function definitions), other parts of it are just simple non-recursive trees. ...
53 views

### Subset sum problem with a complication

I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them? The size of my list can be ...
44 views

### Does there exist standardized language-agnostic data structure notation?

I wonder if there exists language-agnostic data structure notation. Preferably a standard, allowing to describe data structures and basic data types. e.g. something like a subset of ...
56 views

### Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
32 views

### Finding a median in logn from a list of distinct integers

I got an interview question asking for data structure and algorithm. The question is: Given we have unlimited space, We need to insert a key in $O(logn)$ and find a median in $O(logn)$. Min heap/ Max ...
25 views

### Basic Binary search tree query

Inorder traversal of BST is always sorted.But can we say Binary tree is BST if and only if inorder is sorted?I mean if inorder is sorted,can we conclude it is always BST?
30 views

### Algorithm to find out if a set contains two number with sum in the same set using a blackbox function

I need help with the following question - There is a set S of n integers. Given a black box which returns three integers a,b,c in S such that a+b+c = 0 if they exist. One needs to devise an algorithm ...
80 views

### Binary string satisfying several constraints

I'm trying to solve this problem, but without success. Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several ...
141 views

### Find the length of the longest subarray having sum greater than k

I tried to solve this problem but could not do it better than $O(n^2)$. My Algorithm: ...
45 views

### CSES Range Query Question: Index Compression and Updates [closed]

I'm trying to solve this problem: https://cses.fi/problemset/task/1144/ Given an array of up to 200000 elements, my task is to process up to ...
62 views

### Remove vertices until no edges are left

Given an undirected graph G(V,E), find the minimum number of vertices to remove so that the Edge Set of the graph becomes empty. In other words: If we remove one vertex we remove that vertex along ...
47 views

### Potential Example of an algorithm failure

I was looking an algorithm to solve a problem of finding whether and array contains a quadruple with sum = k,(k is input) mentioned at GeeksforGeeks. In one solution the approach mentioned is below,...
22 views

### Range Query Question: Removing Items from a List

My task is to input a given list of size N, then process N queries that remove an item from the list and then print it to the ...
65 views

### Minimum number of nodes to select such that every node is at most k nodes away

I received this problem on an exam a few months ago, and have kept thinking about how to solve it with no luck. Given a binary tree where each node in the tree can either be selected or unselected, ...
22 views

### Data Structures for BST where size uniquely determines shape

There are several data structures in which the number of elements uniquely determines the shape. Examples would be binary heaps, arrays, lists, Braun trees, and Merkle mountain ranges. Are there any ...
28 views

### Definition of 'Record'

Given the definition of 'record': "a collection of field values for a given entity", is this a set of field values for ALL the fields of the entity, or only one particular field [so that you ...
54 views

### Interview q: Small possible length of stick from an array of stick lengths

I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here ...
55 views

### Container with findNthSmallest in O(1)

Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This container should support the following operations: ...
22 views

### Are data storage efficiency and volatility directly correlated?

It seems intuitive to me that less efficient data storage methods are also less susceptible to degradation over time. For instance, the string "ABC" can also be represented as "...
57 views

### Algorithm for Estimating Number of Unique Monthly Visitors

Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as ...
8 views

### Why are these BVH split heuristic formulas different?

I've been doing some research into changing the split heuristic I use for a work project comprised of a BVH binary tree. The heuristic I currently use is centroid median as described here, but I seek ...
24 views

### Computing childrens of ith node of a d-ary tree

Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n). The formula for indices of children of node no. i is given as: {(1-i)d+2, ... , min{n,(1-i)d+d+1}...
61 views

### Difficulty in few steps in proof of “Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$”assuming union by rank, path compression

I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as ...
421 views

### How to calculate the minimum price required to buy all the stones?

I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)). Can someone please help me out to solve this faster?
36 views

### Is there any rich problems that can be solved using several algorithm techniques?

I am wondering if there are some particularly rich problems that have a large intersection with algorithms and data structures. An example could be the travelling salesman problem. Any other ...
47 views

### Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A: A is the sum of every part of a rectangle covered by another. So if two rectangle ...
29 views

### Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...