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
0 votes
0 answers
13 views

What data structure has the most succinct proofs and can be modified efficiently?

Question What data structure has the most succinct proofs and can be modified (insert, update, delete) efficiently? I have proposed a modification of merkle tree hashing as a potential solution but ...
  • 1
0 votes
0 answers
21 views

Improper binary tree: maximum number of external nodes

A binary tree shall be called proper if each node has either zero or two children. If it is not proper, it shall be called improper. I need to determine the maximum number of external nodes in an ...
  • 101
0 votes
1 answer
34 views

Maximum, delete and insert fastest data structure

The runtime to find a min element in max heap is $O(1)$. It takes $O(\log n)$ time to delete an element and $O(\log n)$ time to insert a new element in the heap. Does there exists a data structure in ...
  • 123
0 votes
1 answer
33 views

Is returning pointers to nodes for a list (doubly linked list) implementation a leaky abstraction? and is it bad?

I've been studying closely about the List abstract data type - As I understand it can be implemented with linked-list and/or arrays, and really maybe with any other data types as well. But to satisfy ...
1 vote
0 answers
22 views

What's the difference between the two abstract data types collection vs container?

From abstract data types in wiki, I'm reading about two types: collection and container. Can anyone supply a better detailed difference between the difference between the two? https://en.wikipedia.org/...
2 votes
1 answer
88 views

Approximating the median of the complement of a set

Given an integer $n$ and a tree set $S$, I would like to find the approximate median $x$ of the integer set $T := \{i \in \mathbb N : i < n \wedge i \notin S\}$. There are no constraints to the ...
  • 131
-1 votes
0 answers
21 views

what abstract data type does array belong to if it is a data structure, i.e. in javasript?

if array is just a data structure, I was wondering what abstract data type does it satisfy? When searched online whether Array is an adt or data struct, there are a lot of polarizing answers.
0 votes
1 answer
47 views

Why is Javacript's Object not a primitive data type?

If javascript's object is just associative array, what makes it non-primitive as they have labeled it? It is certainly already built in. Its not like I'm creating my own concrete implementation of ...
2 votes
0 answers
39 views

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at ...
-4 votes
0 answers
15 views

Take input from the user and convert lowercase letters to uppercase in MMIX

Write an MMIX program that converts each letter to uppercase converted. • Take text input from the user. • Write subprogram to convert the input to upper case. delve The thing is I do not know how to ...
1 vote
0 answers
34 views

What is the literature implementation of self-organizing lists?

I'm trying to implement self-organizing lists DS to publish as a public module. Over the course of Algorithms, we learnt that if you add a new element to the list, it should still do the huriectics. ...
  • 231
0 votes
0 answers
32 views

What binary search tree to use if probabilities of element query are known apriori?

There is a universal set of integer pairs $(key; outcomes)$, a subset of which is inserted into a binary search tree in $O(\log n)$ time for each key and can be searched by keys. Afterwards a large ...
0 votes
1 answer
22 views

What is the most efficient way to represent an directed dynamic massive 3D graph?

I know that there are many techniques to represent graphs. Suppose I have a directed massive 3D graph with 100,000 nodes at maximum. Suppose the graph looks somewhat like the following: Suppose each ...
0 votes
1 answer
22 views

Confusion about B-Tree

In a B-Tree, one of the rules is: Every node (except the root) is at least half full But then, in a 4-way B-Tree, we have the following case. Suppose we want to insert $10,20,30,40$ to the tree. After ...
0 votes
2 answers
40 views

if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$?

if we have $f(n)=f(n-7)$ and $f(2)=3$ can we conclude that $f(n) \in \theta(1)$? what if we also have $f(1)=2$?
0 votes
0 answers
23 views

In two level perfect hashing from CLRS we use m = n at the first level for expected space<=3n. Instead if we choose m = αn can space be decreased

In two level perfect hashing scheme shown in CLRS 3rd edition 11.5, this also has a great explanation here We set m = n at the first level and then for secondary hash tables we set mi = n^2. This ...
-1 votes
0 answers
30 views

What’s this data structure?

