Question

Uber | OA Coding Questions and Solutions | Set - 11 | 2022

Answer 1

Given a string that represents a sms message and an integer k that represents some threshold, return a list of strings where each string represents an SMS message and ends with a signature indicating which text out of the total number of texts the current text is.

 

Words cannot be broken up.

 

Example
s = "I love leetcode"
k =10

Output: ["I love (1/2)", "leetcode (2/2)"]

Answer 2

def get_extra(k):
	return sum(len(s) for s in [f'<{i}/{k}' for i in range(1, k+1)])


def is_possible(text, k, limit):
	total_len = len(text) + get_extra(k)
	return total_len <= k*limit



def get_ans(text, limit):
	min_len = 4 + len(text)
	min_k = min_len // limit
	if min_k%min_len != 0:
		min_k += 1
	max_k = get_extra(len(text)) + len(text)
	ans = min_k
	while min_k < max_k:
		mid = (min_k + min_k) // 2
		if is_possible(text, mid, limit):
			ans = mid
			max_k = mid
		else:
			min_k = mid + 1
	start = 0
	msgs = []
	tmps = []
	for i in range(ans):
		suffix = f'<{i+1}/{ans}'
		end = start + limit - len(suffix)
		prefix = text[start:end]
		start = end
		tmps.append(prefix)
		msgs.append(f'{prefix}{suffix}')
	print(msgs)
	print(''.join(tmps) == text)
	return ans


def main():
	text = "dnutejogoweqebjzlhkbqqqdbkzylmbbifujihtqnqgydzwgclzlgurqvaczoruajnxninhavonpldztrybzrrgxaekzmhuedmrmibjeglollyoocmoouwxfqwzzfhvuncvlritfjhetfbhwjpjarpynvkmbaucqyhpbzgssnzonakefndfrzzrlmmgvkhganjkmaafnehmoebjpsvlmsdcilasmgjukvfxteivzxeptirvopnudlqrvdwcwurpioeblfkktritbngqnmnxknwbkllakaynxfrxznqnccwvxvrs"
	limit = 10
	print(len(text))
	print(get_ans(text, limit))
	return


if __name__ == "__main__":
	main()

 

Time Complexity: O(log(get_extra(len(text)) + len(text)))