0

I am required to implement two operations below with performance constraints,

  /** insert a character, c at a given position, pos **/
    void insert(char c, int pos);

  /** return the current character at given position, pos **/
    char query(int pos);

Both of these functions can be called 10^8 times :(. Inserting new value at any position will change/increase all of positions of its right parts elements.

At first, I was thinking to implement with Array but that costs a lot in worst case insert(), because every time I need to shift right part of the array when I insert new value somewhere at the beginning of the Array.

Then I was thinking to implement with Linked List, but this has the same cost for query() function because, to get the actual value I must move forward/backword of the linked list.

I wonder if there is any well known algorithm or data structure which can be helpful in this situation.

Update #1:

Similar question was posted here (Data structure: insert, remove, contains, get random element, all at O(1)) before,

but hash is not feasible for this problem because of frequent collisions when the value is of char type. There can be only 26 char in 10^8 positions. Also I don't need to solve in O(1) because this problem seems not solvable in O(1) by its nature. I want some trade of or hybrid solution where worst case of array and linkedlist will be minimized.

As @DAIe mentioned in comment I need some string like operations. Moreover, insert to position operation is not a hashtable operation at all.

Sazzad Hissain Khan
  • 37,929
  • 33
  • 189
  • 256
  • 1
    have you check this https://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1 – thebenman Oct 31 '17 at 07:51
  • @thebenman the problem is different. Hash is not possible when the value is char type. moreover I don't need O(1) solution. – Sazzad Hissain Khan Oct 31 '17 at 08:02
  • You certainly can use hash data structure with char data type. Also if you call it 10^8 times having `O(1)` can make significant improvements. – thebenman Oct 31 '17 at 08:07
  • 2
    @thebenman, `insert to position` operation is not a hashtable operation at all – DAle Oct 31 '17 at 08:10
  • 1
    @SazzadHissainKhan, please, add to the question the clarification about where do you need to insert/query character – DAle Oct 31 '17 at 08:14
  • @DAIe I edited the question. I don't know why people are marking as duplicated. – Sazzad Hissain Khan Oct 31 '17 at 08:17
  • The last question to clarify. Does insert operation to position `pos` change all positions of characters with positions `>= pos`? (Like in the string insert operation) – DAle Oct 31 '17 at 08:40
  • @DAle yes off course – Sazzad Hissain Khan Oct 31 '17 at 08:42
  • @SazzadHissainKhan, that is the thing that is not clear from the question, and that's why hashtable comments appeared – DAle Oct 31 '17 at 08:44

1 Answers1

4

There is a rope data structure. It is a balanced binary tree with leaf nodes containing short strings.

enter image description here

It has O(log(n)) worst-case query operation and O(log(n)) average time insert operation.

DAle
  • 8,990
  • 2
  • 26
  • 45