Given a series of timestamped values and some calculation can be done on a contiguous range of values. The calculation is composable. For efficiency, we can preemptively cache the calculations on ...
-1 votes
1 answer
25 views

A question about the graph theory or data structure and algorithms

I would like to ask this question as I am not sure about the answer. Let $G=(V,E)$ be a connected, undirected graph, and let $x,y\in V$ be two different vertices. Let $A$ be the problem of finding the ...
1 vote
2 answers
82 views

Order-preserving hashtable for integer tuples

There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$. The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
2 votes
0 answers
17 views

Proof that state-based (convergent) CRDTs are causally-consistent

Conflict-Free Replicated Datatypes (CRDTs) are a class of distributed data structures where replica states are allowed to temporarily diverge, but will eventually converge (in the absence of network ...
  • 253
4 votes
1 answer
61 views

Function which describes an optimal data structure for a bounded number of query operations?

Given an ordered sequence of $n$ elements, you have to choose a family $A$ of subsets of consecutive elements, such that each subset of consecutive elements (not necessairly in $A$) can be represented ...
2 votes
0 answers
40 views

Enumeration of the vertices in a quad-edge structure

A quad-edge is a well-known data structure used to represent planar subdivisions or polyhedra. https://en.wikipedia.org/wiki/Quad-edge The procedure to enumerate the edges works by recursively ...
  • 6,085
0 votes
1 answer
30 views

Representing graph as a search tree

How do I convert a graph to a search tree? Here's the question- The problem is that I don't know how to represent interconnections in a graph on a tree. In the diagram A is connected to D, and same ...
  • 3
1 vote
1 answer
74 views

What is the proper way to approach a competitive coding problem?

***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/ 1) Take the "***Climbing Stairs" Problem for instance: If I was given a problem like this on a test after mastering ...
2 votes
3 answers
68 views

Best Data Structure For Text Processing

Given a sentence like this, and i have the data structure (dictionary of lists): {'cat': ['feline', 'kitten']} A feline was recently spotted in the ...
  • 121
1 vote
4 answers
54 views

How to index a table for fast intersection?

For example (and this is not my use case), imagine there is a set of 50 000 random natural numbers represented in decimal with 8 digits (in the range 00 000 000 to 99 999 999). We could index the set ...
  • 13
0 votes
1 answer
34 views

Randomly build a binary search trees with simple modification

Let $X=x_1,x_2,x_3,\dots,x_n$ be set of $n$ distinct keys. I read this posts about Randomly build binary search trees like this and now I encounter the following question in my mind, suppose we ...
  • 1,418
0 votes
1 answer
52 views

Way to call and explain: "potentially infinite set of attributes" in databases

This is a bit of a theoretical question. I would like to know how to call the principle described below, in proper computer science terms, or math terms. Let's say we have a database in which one ...
2 votes
2 answers
168 views

Designing a Data Structure that allows both insertion and extracting a number lower than median in amoritzed O(1) cost?

Consider a data structure that has only two functions. extract_lowerthan_median() and insert(). How can we design it in a way that the amortized cost for both the operation is O(1)? Using a 2 tree, a ...
0 votes
1 answer
40 views

Minimizing/Maximizing recursion depth for DFS

The idea for this problem comes from GATE CS 2014 Set-3 Q13. Given a graph, are there any heuristics to figure out a DFS traversal which has minimum/maximum recursion depth? Consider the graph from ...
  • 656
0 votes
0 answers
47 views

Can anyone explain how a circular buffer array works?

I'm currently learning about Data Structures and Abstractions and one particular problem has been very confusing to me, and that is the concept of Circular ArrayDeque. In particular, how can we add or ...
  • 101
0 votes
0 answers
33 views

Isomorphism, one-to-one correspondence in Stack

From R C Lacher's slides on Data Structures, These axioms can be used to prove, among other things, that the stack is unique up to isomorphism: Given any two stacks on the same data type, there is a ...
4 votes
1 answer
89 views

Optimal algorithmic complexity of "a nonrepetitive stack"?

I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'. A ...
  • 1,319
0 votes
1 answer
116 views

