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
2 votes
3 answers
81 views

Find the smallest difference between two numbers in a DS in O(1) time

I got an assignment to create a new data structure, with the following rules: Init - O(1). Insert x - O(log$_2$n). Delete x - O(log$_2$n). Search for x- O(log$_2$n). Find max difference between two ...
1 vote
2 answers
4k views

Inorder Traversal of the Ternary Tree

As per Wikipedia, Algorithm for In-order Traversal of Binary Tree If the current node is empty/NULL/None return nothing. Traverse the left subtree by recursively calling the in-order function. ...
0 votes
2 answers
55 views

Why is behavior included in the definition of a data structure?

When reading about ADT's and data structures it is common that the ADT Stack is implemented in at least two ways. Either based on an Array or Linked List. From these examples I tend to think that the ...
2 votes
1 answer
538 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 ...
0 votes
3 answers
75 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 ...
0 votes
3 answers
245 views

How to convert a Complete Binary Tree to a Priority Search Tree in O(n)?

I would like to know if there is a linear-time algorithm ($\mathcal{O(n)}$ time) to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, to a Priority Search ...
0 votes
1 answer
48 views

Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
1 vote
3 answers
480 views

When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?

This seems to be my first ever question :) Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that. I don't ...
0 votes
1 answer
62 views

How does vector space model differs from traditional B-tree indexes

I've asked the following question on StackOverflow: https://stackoverflow.com/questions/71819288/mongodb-vs-elasticsearch-indexing-parallel-arrays I think that getting theoretical information on this ...
-1 votes
1 answer
45 views

Reverse An Array whats wrong with this type of code?

...
2 votes
1 answer
209 views

Show all chains per user

Some time ago I had in one of the big tech interviews the following question that I still don't know how to approach it. You have a chains of reservations from AirBnb: ...
0 votes
1 answer
120 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 ...
2 votes
1 answer
44 views

Shortest word not in dynamic set

What is the most efficient data structure for a dynamic set of words over a finite alphabet $\Sigma$ which supports the following operations? Add a word. Remove a word. Determine a shortest word ...
1 vote
1 answer
46 views

Randomized Algorithm Lemma

Hello I am struggling with proving a lemma, it goes as follows: Suppose we have a vector r = (r1....rn)^T where rj is either 0 or 1 which is selected uniformly at random with probability 1/2. Suppose ...
1 vote
1 answer
26 views

What is a good load factor for seperate chaining (closed addressing)?

For open addressing, I know that once you have around 70% table being filled you should resize because more than that you get collision. But for closed addressing, I read that load factor should not ...
0 votes
0 answers
18 views

Looking for an algorithm for multi-path funnel analysis

Suppose we have a dataset with each instance: {uid, action, TS}. The funnel algorithm (e.x https://clickhouse.com/docs/en/sql-reference/aggregate-functions/parametric-functions/#windowfunnel) looks at ...
2 votes
1 answer
365 views

Splay trees: why are depths of nodes on the access path halved?

The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that: Splaying not only moves x to the root, but roughly halves the depth of every node ...
0 votes
1 answer
48 views

equivalency of some facts in $O$ notation

I misunderstanding about some logarithm property in algorithm course: is it correct that we say following three term is equivalent? $O(\log a + \log b)$ $O(\log (ab))$ $O(\log (a+b))$
8 votes
7 answers
57k views

Are degree and order the same thing when referring to a B-Tree?

I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2. We know that the degree is related to a node but what is the degree of a tree? Does degree impose any ...
0 votes
0 answers
27 views

Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)

Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as - F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
2 votes
2 answers
60 views

What is the lower bound on retrieving an item in a collection if no arrays(Random access memory) are allowed?

I know that retrieving an item in a collection can be done in $O(1)$ time(on average) using hash tables. I would like to know if there is an algorithm that could be as performance without using arrays....
2 votes
1 answer
337 views

Proof of Fenwick Tree's correctness

Unfortunately (like many other authors) Fenwick does a very bad job of explaining his work (the Binary Indexed Tree) in the original text. The paper lacks a proper formal proof of why this structure ...
0 votes
1 answer
130 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. ...
2 votes
2 answers
2k views

Interval tree: find all intervals containing a given interval

Given an interval tree $T$ and an interval $I$, I need to find an algorithm that returns all intervals in $T$ that contain $I$. The asymptotic running time should be $O(\min(n,(k + 1) \log n))$ where $...
2 votes
1 answer
50 views

Bounding the height of a tree in a variant of disjoint set union

Consider a variant of link-by-size implementation of the Union–Find data structure, in which trees will be linked by the logarithm of the size. Let $\ell_i$ = $⌊\log_2|T_i|⌋$ and, when merging $T_i$ ...
2 votes
2 answers
63 views

