Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,487
questions
1
vote
1answer
26 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 ...
0
votes
1answer
38 views
Check subset sum for special array
I was trying to solve the following problem.
We are given N and A[0]
...
1
vote
1answer
24 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 ...
1
vote
0answers
36 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) ...
0
votes
1answer
35 views
Perfect Hash Function: How does it cope with lookups outside the set of keys?
I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the ...
1
vote
2answers
138 views
How can I make my algorithm more efficient or Is there a better way to solve the problem
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 ...
0
votes
1answer
81 views
How to answer multiple queries for a tree?
I encountered an interesting problem based on tree-data-structure.
We are given a tree which has N nodes, with 1≤N≤105.
Time starts from second 1 and it continues for q seconds.
At each ...
0
votes
2answers
44 views
Range Query with conditions
Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the ...
-3
votes
1answer
41 views
I want to solve this question for algorithm, please [closed]
Write an algorithm that calculates the monthly payment of a bank loan with
a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of
years to pay the loan, you can ...
0
votes
0answers
15 views
What is the difference between $\ Ω $ , $\ Θ $ , and O , [duplicate]
What are these difference $\ Ω $ , $\ Θ $ and O ?
Why
$\ n^3 + 4n^2 = Ω(n^2) $
But,
$\ n^3 + 4n^2 = O(n^5) $
0
votes
0answers
13 views
Big Oh Notation Complexity [duplicate]
How it can possible
$\ 1/2n^2 -3n = Θ(n^2) $
Why we dont care $\ 3n $ and $\ 1/2 $
0
votes
2answers
82 views
number of permutation with k inversions
We are given two numbers N and K.
N <= 10^9.
K<=min{1000,(N*(N-1))/2}
We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.
If N was <= 10^3. It would ...
2
votes
1answer
56 views
find maximum sum of xors
we are given an Array
Array size <= 10^4 .
0 <= A[i] <= 15
We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
0
votes
0answers
17 views
What are the graph classes which takes logarithmic space in $|V|$ in circuit representation?
The $\text{SCR}$ representation of a graph $G=(V,E)$ is $C_{G}$ id the following conditions hold:
$C_{G}$ is a combinatorial circuit with memory.
$C_{G}$ has two inputs of length $n$ bits.
$C_{G}$ ...
0
votes
1answer
46 views
Why $o(\log n)$ bits instead of $O(\log n)$ bits needed for succinct data structure?
Succinct data structure = succinct representation of data + bits for indexing. Link
Let $S$ be subset of of $\{1,2,\ldots,n\}$ then $\lceil \log (2^n) \rceil + o(\log n )$ bits are needed in ...
2
votes
1answer
37 views
Efficient data structure for matching 3D lines
I'd like to
Store a set of many infinite undirected 3D lines.
Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?"
The incidence-...
1
vote
1answer
59 views
Running time of algorithm (effect of j*j in for loops) - Theta Runtime
In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
j=1
while j*j <= i:
j = j + 1
Since the outer loop ...
1
vote
1answer
64 views
Divide a number in k powers of 2
Example
N = 9 and K=3
4 + 4 + 1 = 9 .
What I have tried.
We can not go on dividing with 2.
We can use unbounded knapsack with array elements from 2^0 to 2^32.
0
votes
0answers
17 views
Updating trading order book between two machines
Let's say you are fetching order book like this
...
5
votes
1answer
110 views
Concatenate multiple integer arrays such that number of inversions in resulting array is minimal
Given N arrays of variable length.
Find a way to concatenate the arrays in such a way that the number of inversions is minimum
An inversion for an array Arr can ...
1
vote
2answers
22 views
How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?
Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such ...
0
votes
1answer
31 views
Unique property of a full binary tree
I read a statement that was unclear to me, and was hoping to get some clarification.
It said that given a full binary tree with $n > 2$ leaves, there exists some internal node such that one third ...
4
votes
0answers
26 views
Data structure for identifying elements while keeping track of relation
I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently:
Add a new element $i$ to $I$.
...
1
vote
2answers
111 views
Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time
A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the ...
0
votes
2answers
44 views
Time complexity for balancing an unbalanced binary tree
The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?
The solution I thought of involved solving using Recursion where for the ...
0
votes
1answer
27 views
Is the tree shown a valid red-black tree?
I have made a red-black tree and I think that it is not valid. Could someone please verify?
As far as I know, in red-black tree we also consider the leaf nodes at the NULLS of the visible leaf nodes ...
3
votes
1answer
67 views
Why is LinkedList useful?
If you implement a stack with a dynamic array-based with LinkedList you need more memory than with a dynamic array, and with dynamic array for insert in amortized cost is O(1), so the advantage of the ...
1
vote
1answer
34 views
How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$
I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a ...
2
votes
0answers
43 views
How to solve following tree problem?
Source of the problem is https://codeforces.com/contest/1152/problem/D . I think i understood the problem , but if possible please explain the problem in simple way and the solution also .I tried very ...
0
votes
0answers
12 views
When to apply a probe sequence when inserting an element to a hash table
So, if we start out with an empty table with M elements. Do we always need to have a specified hash function say $h(x) = x \% 8$ as well as a specific probing sequence to use when inserting a ...
1
vote
3answers
88 views
Why is heap insert O(logN) instead O(n) when you use an array?
I am studying about the arrays vs heap for make a priority queue
For check the heap implementation I am reviewing this code: Heap
, but I have the following question.
Heap is based on array, and ...
0
votes
0answers
29 views
Linked lists with auxiliary data
I'm trying to design a data structure that supports the following operations in $O(1)$ time:
$\operatorname{query}(\ell)$: Yield some auxiliary datum associated with list $\ell$ (just a single ...
0
votes
0answers
33 views
Complexity of Rearranging a Prefix Tree/Alternative Data Structures
Let $S$ be a subset of $[0,1]^l$. Is there some data structure that can represent $S$ and can perform the following operations/queries efficiently*?
$ADD(s \in [0,1]^l)$ - operation which updates $S$ ...
0
votes
1answer
52 views
heap data structure complexity
I'm trying to count running time of build heap in heap sort algorithm
...
0
votes
1answer
28 views
Filler Algorithm
I am curious to know if there is an algorithm that, given an array of decimals and integers, and given an integer, returns a sequence in descending order, composed of those numbers of the input array ...
0
votes
2answers
87 views
Difference between Quick sort, Merge sort and Heap sort
We know all the above-mentioned sorting algorithms take $\mathcal{O}(\mbox{N log N})$. Merge sort and Heap sort algorithms take $\mathcal{O}(\mbox{N log N})$ time in worst-case where Quicksort takes $\...
0
votes
1answer
33 views
Is Binary search tree in 1D?
This post says
Binary Space Partitioning Trees are a
generalization to dimensions > 1 of binary search trees
which indicates the binary search trees lives in 1d space.
Is my understanding right?...
2
votes
2answers
100 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", "...
2
votes
2answers
78 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
1answer
27 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
35 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
23 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
24 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
68 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
65 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 ...
2
votes
1answer
62 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 ...
0
votes
1answer
53 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 ...
1
vote
1answer
53 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
57 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
17 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 ...
