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

1
2 3 4 5
39