How are a graph and a binary tree represented as data structures in CLRS' Introduction to Algorithms?

In CLRS' Introduction to Algorithms: (1) In 22.1 Representations of graphs The adjacency-list representation of a graph G = (V, E) consists of an array Adj of |V| lists, one for each vertex in V. For ...
1 vote
1 answer
84 views

Is there a simpler solution for this recuurence?

Consider this recurrence relation, $$T(n)=T(n-\sqrt{n})+1$$ I try to show that $T(n)=O(\sqrt{n})$. Also, I read this link, but my question is, can I claim that, at each step $n$ decreased by at least ...
1 vote
1 answer
58 views

Why do hash tables have no access/indexing complexity but have $O(1)$ search complexity?

Sources: https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://www.bigocheatsheet.com/ It can be seen that a Hash Table has no access/indexing complexity given the above sources. This ...
0 votes
1 answer
59 views

Computing childrens of ith node of a d-ary tree

Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n). The formula for indices of children of node no. i is given as: {(1-i)d+2, ... , min{n,(1-i)d+d+1}...
2 votes
1 answer
51 views

Efficient data structure to maintain a set of postal codes and mailbox numbers

A 'person' is represented by a combination of postal code and mailbox number(both are natural numbers) No two postal codes are alike, yet a postal code can contain many different mailboxes. At any ...
3 votes
1 answer
48 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 ...
5 votes
4 answers
5k views

Depth of any node x in Weighted Quick-Union Algorithm

I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall ...
1 vote
2 answers
46 views

Encoding set values in $o(n)$ memory

Apache Spark, a distributed computation framework, has a construct called accumulators which are global variables with an associative addition action. These can be used to aggregate statistics during ...
1 vote
1 answer
35 views

Tight analysis on a custom data structures with Insert and Remove-Min

I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() ...
2 votes
1 answer
125 views

Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can ...
0 votes
0 answers
24 views

Algorithm to generate unique suggestions for creating an ID

Let's say I have a service where I provide user registration. The user chooses a ID. Now if I already have someone who is registered against that ID, I will inform the user that this ID is already ...
3 votes
1 answer
425 views

Efficient data structure for insertion, deletion and smallest-not-in-range query on an array of integers

I'm trying to make a data structure $A$ that has the following features: insert($a$) operation : insert given integer $a$ to $A$. It is assured that all integers are unique. delete($b$) operation : ...
3 votes
1 answer
310 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
0 votes
0 answers
43 views

Efficiently finding range from ordered list of ranges with preprocessing

Say we have a list of ranges like so: ranges = [(0, 100), (101, 200), (201, 300)] The ranges will always be ordered, never overlap, and perfectly align. We want to ...
1 vote
0 answers
17 views

In a relaxed radix balanced (RRB) tree, how is the height determined in practice?

In a traditional radix-balanced tree, the height of the tree can be determined quickly by counting the leading zeros of the number of elements of the tree, and indexes to node children can be ...
2 votes
1 answer
87 views

Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking

I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article. ...
4 votes
1 answer
734 views

Optimal Binary Search Trees Knuth

Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289 Please have a look at this paper, specifically page 18 in which he tries to prove his ...
2 votes
0 answers
678 views

How much better are conservative updates for count-min sketch?

I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative ...
0 votes
0 answers
27 views

How to reposition an undirected weighted graph on a 2D grid where strongly connected nodes stay together?

I have an undirected fully-connected weighted graph of $n$ nodes, where $n=m\times m$. I want to visualize this graph on an $m$ x $m$ 2D grid. My goal is to place nodes connected with edges of higher ...
0 votes
1 answer
78 views

updating n elements in $O(\lg{n})$ time

I need to devise a data structure $S$ with the following functions: BUILD($S$) - build the data structure from a series of $n$ elements in time $O(n \lg{n})$ INSERT($S$, $k$) - insert a new element ...
1 vote
2 answers
5k views

Difference between Sequential ,Direct and Random acess with their acess time

I'm stuck on a point while reading about these different accessing methods. As per author. Sequential access Memory is organized into units of data, called records.Access must be made in a ...
1 vote
2 answers
198 views

Unique combinations of growing collection elements

Initial collection A = [1,2,3] should provide such combinations: {(1, 2), (1, 3), (2, 3)} I want to pop the first combination <...
0 votes
2 answers
73 views

can a complete binary tree have at least two nodes with just one child?

https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees says A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the ...
1 vote
1 answer
92 views

Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
-1 votes
1 answer
106 views

Is there an O(m (log n+ log m))-time algorithm that finds k-th smallest element in a row-wise-sorted two dimensional array?

I prepare for entrance exam and try to practice some hard problems. The following nice problem is problem 1(c) of this problem set. Suppose we are given a two-dimensional array $A[1...m][1...n]$ in ...

1
2 3 4 5
40