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.

	'''
	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 n th word ignoring the whitespaces
	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
	'''
	class Node:
	def __init__(self, c, pos):
	self.word = c
	self.s= self.e = pos
	self.p = self.l = self.r = None
	def insert(self, c, pos):
	if pos == self.s:
	self.word = c + self.word
	elif pos == self.e+1:
	self.word = self.word + c
	else:
	# insert in the middle
	relative_pos = pos - self.s
	self.word = self.word[:relative_pos] + c + self.word[relative_pos:]
	self.e+=1
	def increment(self):
	self.s +=1
	self.e +=1
	def split(self, pos):
	relative_pos = pos - self.s
	later = Node(self.word[relative_pos:], pos)
	later.e = self.e
	self.word = self.word[:pos]
	self.e = pos - 1
	return later
	def __str__(self):
	return "[v:{}, s:{}, e:{}]".format(self.word, self.s, self.e)
	class BigString:
	def __init__(self):
	self.root = None
	def _increment(self, cur: Node):
	if cur is None:
	return
	cur.increment()
	self._increment(cur.l)
	self._increment(cur.r)
	def _increment_right_side(self, cur:Node):
	if cur.p and cur.p.l == cur:
	# increment the parent and call _increment on p.r
	cur.p.increment()
	self._increment(cur.p.r)
	self._increment(cur.r)
	def insert(self, c, pos):
	if self.root is None:
	self.root = Node(c, pos)
	else:
	self._insert(self.root, None, False, c, pos)
	def add(self, node: Node):
	if self.root is None:
	self.root = node
	else:
	cur = self.root
	prev = None
	is_left = False
	while (cur != None):
	prev = cur
	if node.e < cur.s:
	cur = cur.l
	is_left = True
	else:
	cur = cur.r
	is_left = False
	node.p = prev
	if is_left == True:
	prev.l = node
	else:
	prev.r = node
	def _insert(self, cur:Node, prev:Node, isLeft, c, pos):
	# reached the leaf
	if cur is None:
	if c != ' ': # c is not blank
	new_node = Node(c, pos)
	new_node.p = prev
	if isLeft is True:
	prev.l = new_node
	else:
	prev.r = new_node
	self._increment_right_side(new_node)
	else: # c is blank. simple increment prev
	self._increment(prev)
	return
	# adding in the middle of existing node. a.k.a expanding node.
	if cur.s <= pos and pos <= cur.e +1:
	if c != ' ':
	cur.insert(c, pos)
	else: # c is blank
	# adding blank in the front.
	if cur.s == pos:
	cur.increment()
	elif pos <= cur.end:
	# adding blank in the middle.
	splited = cur.split(pos)
	self.add(splited) # add the node and take care of increments.
	self._increment_right_side(cur)
	elif pos < cur.s:
	self._insert(cur.l, cur, True, c, pos)
	else:
	self._insert(cur.r, cur, False, c, pos)
	def search(self, index):
	found = self._indorder_search(self.root, index, [])
	return found.word if found is not None else None
	def _indorder_search(self, cur:Node, index, queue):
	if cur == None:
	return None
	found = self._indorder_search(cur.l, index, queue)
	if found != None:
	return found
	# print("adding {}".format(cur))
	queue.append(cur)
	if index != -1 and len(queue) -1 == index:
	return cur
	return self._indorder_search(cur.r, index, queue)
	def __str__(self):
	output = []
	self._indorder_search(self.root, -1, output)
	result = ""
	last_pos = None
	for i in range(len(output)):
	next = output[i]
	if last_pos is None:
	num_whitespace = next.s
	elif last_pos < next.s:
	num_whitespace = next.s - last_pos - 1
	for i in range(num_whitespace):
	result = result + " "
	result = result + next.word
	last_pos = next.e
	return result
	print("insert test")
	big_string = BigString()
	big_string.insert('a', 0) #[a]
	print (big_string)
	big_string.insert('b', 0) #[ba]
	print (big_string)
	big_string.insert(' ', 0) #[ ba]
	print (big_string)
	big_string.insert('c', 0) #[c ba]
	print (big_string)
	big_string.insert('e', 11) #[c ba e]
	print (big_string)
	big_string.insert('f', 8) #[c ba f e]
	print (big_string)
	big_string.insert('o', 3) #[c boa f e]
	print (big_string)
	big_string.insert('u', 10) #[c boa fu e]
	print (big_string)
	print("search test")
	print(big_string.search(0))
	print(big_string.search(1))
	print(big_string.search(2))
	print(big_string.search(3))

view raw google_big_string.py hosted with ❤ by GitHub

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.

	class Word:
	def __init__(self, c = ''):
	self.value = c
	class BigString:
	def __init__(self):
	self.list = []
	# O(N)
	def insert(self, c, pos):
	#check if pos exists
	if pos < len(self.list):
	if c == ' ' and pos == 0:
	self.list = [Word()] + self.list
	else:
	#case 1, pos is within the word, just insert
	if pos < len(self.list[pos].value):
	self.list[pos].value = self.insert_into_word(c, self.list[pos].value, pos)
	#case 2, pos is outside of word, add blank words before a new word with c
	else:
	for i in range()
	self.list[pos].value = c + self.list[pos].value
	else: # beyond current length, fill the gap with blank words
	for i in range(pos - len(self.list)):
	self.list.append(Word())
	self.list.append(Word(c))
	def insert_into_word(self, c, word, pos):
	return word[:pos] + c + word[pos:]
	# O(N)
	def to_string(self):
	result = ''
	for w in self.list:
	result = result + w.value +' '
	return result
	# O(1)
	def search(self, pos):
	if len(self.list) < pos:
	return None
	return self.list[pos]
	b = BigString()
	b.insert('a', 0)
	print(b.to_string())
	b.insert('b', 0) # [ba]
	print(b.to_string())
	b.insert(' ', 0) # [ ba]
	print(b.to_string())
	b.insert('c', 0) # [c ba]
	print(b.to_string())
	b.insert('e', 11) # [c ba e]
	print(b.to_string())
	b.insert('f', 8); # [c ba f e]
	print(b.to_string())
	print(b.search(0).value) # c
	print(b.search(1).value) # ba
	b.insert('d', 2) #[c ba d f e]
	print(b.to_string())

view raw big_string_v1.py hosted with ❤ by GitHub

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