Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1
vote
0answers
12 views
What is the term for two file formats that describe the same amount of information?
I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not ...
0
votes
0answers
22 views
Quick access to top element of subsets of elements
I have a set S of (key, value) pairs and a large number of subsets of S. I'm looking for a ...
14
votes
2answers
1k views
What is this data structure/concept where a plot of points defines a partition to a space
I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem.
Basically it's a plot of points, and the ...
0
votes
0answers
6 views
Adaptive radix tree for storing Hash vs HAMT
Is there any disadvantage to using Adaptive radix tree to store hash of key like it is done in HAMT and Ctrie
Would it be slower?
Would it use more memory?
0
votes
0answers
18 views
Pseudocode for Userdefined Data Types
In the pseudocode guide for my syllabus, an example of a record data type is given as below:
...
1
vote
0answers
28 views
Probability lower bound on a double cycle in cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
0
votes
0answers
13 views
Set List Queue Deque Map these are Collection frameworks of Java but can anyone differentiate the unique features among each of them [on hold]
We are know Set List Deque Map Queue are all a part of java collection framework but can anyone please tell me how are the unique in terms of
Memory management
Fetching Data
When is the particular ...
0
votes
0answers
15 views
How to sort a woven shuffled stack
Say you have sort of a "woven shuffling situation" going on, sort of like this.
Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...
0
votes
0answers
12 views
How to identify the final set of “contours” when combining multiple primitive contours
This problem is in relation to how fonts work. Say you have a "glyph" that is composed of of these 5 "contours", or enclosed loops.
On their own, each of them is a unified whole. The easiest thing we ...
0
votes
0answers
15 views
How to accomodate decision trees with infinite options
I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
1
vote
1answer
30 views
Delete a node with 2 children in a binary search tree
Recently in class we learned how to delete a node from a binary search tree. Since in a binary search tree, each node can have at most 2 nodes, there are 3 cases of deletion.
Case 1: The node is a ...
0
votes
0answers
6 views
Composite and Non-Composite User-Defined Data Types
I have a learning resource which claims the following about user-defined data types
Non-composite include:
Enumerated
Pointer
Composite include:
Record
Set
This confuses me, and I would ...
2
votes
1answer
35 views
What, if any, is the term for a node whose children are all leaf nodes?
More specifically, I'm interested to know if there is a term that describes a tree node that meets two conditions:
- It has >= one child
- Any children that it has are all leaf nodes.
2
votes
1answer
37 views
Find four sets where each element from those four appears in at least two of those four sets
I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:
$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$
$A_i$ ...
1
vote
1answer
27 views
Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex
How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?
UPD:
Example for n = 4:
insert 60
insert 10
insert 20
insert 50
...
2
votes
0answers
39 views
Storing relations space efficiently?
Let $f$ be a binary relation defined on set $S$, which contains numbers from $1$ to $n$. It is also given that number of $|\text{Img}(f)| \le k$. I want to store the function $f$ such in way such that ...
2
votes
0answers
30 views
Documentation of “bin number” trees
TL;DR: I implemented a special (?) binary tree and can't find any further details on the method I used on the internet. I would like to know if there are any scientific papers discussing my ...
2
votes
2answers
52 views
Interview Question: Insert switch to maximize time lightbulb spends on
Problem statement:
You have a lightbulb for an interval of $N$ seconds, where $N$ is given.
At time 0, the lightbulb switches on, and at time $N$, it switches off,
regardless of any switches. ...
1
vote
1answer
41 views
Number of contiguous subsequences summing to a given target
I could not figure out an efficient way (better than $O(n^2)$) to count the number of contiguous subsequences of an array of both positive and negative integers summing up to a given number $k$.
For ...
2
votes
0answers
28 views
Algorithm / data structure to filter documents by number of missing words
Is there a data structure or an algorithm or a combination of both to allow me to filter a set of documents based on the number of missing words (compared to another list)?
Problem Definition
We ...
1
vote
2answers
81 views
How to analyze the worst case of weighted quick-union method on union-find
Here is exercise 1.5.15 in Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne.
Show that the number of nodes at each level in the worst-case trees for weighted quick-union are binomial ...
1
vote
0answers
15 views
Data structure able to perform fast and simple updates
Let's say we want to build data structure able to perform two operations.
First one, query is asking for the sum of values in the range $[i, j]$. And the second one, the update is setting all values ...
3
votes
1answer
37 views
Graphs in space efficient representation
Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph ...
3
votes
0answers
24 views
How to maintain completely dynamic convex hull quickly?
If there's no deletion, we can use $2$ balanced trees to maintain $2$ half convex hulls(up and down). In this way, we can insert $n$ points in $O(n\log n)$ time.(In the beginning, there are no points)
...
1
vote
0answers
25 views
Efficient data structure for multidimensional searching on intervals and keys
I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (...
1
vote
1answer
28 views
Understanding access and insertion time of arrays
Why do most implementations of arrays have constant access time and linear insertion time?
4
votes
0answers
49 views
Distribution of pointer keys in a Skip-list node
Suppose we have a list of $N$ keys where the distribution of keys follows $f(x)$.
We construct a skip list over the keys.
Now if I pick a key (e.g. 31 in the ...
0
votes
2answers
36 views
Sorting in a Priority Queue
Does a priority queue Queue<K,V> always sort its elements based on the value of each element or its key?
I know than the priority in the queue is based on ...
0
votes
1answer
19 views
Maintaining data structure with two operations
I was trying to implement data structure over set of rectangles that can perform two types of operations.
Update operation, add new rectangle with sides parallel to x and y axis and positive ...
0
votes
0answers
16 views
Find the direction of monotone polygon (if exists) in linear time
Implement a program that checks if there is a direction in which a simple polygon is monotone and,in that case, reports such a direction.
Upper bounds: O(n) time, where n is the size of
the ...
0
votes
0answers
44 views
Find the Maximum rows having all ones in the binary if you are allowed to toggle columns in the matrix for exactly k number of times
A binary matrix of nxm is given, you have to toggle any column k number of times so that you can get the maximum number of rows having all 1’s.
for eg, n=3, m=3,
...
2
votes
1answer
42 views
Data Structures - Segment Trees
I was learning about segment trees and came across this:
We have an array arr[0 . . . n-1]. We should be able to
1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1
...
3
votes
1answer
86 views
Find all values repeating more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time
Given a parameter $k$ and an array (not sorted) of length $n$ return all values which repeat more than $\lfloor n/k \rfloor$ times in $O(n \log k)$ time.
I've managed this in $O(nk)$ time, but can't ...
1
vote
1answer
29 views
Linear ordering of all subsets of size k
I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
1
vote
1answer
32 views
Matrix of a graph and computational complexity
Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
2
votes
0answers
27 views
Bug in wikipedia page for Van Emde Boas tree?
The Wikipedia page for vEB trees (specifically the version from 27 September, 2018),
gives the following pseudocode for finding the successor element of x in the vEB tree (of universe of size M):
<...
-1
votes
0answers
15 views
AVL Tree:Deletion proof
Show that at most one node in an AVL tree becomes temporarily imbalanced after the immediate deletion of a node as a part of standard remove map operation.
How should I start and what should I use to ...
2
votes
1answer
60 views
Largest rectangle problem
Recently while solving programming challenges for the fun of it, I encountered a challenge which left me kind of puzzled and yearning for a proper solution, other than brute forcing. The problem (...
0
votes
1answer
37 views
Determining an appropriate number of buckets for a hash function
I would like to select an appropriate number of buckets in my hash table for this scenario:
A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed ...
2
votes
1answer
36 views
minimum number of nodes that traverse all the graph
In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
0
votes
1answer
79 views
Calculate the average length of the linked lists in a hash table
I am learning hash tables, and I would like to know how to determine the average length of the linked lists.
For example: A hash table holds about 10,000 employee records. Each record is indexed by ...
2
votes
0answers
14 views
What are some of the simplest applications of heavy hitter problem?
I am learning about stream algorithms and am implementing Count-Min sketch data structure. I am also learning to approximately solve the HH problem with sublinear space complexity.
I want to know ...
2
votes
0answers
45 views
Insertion in 123 skip list
I had a problem in my exam dealing with 1-2-3 skip lists.
I have a problem with the insertion process in a 1-2-3 skip list. What I understand is that if the minimum of heights of 2 nodes in a 123 ...
3
votes
3answers
54 views
BST - Sufficient condition for connecting a node to a parent
Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree.
I want to prove that if I insert a node X into the tree and node X is ...
2
votes
1answer
14 views
Approximating unique string occurrences using a small, fixed amount of memory
Is there a small-memory way to estimate how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track ...
1
vote
0answers
19 views
How did the Registers get their names?
I'm interested in how the computer registers got their names, for example:
eax and ebx. I couldn't find anything.
1
vote
0answers
30 views
Intuition behind balancing of link/cut data structure
My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no ...
1
vote
1answer
29 views
Understanding basic queue and dequeue operations
CLRS gives the following implementation for a queue's enqueue and dequeue operations
...
1
vote
0answers
26 views
Direct addressing on a huge array
A Question from CLRS book:
(CLRS 11.1-4) We wish to implement a dictionary by using direct addressing on a
huge array. At the start, the array entries may contain garbage, and initializing the
...
1
vote
1answer
29 views
How to find the number of Binary Search Trees with given number of nodes and leaves?
With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:
Exactly $1$ leaf node(s) present?
Exactly $2$ leaf nodes present?
I was able to solve the first ...
