Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Data structure that allows accessing elements by index and delete them in O(1)

Tags:

algorithm

I have following task (as part of bigger task):

I need to take an k element from array like data structure and delete it (k is any possible index). Array have O(n) for deleting elements, and List have O(n) for searching element. I would like to do both operations in O(1) time.

Which data structure should I use to meet this requirement?

Clarification:

Deleting element on index(5) will move element from index(6) to index(5).

This particular task is topcoder srm 300 div2 500 points problem. It does not require such sophisticated data structure (simple java methods will do the job since max data is really small), but I am curious how to deal with much bigger problem using c-like thinking about data.

So maybe I am sticked to much to array for this problem? But I will analyze it and edit question later, after work (if you are really curious, you can see task on top coder).

like image 711
Sławosz Avatar asked Aug 05 '13 07:08

Sławosz


People also ask

Which data structure can remove in O 1 time?

Answer: Answer:Deleting the top element of a stack is O(1), which is valid because you only have access to the top of the stack. Hash tables also have amortized O(1) deletion for any element of the table.

What is O 1 in data structure?

O(1) — Constant Time Constant time algorithms will always take same amount of time to be executed. The execution time of these algorithm is independent of the size of the input. A good example of O(1) time is accessing a value with an array index.

Which data structure allows elements to be inserted or deleted only from one end?

Stack is a linear data structure in which the insertion and deletion operations are performed at only one end. In a stack, adding and removing of elements are performed at single position which is known as "top".

What is O n in data structure?

O(n) Called “O of n” or Linear Time. As more items are added to the array in an unsorted fashion, it takes a corresponding linear amount of time to perform a search. e.g. Insertion & Deletion in an array.


2 Answers

I believe what you're asking for is impossible.

However, if you can relax your requirement for indexing to O(log n), then ropes may be able to satisfy it, although I'm not sure if they have a probabilistic or deterministic guarantee (I think it's probabilistic).

like image 175
user541686 Avatar answered Sep 21 '22 16:09

user541686


Given the nature of the "dating" problem as given, it involves continuously choosing and removing the "best" member of a set--a classic priority queue. In fact, you'll need to build two of those (for men and women). You'll either have to build them in O(NlogN) time (a sorted list) for constant O(1) removal, or else build them in linear time (a heap) for O(logN) removal. Overall you get O(NlogN) either way, since you'll be removing all of one queue and most of the other.

So then the question is what structure supports the other part of the task, choosing the "chooser" from the circle and removing him and his choice. Since this too must be done N times, any method that accomplishes the removal in O(logN) time won't increase the overall complexity of your algorithm. You can't get O(1) indexed access with fast deletions given the re-indexing requirement. But you can in fact get O(logN) for both indexed access and deletion with a tree (something like a rope as mentioned). This will give you O(NlogN) overall, which is the best you can do anyway.

like image 22
Lee Daniel Crocker Avatar answered Sep 22 '22 16:09

Lee Daniel Crocker