# Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

1,989 questions
Filter by
Sorted by
Tagged with
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
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. ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
45 views

...
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: ...
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 ...
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
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
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 ...
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 ...
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 ...
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))$
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 ...
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 , .... , ⌈ ...
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....
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 ...
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. ...
2k views