Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,989
questions
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 ...
- 135
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.
...
- 1,005
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 ...
- 217
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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
...
D.W.♦
- 140k
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 ...
CommunityBot
- 1
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 ...
- 1,005
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 ...
CommunityBot
- 1
-1
votes
1
answer
45
views
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 ...
CommunityBot
- 1
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 ...
D.W.♦
- 140k
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 ...
- 325
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 ...
- 1,005
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 ...
CommunityBot
- 1
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))$
- 3,241
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 ...
- 33k
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 , .... , ⌈ ...
- 1
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....
- 235
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 ...
- 101
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. ...
CommunityBot
- 1
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 $...
CommunityBot
- 1
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$ ...
- 33k
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,005
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 ...
- 22.7k
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 ...
- 1,257
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}...
CommunityBot
- 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 ...
- 1,257
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 ...
CommunityBot
- 1
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
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 ...
- 13
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() ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 330
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 : ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 111
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.
...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 <...
- 1,257
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
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 ...
- 33k
-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 ...
- 33k