Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,696
questions
-1
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
0answers
28 views
1
vote
1answer
33 views
k-th smallest element in sliding segment
Consider an array $a[1\ldots n]$ and another array $l = a[0]$ (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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 <...
0
votes
0answers
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 ...
0
votes
0answers
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?
...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-2
votes
1answer
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)$ ...
5
votes
1answer
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 ...
10
votes
3answers
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,...
6
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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
...
2
votes
1answer
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?
...
-1
votes
0answers
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.
...
0
votes
0answers
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 (...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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.
...
-3
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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?
0
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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:
...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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,...
1
vote
0answers
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 ...
2
votes
0answers
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, ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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:
...
0
votes
0answers
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 "...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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}...
2
votes
1answer
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 ...
-2
votes
1answer
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?
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
2answers
123 views
Data structure for shopping cart
I'm working on an e-commerce application where users can add stand-alone products like speaker or they can add a bundle product like desktop that has options like mouse, keyboard etc. All the products ...
0
votes
1answer
39 views
Data structure for efficient group lookup
I need a data structure, which allows efficient queries for 'give me the group of x'.
Let me give you an example:
...
