Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
1,666
questions
-4
votes
0answers
141 views
Counting a number of sequences where the item is the most frequent one [closed]
Consider an array $a$, where elements are numbers. Consider all subsequence of $a$. For each subsequence $s$, we find an element $k$ with the largest number of occurrences in $s$ (if there are several ...
1
vote
1answer
20 views
Definition of 'Record'
Given the definition of 'record': "a collection of field values for a given entity", is this a set of field values for ALL the fields of the entity, or only one particular field [so that you ...
1
vote
1answer
48 views
Interview q: Small possible length of stick from an array of stick lengths
I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here ...
0
votes
1answer
53 views
Container with findNthSmallest in O(1)
Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This container should support the following operations:
...
0
votes
0answers
22 views
Are data storage efficiency and volatility directly correlated?
It seems intuitive to me that less efficient data storage methods are also less susceptible to degradation over time.
For instance, the string "ABC" can also be represented as "...
2
votes
2answers
54 views
Algorithm for Estimating Number of Unique Monthly Visitors
Is there a way to estimate the number of unique monthly visitors to a site based on a limited sample of one week of data? I have information about when a given user visited the site. This isn't as ...
0
votes
0answers
8 views
Why are these BVH split heuristic formulas different?
I've been doing some research into changing the split heuristic I use for a work project comprised of a BVH binary tree.
The heuristic I currently use is centroid median as described here, but I seek ...
0
votes
1answer
21 views
Computing childrens of ith node of a d-ary tree
Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n).
The formula for indices of children of node no. i is given as:
{(1-i)d+2,
... , min{n,(1-i)d+d+1}...
2
votes
1answer
54 views
Difficulty in few steps in proof of “Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$”assuming union by rank, path compression
I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as ...
-2
votes
1answer
38 views
How to calculate the minimum price required to buy all the stones?
I have shared the question above. My current algorithm does the calculation in O((n^4)*(2^n)).
Can someone please help me out to solve this faster?
1
vote
1answer
25 views
Is there any rich problems that can be solved using several algorithm techniques?
I am wondering if there are some particularly rich problems that have a large intersection with algorithms and data structures. An example could be the travelling salesman problem. Any other ...
1
vote
0answers
41 views
Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree
I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A:
A is the sum of every part of a rectangle covered by another. So if two rectangle ...
1
vote
0answers
25 views
Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
0
votes
2answers
37 views
Data structure for shopping cart
I'm working on an e-commerce application where users can add stand-alone products like speaker or they can add a bundle product like desktop that has options like mouse, keyboard etc. All the products ...
0
votes
1answer
31 views
Data structure for efficient group lookup
I need a data structure, which allows efficient queries for 'give me the group of x'.
Let me give you an example:
...
0
votes
0answers
18 views
Bloom filter alternative supporting deletion without false negatives
There are several alternatives to bloom filters that support deletion from the set, for example Cuckoo filters or Counting Bloom filters.
However, deleting an element from these data structures ...
0
votes
1answer
15 views
Number of ways to bicolor a graph with some constriants
Given a graph G, I need to find the number of ways to color it using two colors Black and ...
1
vote
0answers
9 views
When would you use an edge list graph data structure instead of an adjacency list or adjacency matrix?
In what applications would you choose an edge list over an adjacency list or an adjacency matrix?
Sample Question, VisuAlgo: Which best graph DS(es) should you use to store a simple undirected graph ...
0
votes
3answers
47 views
Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound?
The worst case time complexity of a given algorithm is $\theta(n^3logn)$.
Is it possible that the worst time complexity is $\Omega(n^2)$?
Is it possible that the worst time complexity is $O(n^4)$?
The ...
0
votes
0answers
40 views
Which advanced data structure to use?
For range queries on a subarray [L,R] , I want to find all the indices of successive maximums from left to right within O(log(R-L+1)), excluding index "L". I know using segment trees I can ...
1
vote
0answers
30 views
How to map structured grid data onto a regular grid efficiently?
Context:
First of all, my data:
I am working with 3D data shaped onto a structured grid made of hexahedrons with for each 8 vertices and 12 edges.
The data I'm working on is cell data (and not point ...
0
votes
1answer
45 views
What is the difference between python list and c++ vector?
I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
19
votes
8answers
4k views
Is Group Theory useful in Computer Science in areas other than cryptography?
I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
2
votes
1answer
56 views
Efficiently storing and modifying a reorderable data structure in a database
I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each ...
1
vote
1answer
37 views
Tight upper bound for forming an $n$ element Red-Black Tree from scratch
I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order ...
2
votes
1answer
48 views
Uniform Hashing. Understanding space occupancy and choice of functions
I'm having troubles understanding two things from some notes about Uniform Hashing.
Here's the copy-pasted part of the notes:
Let us first argue by a counting argument why the uniformity property,
we ...
0
votes
1answer
34 views
Augmenting AVL tree to calculate sum of subtree
Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function
calculateSum(key), which receives a key of a node and returns the sum ...
1
vote
0answers
54 views
Is there a known way to make an efficient, compact, and fully persistent stack or queue?
In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
0
votes
1answer
14 views
Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time
I wonder what is the best data structure I can use in order to achieve the following:
Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ ...
2
votes
1answer
29 views
Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept
Originally posted in Stack Overflow but was told to post here.
Context: I am doing a PCA on a $M \times N \, (N \gg M)$ matrix with some invalid values located in the matrix. I cannot infer these ...
0
votes
1answer
16 views
Method to change value in a key for a min heap
How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
1
vote
0answers
28 views
Set data structure for data too large to fit into memory
I'm trying to solve the following exercise:
Given N data items and memory that can hold M/B blocks of size B.
Describe a data structure that needs at most N/B blocks of external memory and allows ...
0
votes
1answer
13 views
Binomial trees in binomial heap with 27 elements
How many binomial trees are in a binomial heap with 27 elements and how would you find this number?
0
votes
1answer
30 views
Use tree in-order traversal to determine whether a BST or Heap
Given these in-order traversal lists:
1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19
2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17
I need to determine whether each one of those lists represent a valid BST ...
2
votes
2answers
50 views
Implementing Queue operations in $\Theta(1)$
We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 ...
1
vote
0answers
34 views
How to estimate the number of elements inserted to a Bloom filter
A Bloom filter is a probabilistic data structure that allows encoding sets with false positives.
Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
2
votes
2answers
52 views
Efficient Data Structure for Closest Euclidean Distance
The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628.
A network of ...
0
votes
0answers
12 views
What is the insertion algorithm for an AVL tree with balance constraint of 2?
What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
2
votes
1answer
55 views
How to represent sums of piecewise quadratic functions for efficient optimisation?
I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
1
vote
0answers
63 views
Trees with duplicate nodes and path cancellations
I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
0
votes
0answers
26 views
Finding minimal degree for a B-Tree
We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5).
We are asked: "What is the minimal t we can choose?"
($t$ is the minimal degree, in ...
2
votes
1answer
75 views
What does Lambda Calculus teach us about data?
In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing?
Some context: as a software developer, I ...
2
votes
2answers
84 views
Managing an hotel using AVL trees - Data Structures
I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$
and it can be occupied or not.
Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, ...
0
votes
1answer
25 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 ...
0
votes
1answer
27 views
Prove that AVL tree has this kind of property with Fibonacci sequence
Q: Prove that for any AVL tree that has $n$ nodes ($n\geq 1$)
and has a height of $h$ this property is true:
$n \geq F(h)$ where $F(h)$ is the $h$-th element in the Fibonacci sequence:
$F(0) =0, F(1)=...
2
votes
1answer
47 views
Algorithm for splitting an array into k sub-arrays
We want implement a data structure that have the following methods: Init(A,k)- Gets an array A with n different values and initialize our data structure that so it will divide A into k equally sized ...
1
vote
2answers
34 views
Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets
Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.
More ...
0
votes
0answers
20 views
Best way to find and store difference between two strings
I want to implement my version of the Codeshare service. Now I'm thinking of an implementation where all users have access to one string that can change (if you already have a better option here - ...
1
vote
1answer
34 views
Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?
Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined.
The question is ...
1
vote
1answer
39 views
Finding a closed formula for recurrence relation
I'm trying to find a closed formula for the below recurrence relation:
For the first one, $n$ is some power of 2
$$T(n) = \begin{cases}
4 & \text{if $n=1$} \\
2T(\frac{n}{2}) +4 & \text{...
