We’re rewarding the question askers & reputations are being recalculated! Read more.

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