Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,916
questions
0
votes
0answers
9 views
2D segment tree query time complexity
These sources cp-algorithms and geeksforgeeks
state that query complexity (for example, submatrix sum) of 2-D segment tree is O(logN * logM), because
it first descends the tree in the first ...
0
votes
0answers
13 views
How to efficiently see if a value is in a set
I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
0
votes
0answers
10 views
Split-Ordered Lists: Lock-Free Extensible Hash Tables
I am reading the research paper "Split-Ordered Lists: Lock-Free Extensible Hash Tables" by Nir Shavit and Ori Shalev.
https://dl.acm.org/doi/10.1145/1147954.1147958
I was just wandering if ...
3
votes
1answer
37 views
Shortest possible path between closest pair of specific nodes in a maze
Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $O(MN)$ time? (M rows, N cols). $O(...
4
votes
0answers
74 views
Fast and compact data structure for dynamic graphs
Assume a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ is represented as follows in central memory:
an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[...
0
votes
0answers
17 views
Treap use cases
I am trying to develop an appreciation for the treap data structure; my goal is not to implement one but use boost when the problem calls for this construct.
Some use cases, or small problems showing ...
0
votes
1answer
22 views
Complexity of insertion into a linked list, single vs double
At https://www.javatpoint.com/singly-linked-list-vs-doubly-linked-list, it says:
In a singly linked list, the time complexity for inserting and
deleting an element from the list is O(n).
And:
In a ...
1
vote
1answer
15 views
Linear having two different connotations?
When we discuss data structures, linear typically means that we can iterate through the data sequentially. For example, a linked list or array can fall into this category while a binary search tree is ...
0
votes
0answers
17 views
Looking for a reference for "structured programming for data structures"
In a talk by Tony Hoare, he said something interesting and I'm looking for more reading on the topic
minute 57:
"Languages don't recognize the different structuring principles that are being ...
0
votes
0answers
28 views
Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?
Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap?
...
0
votes
1answer
22 views
Turing machine accepting square
I'm trying to figure out following assignment and I could use your help, because I'm stuck.
Task:
Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. ...
1
vote
1answer
54 views
Algorithm to find shortest distance from source to all other vertices of graph in O(m)?
My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
2
votes
2answers
60 views
If both could be implemented with the other, what are the differences between priority queues and binary heaps?
I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap.
This seems strange to me as ...
12
votes
3answers
3k views
Data structure for fast insertion and fast random element removal
I'm looking for a data structure that supports the following operations:
add(elem) - Add an element to the data structure.
remove_random() - Remove and return a random element.
The best I got so far ...
0
votes
1answer
23 views
Hashing using chaining
In resolving collisions while hashing by chaining , if we store keys in the list in sorted manner, will we obtain any substantial performance in successful searches , insertion, deletion? What would ...
3
votes
1answer
38 views
A question about hash problems in CLRS book
Consider the following problem 11.2-6 from CLRS book:
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
0
votes
1answer
32 views
How to make a Huffman tree
I'm trying to make a huffman tree based off of some words. I have the frequencies of each character stored using a hashtable, but i need to then make a minheap structure in order to then be able to ...
1
vote
0answers
19 views
Prove that you can design any digital circuit with only NAND gate or only NOR gate
I have read that NAND gate and NOR gate are called universal gates... but i cannot find a rigorous proof that any circuit can be designed by these two gates only.
1
vote
1answer
32 views
A hash function for a 2D hash table with a scattering property?
I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
0
votes
0answers
16 views
Infix To Postfix Proof Of Correctness
Is there an easy/intuitive way to understand why the algorithm for transforming an infix expression to a postfix expression using a stack works?
1
vote
1answer
46 views
Given a set of partial preorders, return one not covered by any in the set
Let $S$ be a set of partial preorders over a set $U$
($\le$ is a preorder/quasiorder if $\forall x,y,z\in U$, $x\le x$ and $x \le y \land y \le z \implies x \le z$).
We say that a partial preorder ...
0
votes
0answers
35 views
Applications of circular linked lists
Is a circular linked list just a nice programming exercise, or does it have any real world applications? I am unable to find much information on this topic, and any help would be appreciated.
2
votes
2answers
66 views
Memory-efficient list of N unique integers from 0..N-1 with fast lookup
We want to represent a list of $n$ unique integers between $0$ and $n-1$ in a memory-efficient way. The only operation we need to support is looking up the $n\text{-th}$ element.
What are some of the ...
-1
votes
1answer
93 views
AVL Tree rotations
What size is the largest AVL tree for which an insertion could trigger a double rotation?
-3
votes
0answers
32 views
What is the time complexity of this code? can you explain in detail? [duplicate]
Consider the following code segment. Assume n to be a positive integer.
...
1
vote
0answers
41 views
Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]
I'm trying to solve following problem:
Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
0
votes
1answer
40 views
Are there still researches on new Data Structures? If so, what are some examples / scenarios?
And I assume these new data structures are more context/field-specific?
0
votes
0answers
55 views
Write functions that run in O(1) time
This Question can be found in the book: ODS: An Introduction (Chapter 6)
Suppose we are given a binary tree with pre-, post-, and in-order numbers assigned to the nodes. Show how these numbers can be ...
1
vote
1answer
19 views
Pre-computing min/max for interval queries?
I'm basically trying to figure out if the following problem has a common name and/or a standard solution in computer science.
Let assume we're given $N$ two-dimensional tuples $(x_i, y_i)$. This data ...
0
votes
0answers
26 views
Data structure for incremental KNN (IKNN) search over high-dimensional vectors
I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
0
votes
0answers
8 views
Comparing the added cost of replacing a map with an extra Merkle tree to provide non-membership proofs
Here is the trade-off:
-Merkle trees that append leaves to the right tend to have a better Locality of reference, and thus shorter batch proofs (a lot of sibling nodes will be common and thus fetched ...
0
votes
0answers
17 views
Computer network graph design
In the following question, we need to suggest a graph design and a routing algorithm.
Routing from $A$ to $B$ is done by returning an edge sequence in the graph that will lead us from $A$ to $B$
...
0
votes
1answer
34 views
Give an O(n^2) algorithm to solve
This is my homework question
Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that
A[i] + A[j] = α for a given value α.
Give an O(n^2) ...
0
votes
1answer
26 views
Considerations for space complexity analysis
There is a lot of information on time complexity analysis. For example, we know that for calculating the time complexity we study the number of operations (e.g. traversal, swapping, comparisons etc.) ...
1
vote
1answer
65 views
How to join two Scapegoat Trees in O(log n) time?
I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single ...
3
votes
0answers
36 views
How do search engines implement fuzzy search?
Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses".
How is Google able to return near-...
0
votes
1answer
15 views
Given an array of n points of the form (x,y), the distance between two points (x1,y1) and (x2,y2) is defined as min(abs(x1-x2), abs(y1-y2))
We need to find mth smallest possible distance by considering all possible pairs. I solved this problem by considering all possible pairs and maintaining a max priority queue. If the max priority ...
0
votes
2answers
33 views
How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?
Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't ...
0
votes
0answers
30 views
An idempotent grammar for text decoding?
I'd like to create a function decode(x : string) such that decode(x : string) == decode(decode(x : string)).
I believe I can ...
1
vote
0answers
43 views
finding max element in a min-max heap structure
I am trying to implement min-max heap structure
A min-max heap is a data structure that is identical to a binary heap, but the heap-order property is that for any node, X,
at even depth, the element ...
-3
votes
1answer
1k views
Print all nodes which are the endpoint of the diameter of a tree
Given a tree with n nodes, Print all nodes which are the endpoint of the diameter.
1<= n <=100000.
E.g.
For Above tree answer would be A,B,F,G
I tried the O(n2) approach (Running Dfs from each ...
2
votes
1answer
32 views
Using B+Tree to implement index, when the index-key size and the data-block size are of the same order
I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a ...
1
vote
2answers
97 views
Find neighbour objects in a 3d grid
I have points in a 3d world where their position is defined by 3 integers: X, Y, Z.
I'm searching for an algorithm / data structure to store these points in a way I can quickly find (e.g.: O(log(N)) ...
1
vote
1answer
58 views
Minimum time to finish all meetings
what algorithm would you use to solve this problem which I recently faced in an interview?
There's a council where people go to have meetings. A person comes at time x and needs to be in a meeting for ...
1
vote
1answer
109 views
Why is the space complexity of finding anagrams in a string O(1) instead of O(n)?
In the problem
find-all-anagrams-in-a-string,
one tries to find all anagrams of a string $p$ (of length $k$) in a
string $s$ (of length $n$) and return a list of the anagrams' starting
indices.
The ...
1
vote
3answers
220 views
The number of ways of insertion in binary search tree
The number of ways in which the numbers $1,2,3,4,5,6,7$ can be inserted in an empty binary search tree, such that the resulting tree has height 5, is _________.
Note: The height of a tree with a ...
1
vote
2answers
188 views
How C++ and alike maps are actually stored in memory?
I admit I didn't know much before what a Map is living with just the terminology Hash Tables, even when I first Google it I found this
https://www.mathworks.com/help/matlab/matlab_prog/overview-of-the-...
2
votes
0answers
29 views
Shortest path in a tree
Is it correct to talk about shortest path in a tree, isn't a tree has only single path between any two nodes ?
0
votes
1answer
32 views
How is a histogram implemented as a data structure?
I'm reading a paper about O(1) median filtering. I'm confused how histograms, denoted H, have the properties described. How can histograms be implemented such that: summing histograms, H(A ∪ B) = H(A) ...
0
votes
1answer
27 views
What is the name of a sequence structure where writes in the same area are faster?
I recall reading about a data structure for sequences where writes in the same area are faster due to some kind of caching or structure manipulation. What are some structures that do this? I know a ...
