Design the BigString class

Problem [Revised]

Design the BigString class which has the following public methods

// method to add char to the word at the specified index.

void insert (char c, int pos)

{

  //

}

//method to return the word at the specified index.

word * search(int index)

{

//

}

Example)

insert('a', 0); ==> [a]

insert('b', 0); ==> [ba]

insert(' ', 0); ==> [ ba]

insert('c', 0); ==> [c ba]

insert('e', 11) ==> [c ba       e]

insert('f', 8); ==> [c ba    f   e]

insert('o', 3)  ==> [c boa    f   e]

insert('u', 10) ==> [c boa    fu   e]

search(0) ==>  c

search(1) ==>  boa

search(2) ==>  fu

search(3) ==>  e

UPDATE(2023-02-20): After searching for a similar question, I found that the original question was confusing and the examples were incorrect.  

There was a similar but slightly different question found in the leet code.

People talked about using Rope data structure and range binary search tree

I decided to go with the range binary tree idea.

This implementation is built on the following assumptions:

• insert() operation always inserts the char in the given position in the string whether it is a char or whitespace.
• search(i) operation returns the word, not the char and the position is not the position in the string. It is the ith order from the beginning of a string.

This range tree-based algorithm has the following time complexity, where N is the length of the big string and M is the number of words within the string.

•  insert operation: $O(M)$, where M is the number of words in the string. In the worst case where there are char and whitespace alternates, M will be close to N thereby $O(M) \approx O(N)$. However, M will be much smaller than N in reality.
• Search operation: $O(M)$, where M is the number of words in the string.

Overall performance will be better than using a string array for the implementation, where $O(N)$ is the time complexity for both insert and search.

Here is the first (in 4 years!!) working solution in python.

Prior unsuccessful attempts.

UPDATE(2019-07-21): resolved this problem again. But I wasn't sure about the example for the question. It is unclear at this point if the example is correct. It is misleading. 

I solved this problem again based on the following assumptions:

Assumptions made:

• parameter 'pos' of insert(c, pos) refers to the postion of word in the BigString.
• when a character is added it is added to the front of the word at position, 'pos'

Here is the python solution with $O(N)$ for insert and $O(1)$ for search.

Practice statistics:

16:00: to write up the algorithm

14:00: write up the code with an incomplete test case

5:00: to fix up the test case