# Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

1,916 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
37 views

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 ...
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 ...
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 ...
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 ...
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? ...
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. ...
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.
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 ...
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 ...
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 ...
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, ...
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 ...
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.
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. ...
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?
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 ...
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.
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 ...
93 views

### AVL Tree rotations

What size is the largest AVL tree for which an insertion could trigger a double rotation?
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. ...
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 ...
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?
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 ...
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 ...
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$ ...
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 ...
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$ ...
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) ...
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.) ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)) ...
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 ...
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 ...
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 ...
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-...
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 ?