Was asked to code Collatz Conjecture.
After a simple iterative solution, I was asked to optimize it for frequent calls. But without recursion. I could not provide the correct implementation. I thought of keeping a dict with all numbers (and their counts) encountered so far and then increment each of their count by 1, when an operation is done on current number. But that didn't seem right. Interviewer provided no hint or guidance.
Asked chatGPT after the interview and this is the result, which may or may not be correct. We could get stuck in a loop so need to exit in such a case.
def collatz_memoization(n, memo={}):
"""Implement the Collatz conjecture with memoization for a given number."""
sequence = []
while n not in memo and n != 1:
sequence.append(n)
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
# If we reached a number already in memo, use the memoized sequence
if n in memo:
sequence.extend(memo[n])
else:
sequence.append(1)
# Update the memo dictionary with the current sequence
for i, num in enumerate(sequence):
memo[num] = sequence[i:]
return sequence
# Example: Applying the Collatz conjecture to the number 6 with memoization
result = collatz_memoization(6)
print(result)Comments (1)