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
vote
1answer
13 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
16 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
27 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
20 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
51 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
37 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
31 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
18 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
15 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
39 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
25 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
33 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
93 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
57 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
108 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
208 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
180 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
vote
1answer
41 views

How to count occurences in a Skiplist

If we have an sorted skiplist how can we count the occurences if it is sorted on a effective way? Occurence of the same element in the skiplist?
2
votes
0answers
32 views

Simple efficient algorithm for dynamically maintaining max of special linear functions

Given $n$ tuples $(k_i >0,a_i >0)$, is there any efficient algorithm that can dynamically track $$ \max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\} $$ in response to ...
0
votes
2answers
58 views

Binary Tree as 2D array with variable length raws

Usually we use the tree data structure when we care about time complexity for ins/del/... -In this special case problem, space saving is mandatory too that is 2 pointers for each node is unaffordable; ...
2
votes
2answers
45 views

Definition of position for List ADT (singly linked list implementation)

Chapter 2: Basic Abstract Data Types of the book Data Structures and Algorithms by Aho, Hopcroft & Ullman states the following: If the list is a1, a2, ... , ...
0
votes
1answer
73 views

my dsa teacher gave a assignment which is really confusing (i asked my teacher about it but she said just google it and find it out yourself) [closed]

Write best case, worst case and average case time complexity of following categories of algorithm– a. Constant time b. Linear time c. Logarithmic time d. Polynomial time e. Exponential time (this ...
0
votes
1answer
65 views

Checksum Algorithm that produces correct 16-bit checksum value for any given input

I need a checksum algorithm that produces the correct 16-bit checksum value for a given input. It's a packet recording from serial communication that I would like to reverse engineer. I have two data ...
2
votes
1answer
88 views

Find maximum length subarray whose bitwise AND is at least $k$ in $o(n^2)$

Given an array $A$ of unsigned integers, a subarray is a contiguous interval $A[\ell],\ldots,A[r]$. The bitwise AND of the subarray is just the bitwise AND of $A[\ell],\ldots,A[r]$ (what is denoted by ...

1
2 3 4 5
39