Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,457
questions
0
votes
1answer
26 views
Finding the last substring in lexicographical order in O(n) time
Given a string s, return the last substring of s in lexicographical
order.
Example 1:
Input: "abab" Output: "bab" Explanation: The substrings are ["a",
"ab", "aba", "abab", "b", "ba", "...
-1
votes
0answers
27 views
Linked List implementation with Priority Queue [on hold]
If priority queue can implement a stack, why a linked list cannot implement with priority queue??
1
vote
1answer
20 views
What is the meaning of uniform distribution of elements in an array?
I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
0
votes
0answers
20 views
Disjoint Set Connected Components With Weighted Graph
I have been trying to solve this HackerRank problem (link).
The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
2
votes
0answers
29 views
Data structure & algorithms for super-interval queries on intervals with small integer ends
I would like to have an online data structure that supports inserting an interval, and given a query interval $I_q=[l_q,h_q]$ answer if some interval of the data structure is contained in $I_q$, i.e. ...
0
votes
0answers
15 views
Number of distinct BFS, DFS trees in a complete graph
What is the number of distinct BFS, DFS in a complete graph?
My approach is like this-->
For DFS take a node, we have (n-1) possible tree edges, next we have all possible (n-2) tree edges,..........
1
vote
0answers
22 views
Parallel deletion and traversal in a lock free linked list
I'm unsure about the safety of deletion in a linked list. I've seen the issue posed by a parallel insertion and deletion (resulting in the loss of the insertion) and proposed solutions to that problem....
4
votes
1answer
35 views
Min Fibonacci Heap - increase key
I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
0
votes
2answers
64 views
Constructing a directed graph for O(1) queries
This question appeared in an undergrad data structures final. The details are sound.
I need help to design a data structure for a directed graph with the following properties:
Initialization should ...
1
vote
0answers
39 views
Algorithm to save state of array as it changes
There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be ...
-1
votes
0answers
21 views
smallest subset with given sum
How to find the smallest subset with a given sum?
All elements are integers.
I have an array of integers and I want to find a given sum with the least number of
element possible
with both the ...
-1
votes
0answers
13 views
How to select M max Sum from N stack
We are given N stacks of variable length. We need to choose M element such that sum is maximum.
example
3 3
stack a)
1 2 200
stack b)
5 10 7
stack c)
4 6
the answer will be 1+2+200 = 203 .
1
vote
1answer
41 views
How to count all integers less than a given integer and having two contigous digits as $y$?
Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
0
votes
0answers
29 views
Data Structure for applying transformations upon universe of tuples
Problem
I want a data structure which describes a universe of tuples all of length $n$, $U$. In $U$ we associate each $tuple$ with a non-negative value, which we will denote as $U.count(tuple)$. If $...
1
vote
1answer
43 views
How to cover given entries in a matrix with minimum number of rows and columns?
We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates.
example
0 0 1 0
0 1 0 1
0 0 1 0
0 0 1 0
...
2
votes
1answer
49 views
Range of each building in array
I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, ...
1
vote
0answers
12 views
Linear probing and tabulation hashing
I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup [1] because I want to adapt the proof of the constant time complexity of linear probing for ...
1
vote
1answer
47 views
Number of nodes in Van-Emde-Boas tree of universe size u?
The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level.
The height of the tree is $h = \lg \lg(u)$ ...
-1
votes
0answers
6 views
Question about Excel Data Analysis [migrated]
I have been working on this project in excel and have been trying to come up with a solution for a very long time with no results.
What i want to know is that, lets say I have 4 rows in 2 columns as ...
1
vote
0answers
25 views
How can we find number of triangles in a given undirected graph? [closed]
If we assume we have n triangles in a given graph. How can we find the n triangles in O(n) time?
And we also have to add and remove edges in O(log k) when k=|v|
0
votes
0answers
22 views
What does W1 and W2-hardness imply?
Is there any simple definition to understand W1-hardness $\&$ W2- hardness in complexity theory? What I understood, that is the following: Let $\Pi$ be a decision problem with parameter $k$, then $...
-1
votes
1answer
47 views
Is the following a AVL tree? [closed]
I have a tree as
Is it an AVL tree? it seems to balanced for me.
3
votes
1answer
60 views
how to solve simultaneous equation with O(n)
Does someone know how to solve the below?
Assume that the array $A$ is already sorted.
And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that
$A[i] + ...
1
vote
1answer
34 views
Amortized analysis - increment in ternary counter [closed]
What is the amortized analysis of increment action in a ternary counter that is initialized to 0?
1
vote
0answers
37 views
Minimize sum of guesses to win lottery [closed]
Ten boxes are given with $a_1,a_2,a_3,a_4,a_5 ......a_{10}$ number of balls in them respectively .These boxes are randomly ordered but $a_1,a_2 .....a_{10}$ is told.We can arbitrary select a box and ...
2
votes
2answers
28 views
Randomly built binary search trees
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:
The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.
We define "...
0
votes
0answers
9 views
How would you generate files with several different rules?
Okay, the title is kind of cryptic because I'm lacking terminology (part of the problem).
Situation
Let's say you want to generate data corresponding to one specific, standardized paper document. ...
3
votes
1answer
54 views
Returning sorted lowest k elements in a binary heap
Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end?
The ...
0
votes
0answers
47 views
Which of the following data structures would support sub-linear (insertion, max and min lookups)
Min-heap
Max-heap
B-Tree
AVL tree
It's understandable that an AVL tree is a self balancing binary search tree and will maintain logarithmic operations but so would a B-Tree and thus can as well ...
3
votes
0answers
142 views
Algorithm for answering queries of the type “largest interval contained in the given interval”
I have been wondering over the following problem:
Given a set $S$ of intervals on the number line. We can do two operations on them:
Add a new interval $[l_i,r_i]$ to $S$
Given an interval $[l_j, ...
0
votes
0answers
25 views
Data structure to know if something was calculated
There's the typical interview question about how to create a distributed and scalable URL shortener.
One of the issues is to know if a URL was shortened already or not. There's a special data ...
2
votes
1answer
167 views
Are all foldable data structures also recursive?
I was checking what Wikipedia has to say on reduce. It says:
In functional programming, fold (also termed reduce, accumulate,
aggregate, compress, or inject) refers to a family of higher-order
...
0
votes
1answer
48 views
How MO'S algorithm with update query works?
MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing ...
1
vote
1answer
20 views
What is the index of the leftest child of node in a k-nery heap?
Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap?
All questions regarding my problem I ...
2
votes
1answer
92 views
Generate all permutations of 1 to n with i stacks
Assume we have i stacks. the possible actions are:
push to first stack form input
pop from stack i and push it to stack i+1
pop from last stack to output
If we have numbers of 1 to n starting from 1 ...
1
vote
1answer
48 views
Given n standard C++ STL maps, can I merge them? [closed]
I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick.
For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}}
Then the ...
1
vote
1answer
46 views
Shortest path in a incomplete graph
I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
0
votes
0answers
45 views
On the same group data strcture
In a particular school, $n$ students are taught, and we are given a list of interrelations between students.
The teacher asks the students to divide into a maximum number of groups (on his part, ...
5
votes
1answer
264 views
Data structure for selection of K elements and taking sum
The problem:
We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times:
We can select exactly $Z$ ...
0
votes
0answers
28 views
Choosing algorithms and/or data structures at runtime based on input characteristics
I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
1
vote
2answers
41 views
Check if two separate ranges have some number in common
We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there ...
3
votes
2answers
170 views
Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
0
votes
1answer
38 views
Best known (state of science) time complexity of an array access problem
Consider an Array $A$ with $n$ values and the following operations:
get(i): Returns the value of $A[i]$
insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the ...
2
votes
3answers
377 views
Do height-balanced binary trees have logarithmic depth?
A family of binary trees is called balanced if for every tree $t$ in the family the height of $t$ is $O( \log n)$.
Given a family of trees such that for every tree $t$ in the family, for every node $...
2
votes
0answers
18 views
Nested dissection vs kd-tree
Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional ...
1
vote
1answer
20 views
Adding an ordered into a relationship without violating the functional dependencies
Assuming that we have the relationship $R(A,B,C,D)$, the tuple $(W,X,Y,NULL)$ and the following functional dependencies:
$$A \to C$$
$$A \to B,D$$
is it possible to insert a tuple with $NULL$ values,...
1
vote
1answer
25 views
Find candidate keys given functional dependencies
In my database class we practiced how to find the candidate keys, given the functional dependencies. However they were easy examples, based on a single attribute being functionally dependent on a ...
1
vote
1answer
65 views
How to find highest normal form of a relation, given its functional dependencies
Let's say that I have a relational model, defined as:
$$X(A,B,C,D,E,F,G)$$ with the functional dependencies:
$$f_1: \{A,B,C\} \to \{D,E,F,G\}$$
$$f_2: \{A,B\} \to \{C\}$$
Using this information I ...
0
votes
0answers
17 views
Need an optimized way to handle combination of entities to improve performance
So, I am working on a feature in a web application. The problem is like this-
I have four different entities. Let's say those are - Item1, ...
0
votes
0answers
21 views
Do parent pointers affect path-copying in a persistent binary tree?
I am familiar with the concept of path-copying in the context of binary trees to achieve persistent modifications, but I am unsure if the inclusion of parent pointers has any effect on the complexity. ...