Update a property of all objects in a List/Collection/Array when at least one object satisfies a criteria using a single loop

Here is the puzzle I was asked in an interview There's a List of Employee objects. Update all the objects in the list to be eligibleForHike if at least one employee exists whose salary is less than x; ...
1 vote
2 answers
126 views

How can we prove that "extract almost minimum" operation in a priority queue cannot be done in o(log n)?

Suppose we want to create a priority queue with 2 operations: insert and extract almost min. Extract almost min operation selects either the first minimum or a second minimum item from the structure ...
0 votes
1 answer
99 views

Time complexity analysis for Searching in a Hash table

I want to analyse the time complexity for Unsuccesful search using probabilistic method in a Hash table where collisions are resolved by chaining through a doubly linked list. And the doubly linked ...
0 votes
1 answer
32 views

Is it possible to decode an array stored in strings with constraint satisfaction?

I am currently experimenting on compression algorithms, I am using proven algorithms and I am just trying to see if I can make some things more efficient, so I am very sorry if this is a stupid ...
1 vote
1 answer
24 views

Dynamic Data Structure for Sliding Window of varying size with Predecessor queries

I was wondering if anyone can point me to a data structure that supports the following operations. Goal is to create a data structure $D$ that stores 64-bit integers and provides the following ...
  • 103
0 votes
1 answer
44 views

Are linked lists homogenious or heterogenious containers?

I have always assumed that "Linked List" is something in the lines of ...
  • 103
0 votes
0 answers
42 views

If you took the permutations of an array and heapified it, will you always get the same heap?

In other words, if I have 10 arrays each with 10 of the same values but scrambled their order and heapified them all, is it possible to have different results?
1 vote
2 answers
66 views

Algorithm to find if there exists an assignment such that all equality and inequality constraints are satisfied

I have a problem in a Data Structures course I am taking. The question is as follows: Given a number of variables $x_1,\dots,x_n$ and given $m$ equality and inequality constraints (in total $m$ ...
0 votes
0 answers
15 views

Data structure for tracking ordered sub-sequences of data [duplicate]

I'm looking for a data structure to help me solve the following problems: EDIT: This describes a skyline query. Given a set of points (x,y), find the subset of points where if you order strictly ...
  • 101
3 votes
3 answers
755 views

A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity

Why is Solution 1 faster than Solution 2? The input passed to both solutions: ...
1 vote
2 answers
479 views

Data structure to determine number of values less than an integer

Given an array of N integers, there may be a need to perform q queries. A query could be like determining the number of values that are less than an integer k. Which data structure could be used to ...
  • 19
0 votes
2 answers
123 views

Best data structures to store overlapping intervals?

I have different time intervals (contains partial or full overlaps). I provided the sample input and output so that it would be easy to understand. Sample Input-1: ...
0 votes
0 answers
29 views

Slot implementation of LRU cache

Usually LRU cache is implemented with double linked list to fast remove oldest visited, push to front, and move from any place to front; also uses map to fast find element by key. In 64bit systems ...
  • 141
1 vote
1 answer
43 views

Data Structure to Support Max Value of Keys Greater than Given Value

I want to support two operations: Insert a (key, value) pair into the data structure in $O(\log n)$ time. The key can be assumed to be a unique integer. Given an integer query value $v$, I want to ...
  • 113
1 vote
0 answers
36 views

Algorithm to recreate a Splay tree

Let's say I have some splay tree as following: I want to recrate the exact same Splay tree using insert(key) method. Is there an algorithm that given some Splay ...
  • 231
0 votes
0 answers
16 views

What is the depth of the tree after two operations if the tree uses the "Splay" heuristics?

Further to my previous question, I'm now trying to solve the same question but when the Splay action is involved: It is given that the current tree is a string of $n$ vertices, and a search operation ...
  • 231
0 votes
0 answers
25 views

What is the depth of the tree after two operations if the tree uses the "Move to Root" heuristics?

I'm preparing for my finals in "Advance Algorithms". I'm trying to solve the following question: It is given that the current tree is a string of $n$ vertices, and a search operation is ...
  • 231

1
2 3 4 5
42