Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,995
questions
1
vote
1
answer
30
views
A red-black full tree where every black node has at most 1 red child has at most (n-1)/4 red nodes
Let us call a red-black tree strict when every black node has at most one red child.
Show that a strict red-black full tree has at most $(n − 1)/4$ red nodes; a binary tree is full when every node has ...
- 369
-2
votes
0
answers
18
views
SQL query problem: Only first 3 active affiliate commision out of 10000 recruits is calculated and only for first 3 sales from each recruits?
Create a database query to recruit Mike in the business and they recruited 200 individuals as their business affiliates the first active individual who made their $100.00 monthly membership fee would ...
- 1
2
votes
1
answer
52
views
Solution Verification: How does the postorder traversal of a BST change after rotating left?
Given a BST $T$, $x$ is a random node in it and $y$ is the right child of $x$.
How does the PostOrder traversal of BST $T$ change after we rotate the tree left on node $x$? In which cases does the ...
- 165
2
votes
0
answers
42
views
$y$-Fast Tries: Why not partition into groups of $\Theta(\log^2 M)$ elements?
The $y$-fast trie is a data structure for storing a sorted collection of $n$ integers from the range $[0, M)$. It builds on the $x$-fast trie, which also stores elements in this range.
The space usage ...
- 8,817
0
votes
0
answers
34
views
Undirected unweighted sub-graph enumeration with threshold on node value
I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive.
Given an input threshold $t\in [0,1]$, I ...
- 101
0
votes
2
answers
78
views
Binary compression algorithm with decompress by index
I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The ...
2
votes
3
answers
113
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 ...
- 23
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 ...
- 23
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 ...
- 11
1
vote
1
answer
52
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 ...
- 37
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
214
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:
...
- 21
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))$
- 381
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
62
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
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$ ...
- 369
1
vote
1
answer
60
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 ...
- 381
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
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 ...
- 21
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
0
votes
0
answers
33
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
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 ...
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 ...
3
votes
1
answer
433
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 : ...
user149684
1
vote
0
answers
18
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
0
votes
0
answers
28
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 ...
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 <...
- 199
0
votes
2
answers
89
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
96
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 ...
- 13
3
votes
0
answers
70
views
Does a priority queue exist with O(1) extract-min and re-insertion from removed positions?
I am envisioning a priority queue that is a bit strange. It represents wanting to do a depth-first left-to-right walk of a tree, but allowing for parallel workers where there can be time between ...
- 12.3k
-1
votes
1
answer
107
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 ...
- 7
2
votes
2
answers
64
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
1
vote
0
answers
31
views
Data Structure for Floorplan with Moveable Walls
I am currently reading through the paper "Computer-Generated Residential Building Layouts" by Paul Merrell, Eric Schkufza and Vladlen Koltun. In this paper, they create and optimize ...
0
votes
0
answers
34
views
Pointers are only used in algorithms concerning data-structure?
From the point of view of writing pseudocode, I have never seen any algorithm making use of pointers except when writing algorithms about data-structure (like writing algorithms for linked list ...
1
vote
0
answers
24
views
What Data Structure works best for this problem?
I have 2 sets of atmost 25000 4-tuples. Currently, I am storing them as 2 lists of 4-tuples A and B.
I have to perform the following computation for each of the combinations of A and B.
...
- 11
2
votes
0
answers
56
views
Data structure for finding greatest lower bound with respect to a partial order
I have some partial order $\preceq \,\,\subset A \times A$, I'd like a data structure with the following operations:
$Insert(a, x, T)$: add $(a, x)$ to the collection $T$
$Find(x, T)$: find the ...
- 3,728
0
votes
1
answer
107
views
what could be more efficient way for this problem?
So I'm trying to solve this problem and I came up with a brute force solution. I was wondering how can i make it more efficient ?
Problem:
Suppose i have resources and integer that denotes at what ...
- 9
1
vote
1
answer
28
views
Why does this example of a Canonical Interval Decomposition contain keys and leaves that are outside of the interval?
I am reading Advanced Data Structures by Peter Brass for self-study, and was confused about the book's example of a Canonical Interval Decomposition for the Segment Tree section (section 4.2):
So, ...
1
vote
0
answers
70
views
Sorting in linear time using Trie data structure
I have written an article on a new way of non comparison sorting and I want it to get peer reviewed. The sorting algorithm uses Trie data structure to store digits of numbers as nodes and iterating ...
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() ...
- 149
0
votes
0
answers
37
views
What are the different methods of evaluating a postfix expression?
As of now, the only method I know for evaluating postfix expression is using a stack.
The following question was asked in a past semester:
What are the two different methods of evaluating a postfix ...
-2
votes
1
answer
68
views
Dividing a binomial heap to 3 equal-sized binomial heaps
Given a binomial heap of $n$ nodes (where $n$ divides by 3), how can I split the heap to three binomial heaps with an equal number of nodes (every heap contains $n/3$ nodes).
The time complexity needs ...
- 1
0
votes
0
answers
95
views
Design a data-structure $BankAccount$ that supports the following operations in constant time complexity
Problem:
Design a data-structure $BankAccount$ that supports the following operations in $ \underline{\text{constant time complexity}} $. Meaning $O(1) $.
$Init()$ - initializes bank account $L$ with ...
- 211
1
vote
1
answer
36
views
Why doesn't this implementation of Skip List simply return the current node when its key is equal to the query key?
I was studying Skip Lists in section 3.10 of Advanced Data Structures by Peter Brass and was confused about a detail of how the search algorithm in implemented. (This is self-study, not homework).
The ...
0
votes
0
answers
13
views
Naming the functions for Shaping the data for UI
Context
I work as a frontend developer, our main stack is Graphql & React that's relevant for this question.
The data I'm requesting can be quite complex and very often combined with several ...
- 1
2
votes
1
answer
54
views
(Algorithm required) How to determine if a point is in one of many rectangles
What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it)
Whats the most ...
- 23
2
votes
1
answer
39
views
Lower bound for querying KD tree
In the book Computational Geometry, Algorithms and Applications there is an exercise asking:
In the proof of the query time of the kd-tree we found the following recurrence:
$$
Q(n)= \begin{cases}O(1)...
- 69
1
vote
2
answers
46
views
Space-efficient way to prove that a data has been processed before
Suppose that I have a stream of data packets in the form of unsigned 64 bit integers.
And I want to make sure that I am not processing the same packet content more than once.
A way of doing this would ...
- 11
2
votes
1
answer
22
views
How to create tensors at runtime?
I have a small personal CAS project around linear algebra which involves, among other things, manipulating tensors. When I talk about tensors, I mean them according to the physical / mathematical ...
- 255
1
vote
1
answer
74
views
Amortized analysis (accounting/banker's method) for tree operations
Suppose we have a tree data structure with root $r$ with two operations:
Add($x, y$) - adds the node $y$ as a child to the node $x$
Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct ...
- 21