Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

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
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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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: ...
user avatar
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))$
user avatar
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 , .... , ⌈ ...
user avatar
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....
user avatar
  • 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$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 : ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 <...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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 ...
user avatar
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() ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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)...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 21

1
2 3 4 5
40