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