Bloomberg | Onsite | London | Feb 2022 | Collatz Conjecture [Passed]
Anonymous User
2483
BacktrackingMemoizationBloombergInterview

Just got around to writing about my experience at the virtual onsite interview. I was given the same question as listed here, but was asked to come up with an iterative approach which implements backtracking as a means to memoize intermediate numbers. Here is what I came up with.

An iterative approach with memoization

class CollatzConjecture:

	def _init_(self):
		self.cache = {1:0}

	  

	def calculateSteps(self, number):

		if number < 1:
			raise Exception('Number is not valid')

		origin = number
		numbersEncountered = []
		  
		while origin != 1:
			if origin in self.cache:
				break
		  
			numbersEncountered.append(origin)
			  
			if origin % 2 == 0:
				origin = origin // 2
			else:
				origin = (origin * 3) + 1

		  
		backtrackedSteps = self.cache.get(origin, 0) + 1
		while numbersEncountered:
			value = numbersEncountered.pop()
			self.cache[value] = backtrackedSteps
			backtrackedSteps += 1

		return self.cache[number]
Comments (4)