Case study: remove k digits - brute force solution time complexity O(kn)

Dec. 31, 2019

I like to write down a short case study on this mock interview.

Case study

	def removeKdigits(num: str, k: int) -> str:
	if len(num) <= k:
	return 0
	digits = list(map(int, num))
	for i in range(k):
	removed = False
	for j in range(len(digits) - 1):
	if digits[j] > digits[j + 1]:
	digits.remove(digits[j])
	removed = True
	break
	if not removed:
	digits.pop()
	return ''.join(list(map(str, digits)))
	print(removeKdigits("1432219", 3))
	print(removeKdigits("10200", 1))
	print(removeKdigits("10", 2))

view raw removeKDigits.py hosted with ❤ by GitHub

Actionable Items

Compared to the interviewee, I spent over 40 minutes to solve remove k digits in weekly contest, and then it took me another hour to write a brute force solution. In other words, I should learn from SDE II engineer in Seattle, and see how he approached the problem and solved it in less than 15 minutes. 

Here is my discussion post.