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

learn more… | top users | synonyms (1)

-3
votes
1answer
22 views

Constructing binary search tree from given data

The data are in alphabets. U, N, I, V, E, R, S, I, T, Y, O, F, P, O, K, H, A, R, A. Perform pre, in and post order traversals. I'm confused as how to construct it in the 1st place. Only sense i ...
3
votes
1answer
49 views

Why do you need to fill the first element of array when implementing heap?

I'm looking at Heap data structure implementation from different sources. What I found is that sometimes it's implemented with the first element of array set to magic (default, unused?) value. For ...
1
vote
1answer
39 views

Are there data structures that mix a tree structure with lists?

I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data. Something like this (I'll be ...
2
votes
0answers
36 views

Large non-array data structure to describe order of elements

I'm looking to store the order of a series of elements and access the elements in "pages" (elements numbered 101-150, for example) as well as add and delete them. This is being implemented in a graph ...
-3
votes
0answers
18 views

which of the folowing statements is correct about the C program given below? [closed]

include int main() { int x=10; int y=100%90; for(i=1;i<=10;i++); if(x!=y); printf("x=%d y=%d\n",x,y); return (0); } A.the printf function is called 10 times. B.the program will produce ...
1
vote
1answer
48 views

Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
0
votes
2answers
64 views

Correct way to implement linked list

I'm doing this challenge on Hacker Rank that wants me to implement a linked list. It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. ...
1
vote
3answers
69 views

Zero-based array implementation with logarithmic insertion time

Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time. For a specific problem I was musing about a balanced tree that would allow for an zero-...
2
votes
2answers
265 views

Is this probability distribution data structure already discovered?

Problem formulation I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, ...
-1
votes
0answers
25 views

What's the time bound of an inorder traversal followed by a comparison?

I have the above question, and I plan on using an AVL tree to answer the question. The Insert(x) will be simple enough, simply using the default AVL tree insert. My question is for the $GreaterThan(x)...
1
vote
1answer
72 views

Is there a way to determine if a collection is a palindrome within a time bound?

I'm learning about data structures, and there's a problem where, given a collection of words $X = (x_1, x_2, \dots, x_n)$ (can include duplicates), I have to find out if it's a palindrome or not. I'm ...
-3
votes
1answer
49 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
2
votes
2answers
76 views

How can I get O(1) prepend on a random-access list?

I need a data structure that has the following operation: $\operatorname{prepend}([x_{n - 1}, ..., x_0], x_n) = [x_n, ..., x_0]$ $\operatorname{prepend}$ should be in $O(1)$. Assume that you have ...
1
vote
5answers
125 views

Why is b-tree search O(log n)?

B-tree is a data structure, which looks like this: If I want to look for some specific value in this structure, I need to go through several elements in root to find the right child-node. The I ...
0
votes
1answer
33 views

Complexity of testing membership in a disjoint set

I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node". I want to look up a node by value. How can I do this? The representations ...
-1
votes
0answers
29 views

Binary search trees - deleting elements

I received the following question. I terms of intuiton it feels very very wrong, but II've tried many examples and they didn't disprove this claim. Is it true or false, and how should i prove it? ...
0
votes
1answer
39 views

Where does the process reside in memory?

When a program runs in CPU, it turns into a process. In what kind of data structure is the process stored in a system memory? Heap or Tree or some other data structures?
0
votes
0answers
27 views

Linear hashing vs extendable hashing - memory

could you give me an example when linear hashing costs more memory than extendable hashing? And the other side, when extendable hashing takes more memory than linear hashing?
5
votes
1answer
128 views

Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $

Iv'e been struggling a lot with this one. I am looking for a data-structure (could be a modification of an existing type of data-structure, or a combination of more than one data-structure), which ...
-1
votes
1answer
31 views

Priority Queue using an AVL tree, run time question

This is a question I want to answer in pseudocode: This is regarding a sort of priority queue using an AVL tree. I initialize a global variable (named GLOB) with 0. I receive from the user an input ...
1
vote
1answer
33 views

Wikipedia does not list insertion complexity for arrays - why?

Wikipedia does not list insertion complexity for arrays in the list of linked-list implementations. Is this because insertion operations are not defined on the array ADT?
0
votes
0answers
23 views

T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(log n)? [duplicate]

how can i prove that T(n)=T(n-2)+T(n-3)+T(n-4)+2 is O(logn)? or T(n)=T(n-1)+T(n-3)+1 the same.. when T(0)=1 T(1)=2 T(2)=3 T(3)=5 T(4)=8 etc`.. it's a Q about AVL-2 tree,the same rules of AVL tree ...
0
votes
0answers
24 views

How to ensure that no manipulation to data records has been made

Let's say I have a transaction history, like this: Transaction #1: Add 5 Transaction #2: Add 8 Transaction #3: Remove 2 Transaction #4: Cancel Transaction #2 Is ...
1
vote
1answer
35 views

Why does Skiena reserve space for n+1 adjacency lists? [closed]

I am reading up on graph theory from the book Algorithm Design Manual - Skiena. And he shows a structure of a graph as follows : ...
1
vote
1answer
73 views

improving java 8's implement to hash map using avl tree

Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup. Will changing this implement to an avl tree change this O(n) case to ...
1
vote
0answers
23 views

What is the psuedo-code for Tremaux's Algorithm as a Depth First Search to solve a maze?

I was interested in the Tremaux Algorithm as a Depth First Search to solve a Maze. Unfortunately I was not able to understand what Data Structures are and how they could be used. For example, I saw a ...
1
vote
0answers
21 views

Resources to learn about distributed data structures? (DHT, Merkle Tree, etc.)

I'm having a hard time finding comprehensive literature on distributed / p2p data structures... for example, I have found the book "Handbook of Peer-to-Peer Networking", which seems to be what I want (...
3
votes
0answers
30 views

Are there any practical drop-in replacements for BSTs in the case where data are integers?

There are a number of specialized data structures that implement ordered dictionaries for integer keys: van Emde Boas trees, y-Fast tries, fusion trees, etc. Each of these data structures implement ...
0
votes
0answers
39 views

Succinct Data-Structures [duplicate]

What is a possible data structure $X$ which stores non-negative integers $x_1, x_2, ..., x_n$ which supports the following operations: $index(k, X)$ returns the biggest $i$ so that $\sum_{i=1}^n x_i ...
1
vote
0answers
19 views

Succinct Data-Structures [closed]

I can't find a data structure which stores an ordered list of non-negative integers $X=(x_1,\ldots,x_n)$ with the following operations: $\mathrm{Index}(k, X)$ returns the largest $i$ such that $x_1+...
3
votes
0answers
33 views

Data Structure for k Nearest Neighbour Search in D dimension using only point cloud as query points

I have a point cloud of N points in D-dimensional space with periodic boundary conditions, where N can range from 500 to 10^8 and D can range from 1 to 20. The distribution of points varies wildly, ...
1
vote
1answer
50 views

Why isnt node checked for nil value in start when transplanting binary tree

Whilst I was reading CLRS I came across this: When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends ...
1
vote
1answer
50 views

What exactly (and precisely) is “offset”?

Just like my previous question concerning 'hash'; what exactly is an (or the) "offset?" Is it a value or data type? Or is it an address location? I have heard it used in different contexts within the ...
2
votes
1answer
41 views

How to construct a running kd-tree?

I have a stream of 3-tuples of type (x,y,t) where x and y are in the range ...
0
votes
1answer
27 views

Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

In Python's implementation of $k$-$d$ tree it is possible to manually change the norm used for computing distances from $L^2$ to $L^p$. When would one use a norm other than $L^2$ in a $k$-$d$ tree?
1
vote
0answers
29 views

Trying to understand a way to split an AVL tree in O(log n)

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn ...
0
votes
0answers
21 views

On an AVL tree insertion/deletion, which nodes have their height changed and why?

I've begun learning about AVL trees. It seems that the assertion with this data structure is that with every insertion/deletion, the only nodes whose height changes are nodes on the path towards the ...
3
votes
1answer
228 views

What is the difference between a R-tree and a BVH?

I've just read about R-Trees: The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" ...
0
votes
0answers
22 views

RMQ with single index update in array

Range Minimum Query (RMQ) can be solved in (O(n), O(1)) if the array is known to be static by dividing it into blocks and then using Cartesian tree numbers to detect "similar" blocks. Link: http://...
10
votes
7answers
2k views

How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
1
vote
0answers
18 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
-3
votes
1answer
33 views

Virtual address lookup without using all the space to store the physical addresses [closed]

How is a virtual address mapped to a physical address? The most logical solution I, with my meager knowledge, can think of would be to actually store the physical address. The problem with the above ...
5
votes
1answer
99 views

Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$. Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but ...
0
votes
0answers
41 views

minimum and maximum number of internal nodes for given number of leaves in 2-3 tree

I came across following question: Suppose a 2-3 tree has 19 leaves. What are the largest and smallest numbers of interior nodes the tree may have? Identify the correct value for minimum or maximum,...
0
votes
0answers
15 views

Reverse linked list set logic in method B

I am trying to describe a reverse linked list in the B method. The structure I am trying to describe is below: F <- 1 <- 2 <- ... <- x <- L where ...
0
votes
0answers
44 views

Find keys between $x$ and $y$ in binary search tree

Given $x$ and $y$, I want to find keys $k$ such that $x<k<y$, in a binary search tree. Can this be done in time $O(n + h)$, where $n$ is the number of keys between $x$ and $y$, and $h$ is the ...
3
votes
0answers
24 views

How to realize a distributed queue with unreliable participants?

I want to build an application that relies on a distributed queue with participants in a decentralized (peer-to-peer) network. The participants cannot be relied on to correctly follow a protocol. I ...
0
votes
0answers
34 views

joining of binary trees

Suppose we have a set of binary trees with their inorder and preorder traversals given, and where no tree is a subtree of another tree in the given set. Now another binary tree $Q$ is given. Find ...
-1
votes
3answers
91 views

Terminology for trees

In a tree, I want to refer to a particular child of a node, the child of this child, the child of this child of this child, and then the child of this child of this child of this child. For instance, ...
3
votes
2answers
202 views

Is it admited to give the complexity of a function regarding the resulting data structure?

Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$. The time complexity of $...