Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,505
questions
-1
votes
0answers
21 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
27 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
15 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}...
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]
...
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 ...
2
votes
1answer
1k views
Building heaps and heapsort using linked list
I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list.
One of the answers ...
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 ...
0
votes
2answers
37 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 ...
3
votes
2answers
226 views
The origin of list data structure
Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
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?
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 ...
3
votes
1answer
76 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
38 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 ...
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 ...
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 \}$. ...
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-...
Gilles 'SO- stop being evil'
37.2k7 gold badges100 silver badges166 bronze badges
4
votes
2answers
163 views
If a min heap of [n] is stored into an array, what are the minimum and maximum values for an element at a given index?
If we store a min heap of $n$ elements, $\color{Blue}{[1,2, \dots n]}$ into an array, then what can be minimum value present at any index $i$ and maximum value present at any index $i$. (elements are ...
3
votes
1answer
43 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 ...
5
votes
1answer
509 views
Data structure for handling intervals
I am trying to create a data structure for handling the subsets of the real line of the form $[x,y)$. That is, suppose $X \subseteq \mathbb{R}$ and the data structure supports two types of operations: ...
0
votes
2answers
181 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 $\...
2
votes
2answers
74 views
What exactly state is in Model Checking
So I finally realized the difference between transition systems and automata, and now am closer to understanding Model Checking. One of the last pieces is understanding what exactly "state" is in ...
-1
votes
2answers
5k views
what is the advantage of using threaded trees?
Since a binary tree with $N$ nodes has $N+1$ NULL pointers (across leaves), half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a NULL left ...
5
votes
2answers
138 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 ...
4
votes
1answer
48 views
How do 2-3 FingerTrees generalize to bigger branching factors?
FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
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 ...
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 ...
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
118 views
How to delete an element from a B-tree
There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree.
For example, given the following tree, how would we delete 26 and ...
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
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
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 $
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 ...
2
votes
2answers
121 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
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}$ ...
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
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 ...
7
votes
3answers
14k views
What is “rank” in a binary search tree and how can it be useful?
I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me.
What I have ...
92
votes
5answers
105k views
What's the difference between a binary search tree and a binary heap?
These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
0
votes
1answer
53 views
heap data structure complexity
I'm trying to count running time of build heap in heap sort algorithm
...
2
votes
2answers
37 views
Name for type of actions that only care for outcome
There is a definition for kind of actions that only care for outcome.
Classic example for such an action is remove from ...
