CODEWITHSUNDEEP
optimizationdata-structures
Vikram
Vikram

Reputation: 509

Design a highly optimized datastructure to perform three operations insert, delete and getRandom

I just had a software interview. One of the questions was to design any datastructure with three methods insert, delete and getRandom in a highly optimized way. The interviewer asked me to think of a combination of datastructures to design a new one. Insert can be designed anyway but for random and delete i need to get the position of specific element. He gave me a hint to think about the datastructure which takes minimum time for sorting.

Any answer or discussion is welcomed....

Upvotes: 1

Views: 1135

Answers (5)

vasste
vasste

Reputation: 56

It might be Heap (data structure)

Upvotes: 0

jrouquie
jrouquie

Reputation: 4415

Let t be the type of the elements you want to store in the datastructure. Have an extensible array elements containing all the elements in no particular order. Have a hashtable indices that maps elements of type t to their position in elements.

  • Inserting e means
    • add e at the end of elements (i.e. push_back), get its position i
    • insert the mapping (e,i) into `indices
  • deleting e means
    • find the position i of e in elements thanks to indices
    • overwrite e with the last element f of elements
    • update indices: remove the mapping (f,indices.size()) and insert (f,i)
  • drawing one element at random (leaving it in the datastructure, i.e. it's peek, not pop) is simply drawing an integer i in [0,elements.size()[ and returning elements[i].

Assuming the hashtable is well suited for your elements of type t, all three operations are O(1).

Be careful about the cases where there are 0 or 1 element in the datastructure.

Upvotes: 3

Algorist
Algorist

Reputation: 492

What I feel is that you can use some balaced version of tree like Red-Black trees. This will give O(log n) insertion and deletion time. For getting random element, may be you can have a additional hash table to keep track of elements which are in the tree structure.

Upvotes: 0

user82238
user82238

Reputation:

The data structure which takes the least time for sorting is sorted array.

get_random() is binary search, so O(log n).

insert() and delete() involve adding/removing the element in question and then resorting, which is O(n log n), e.g. horrendous.

I think his hint was poor. You may have been in a bad interview.

Upvotes: 0

Alex Wilson
Alex Wilson

Reputation: 6740

A tree might work well here. Order log(n) insert and delete, and choose random could also be log(n): start at the root node and at each junction choose a child at random (weighted by the total number of leaf nodes per child) until you reach a leaf.

Upvotes: 2

Related Questions