Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,582
questions
0
votes
0answers
13 views
What Is The Best Data Structure To Implement Min Priority Queue For Dikstra's Shortest Path Algorithm?
Dikstra's shortest path algorithm uses a min-priority queue for getting the minimum vertex at every iteration. What I want to know is the best data structure to use for this algorithm. From my ...
1
vote
0answers
14 views
Modify Fibonacci Heap to Have a Linear Chain of Marked/Unmarked Nodes Only
In CLRS book there is an exercise (19.4-2), the aim of which is to create a linear chain of nodes by a sequence of Fibonacci-Heap operations. I have solved the problem by recursively making a union ...
0
votes
0answers
20 views
Please explain the algorithm for finding bridges in graph?
let, low[] and disc[] be two 1D arrays
disc[i] stores the discovery time of node[I]
low[i] stores the lowest value between disc[i] and discovery time of children of node[i]
I'm curious that what is ...
0
votes
0answers
15 views
What are some unusual or creative implementations of ADTs you've seen?
While learning about ADTs in a data structures course, we learned that the List ADT is most commonly implemented using linked nodes or arrays. Are there any other fundamentally different and unusual ...
1
vote
0answers
26 views
Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?
When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure.
Using Fibonacci-heaps instead, are we not able to achieve a ...
0
votes
0answers
17 views
How to generate unique keys for different two dimensional matrices having different sizes?
No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
0
votes
1answer
49 views
Amortized value of dequeue with potential function
A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty.
Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1)....
0
votes
0answers
20 views
Hashfunction for unique character distributions
The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of ...
1
vote
0answers
20 views
Determining Range of Current Node in Segment Tree
I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
-1
votes
0answers
20 views
Develop an algorithm [closed]
I participated in a programming competition at my University. I solved all the questions except this one. Now I am practicing this question to improve my skills. But I can't figure out the algorithm. ...
1
vote
1answer
21 views
How many times in this pseudocode is the function F called?
For this question, I thought function F called twice but it called three times. Are those three functions were called? F(N), F(K) and f(N-1)?
How many times in this pseudocode is the function F ...
0
votes
2answers
12 views
The best approach to search for closest object in hash map holding arraylist without changing data structure
Imagine the game handled server sided, don't think of a visual problem.
Given a game 2D map, with size of n * n.
The game contains objects (such as door, wall, a table).
Each tile position (x,y) can ...
1
vote
1answer
15 views
Space-efficient data structure for analytical querying of multiple branching evolutions of a dataset
Problem Description
I have a data state space: a set of data sets, each of which can be modelled as a collection of arbitrary key-value pairs. These data sets are each a branch of evolution of a ...
2
votes
0answers
54 views
Data structure to query intersection of a line and a set of line segments
We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries:
Given a query line $l$, report how many line segments in $S$ does it intersect.
It ...
0
votes
2answers
38 views
Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?
If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly).
Intuitively, it may feel it is, because it is like the reverse of build it up.
(Building a ...
0
votes
3answers
505 views
Why the 127 encodings of ASCII needed to be extended to 256?
As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages".
I still ...
1
vote
0answers
52 views
Should a prefix tree (trie) node store only a single character or a string?
I've just implemented a Trie and I thought it would be a good idea to store strings in the Trie nodes in contrast to storing single characters.
Storing strings is for sure more space-efficient and ...
0
votes
0answers
31 views
Is there a faster than O(n^2) solution for Box stacking problem?
Is there a faster than O(n^2) solution for the Box stacking problem?
1
vote
1answer
18 views
Data structure for equivalence classes
Let $E$ be an equivalence relation defined over a set $S$. The access to $E$ is only via queries of the form $M(s_1,s_2) = 1$ if $s_1$ and $s_2$ are in the same class and $0$ otherwise. Computing $M$ ...
1
vote
0answers
53 views
Range Minimum Query with Updating values
I was wondering if the following problem can be solved in asymptotically better time than$ \ O(n \log n)$.
Suppose you have an array of integers $a_1,a_2,a_3,\ldots,a_i,\ldots,a_n$ where initially ...
1
vote
0answers
12 views
Data Structure for high dimensional data with nullable coordinates
Are there alternatives to uniform grid spatial partitioning when considering data structures for data with nullable or missing coordinate values?
For example with uniform grid spatial partitioning ...
0
votes
1answer
28 views
For what data structures is jump search practically useful?
Jump search is a search algorithm for sorted lists which runs in $O(\sqrt n)$ time, but has the advantage of only making backwards steps at the end (and given the ability to make arbitrarily long ...
1
vote
0answers
38 views
In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?
See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time ...
1
vote
1answer
24 views
Universal hashing - insert / search / delete
I don't understand the highlighted text below in CLRS 3rd Ed.:
I'm not sure I even understand what the sentence is trying to say. For example:
What do they mean by "... operations containing $\...
0
votes
1answer
24 views
Priority Queue Using Stack
Can one build a priority queue using stacks, such that the priority queue has the same complexity for each operation.
Could it be done? If so how? If not what is the best solution that can be done?
...
2
votes
1answer
46 views
What is the point of the “check” array in a triple-array trie?
I am currently reading the definition of a triple-array trie as described here.
More precisely, I am trying to understand the nature of the three arrays:
base. Each element in base corresponds ...
1
vote
2answers
48 views
What is the name of the data structure that is a tree on the backend but has a list like API?
I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a ...
0
votes
2answers
71 views
How to check equality between any two 2-dimensional arrays (dense matrices) with time complexity less than O(n*m)?
Here, n = no. of rows and m = no. of columns
Suppose, there are three matrices - A[3][2] : {{1,2},{3,4},{5,6}} ;
B[3][2] : {{1,2},{3,4},{5,6}} ;
C[3][2] : {{2,1},{3,4},{5,6}} .
Here A=B , A!=C and B!...
0
votes
0answers
15 views
Need explanation of Node Structure, Search, Insertion and Deletion operations in R-Trees?
I am finding it hard to visually understand the R-Tree concepts and its primitive operations, Search, Insert and Delete(which are applicable to any type of tree). I am unable to find good sources for ...
0
votes
0answers
12 views
Data structure for revising ordering given a (largely) ordered stream of data
I have an input stream of timestamped data that is largely sorted in ascending order by timestamp. There are occasionally out-of-order elements, at which point I need to do each of the following:
...
0
votes
0answers
10 views
Data Model or Data Structure for Stored Procedures in Databases
I know that Relational Algebra is the goto data model for storing information related to SQL queries.
I am however yet to find a standard data model that can encapsulate constructs of stored ...
2
votes
1answer
42 views
Numerical Accuracy & Sorting Algorithms?
Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/...
0
votes
0answers
21 views
Runtime of tree sort algorithm confusion
Can anyone explain to me why the average runtime complexity of the program here - https://www.geeksforgeeks.org/tree-sort/ - is nlogn and not n^2logn? Similarly, why is the worst case time complexity ...
1
vote
0answers
25 views
relationship between binary numbers and binomial heaps
I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and ...
0
votes
1answer
47 views
Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing
I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, ...
4
votes
1answer
145 views
Interview Question with Arrays and Consecutive Subintervals
I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it..
The question is:
"An array of $n$ integers is ...
-1
votes
1answer
34 views
Finding the count of 0's bounded by all 1's
Given N * M 2-D matrix find out all the 0's which are completely bounded by the all 1's. ( This is not any online platform question ) (This problem statement I faced during an interview).
Sub-matrix ...
0
votes
1answer
37 views
Need help with adding elements to hashtable with linear probing
Here is an example problem which I have having trouble figuring out. The red text is the answer.
I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
0
votes
0answers
36 views
Efficient way to convert d-ary to binary heap
Even though a general-purpose algorithm is desired, I'm specifically interested in the case that d is 4 (convert 4-ary to 2-ary).
0
votes
1answer
46 views
How can i solve a recursion equation with square root using recursion tree method?
$T(n) = \sqrt{n}T(\frac{n}{2}) + \sqrt{n}$
I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.
I just don't want to ...
2
votes
1answer
53 views
Static Perfect Hashing - FKS
I am trying to understand perfect hashing aka FKS, but I have a few questions.
From my understanding, perfect hashing is a two level hashing in which you take a hash function from a universal family ...
1
vote
1answer
27 views
What is the most effective way to learn, understand, and utilize an algorithm?
In order to keep my interviewing skills sharp, I solve one algorithm/data-structure problem every day, from sites like Leetcode or HackerRank.
If I am not able to solve it after 45 minutes or so, I ...
2
votes
0answers
58 views
Counting triplets from three arrays satisfying the equation x^2 = yz
Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of ...
0
votes
1answer
63 views
Sorting almost sorted array
Encountered this question but I couldn't solve with the complexity they solved it:
Suppose I have an array that the first and last $\sqrt[\leftroot{-2}\uproot{2}]{n} $ elements has $\frac{n}{5}$ ...
1
vote
1answer
48 views
How to speed up finding a subset of a given set?
Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data?
For example, let's say that I have a collection of sets:
...
0
votes
1answer
74 views
Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes
I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary ...
2
votes
2answers
69 views
Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)
Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the ...
1
vote
0answers
53 views
Is the internal structure of a red-black-tree dependent on the insertion order?
Is the internal structure of a red-black tree (which nodes are red or black, the disposition of the branches, the location of each value...) dependent on the order in which the elements were inserted? ...
0
votes
2answers
45 views
Approach for algorithm to find closest 3-D object in a list of many similar objects to a given test case
Lets say I have a list of many (10s of thousands - millions) objects, and each of these objects has a given number of 3-D vertices (my current implementation uses 8 vertices each, but this number can ...
1
vote
1answer
113 views
Independence of order of insertion hashtable with open addressing
I'm taking a data-structure class, and the lecturer made the following assertion:
the number of attempts needed to insert n keys in a hash table with linear probing is independent of their order.
...
