Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [data-structures]

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

0
votes
1answer
20 views

what is the fastest way of loading data from disk to memory?

I have a large data set which is currently stored as 2 million records in a database. I am loading this data and manipulating it so it is stored as java objects in memory to be used later in my ...
0
votes
0answers
17 views

Data Structure which maintains spacing for similar elements

I want a queue like data structure in which a new element inserted has to be some elements away from a related element. While reading from this data structure, related elements should only be read ...
1
vote
2answers
23 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
24 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 ...
15
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
93 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
25 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
29 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
46 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
87 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 ...