Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,505
questions
0
votes
0answers
23 views
Red-Black tree with index
I want to create a Red-Black Tree, with 2 values, (index, value) and I want to insert into the RB_tree based on the index.
So if I have the function: $\text{insert}(root, value, index)$ it will ...
1
vote
0answers
14 views
For what family of graphs does Dijkstra's algorithm achieve the run-time upper bound
The question is in the title of the post. I am hoping to get some validation regarding my solution.
After some trial and error, my idea is as follows.
Worst case complexity of $\mathcal{O}(E\lg_{}{V}...
-1
votes
0answers
19 views
Doubt in Expected number of probes in successful seach in open address hashing
My attempt:
I need to find exected number of probes in case of successful search. I am assuming, n elements and m slots in hash table
E(# of probes) = average of {1st probe success , 2nd probe ...
0
votes
0answers
11 views
Need to understand about Splunk search algorithms [closed]
I am not much comfortable with DS & ALGO. I need to know which is the best algorithm/Data Structure to use in the file content search scenario. I hope nowadays most of them heard about Splunk's ...
1
vote
1answer
49 views
Is there a formal definition of “data structure”?
Data structure is a term that I've heard use I think only somewhat informally in software engineering. Is there a formal definition of it in CS?
1
vote
1answer
26 views
Given a DCEL, how do you identify the unbounded face
I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?.
This correctly identifies all faces, however I'm struggling ...
4
votes
1answer
101 views
Recover permutation from prefix sums, using segment trees?
I encountered the following problem on Codeforces.
An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following ...
1
vote
1answer
21 views
Does the “dictionary of stacks” ADT have an accepted name?
With a stack, you can push and you can pop. There's also a generalization, let's call it a foo, in which key-value pairs are involved. The idea is that instead of just pushing a value, we push a key-...
3
votes
1answer
42 views
Are all data structures in the von Neumann architecture based on the array, or array-like?
I am an old Pythonista now learning C and how various data structures and types are implemented, such as binary trees and hash tables. Learning about the latter, leads me understand that the hash ...
0
votes
1answer
46 views
Complexity of finding 7th smallest element in a min-heap? [duplicate]
I don't know if it's allowed to traverse nodes in a min-heap.
Because, if traversal is allowed then for finding $7^{th}$ smallest element, only a constant number of nodes need to be checked, thus ...
2
votes
0answers
47 views
Efficiently finding all pairs of disjoint sets
Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$.
I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. ...
5
votes
2answers
137 views
checking '<' for two binary numbers in a cnf-formula
I want to check whether a arbitrary binary number is less or equal to another binary number in a cnf-formula. I can already construct a formula, which is not in cnf:
Lets say n and m are two-digit ...
2
votes
0answers
18 views
Poset data structure to find least element, greater or equal to given
Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$.
Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
2
votes
1answer
23 views
Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words ...
1
vote
0answers
13 views
Where can I find someone that will sit with me and explain the analytics reports from my iPhone and computer? [closed]
This may seem like a dumb question to most people, BUT PLEASE READ THIS!! I AM BEYOND DESPERATE to get rid of a hacker that is digitally stalking me and terrorizing me. I picked your forum because ...
0
votes
1answer
52 views
Difference between Sequential ,Direct and Random acess with their acess time
I'm stuck on a point while reading about these different accessing methods. As per author.
Sequential access
Memory is organized into units of data, called records.Access must be made in a ...
3
votes
0answers
42 views
Forbidden Sequence Dynamic Programming
Given a finite set $\Omega$, I have the following problem. Say there is a list of forbidden subsequences $F \subset \Omega \cup \Omega^2 \cup \Omega^3 \dots \Omega^\infty$, while we do not know the ...
1
vote
1answer
41 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
51 views
Check subset sum for special array [on hold]
I was trying to solve the following problem.
We are given N and A[0]
...
1
vote
1answer
26 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
53 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
46 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
146 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
92 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
47 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
46 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
88 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 ...
0
votes
2answers
36 views
inserting into min heap
These are the instructions I been given :
What does the array look like at each step when inserting "2" into the
following min-heap?
Give your answer as comma-separated numbers, with a ...
2
votes
1answer
61 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
18 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
39 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
64 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
19 views
Updating trading order book between two machines
Let's say you are fetching order book like this
...
5
votes
1answer
127 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
24 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
32 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
115 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
93 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
32 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
68 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
47 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
47 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
134 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
30 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 ...
