Collatz Conjecture with Shared Memoization
Reported by candidates from Bloomberg's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Bloomberg reportedly served this Collatz step-count question in October 2022, and the edge case that kills a naive solution is hiding in plain sight: intermediate values blow far past the input range. If you cache only the queried numbers, you redo the same chains again and again. If you use a plain array sized to 10^6, you crash the first time 3n+1 jumps over it. The real task is memoization shared across the whole batch, with nonpositive inputs returning "null". If you blank during the OA, StealthCoder is the safety net running invisibly on your screen.
The problem
For each value in queries, return its Collatz step count as a decimal string. For a positive value n, repeatedly apply: If n is even, replace it with n / 2. If n is odd, replace it with 3n + 1. The step count is the number of replacements required to reach 1. For a nonpositive query, return "null". Process queries in order and share memoized results, including intermediate values, across the batch. Function collatzSteps(queries: long[]) → String[] Examples Example 1 queries = [5,8,4,-3] return = ["5","3","2","null"] 5 -> 16 -> 8 -> 4 -> 2 -> 1 takes five steps. Later queries reuse cached suffix counts. The negative query returns null. Example 2 queries = [1,2,3] return = ["0","1","7"] One is already complete; two takes one step; three follows 3,10,5,16,8,4,2,1. Constraints 1 <= queries.length <= 10^4. -10^6 <= queries[i] <= 10^6. For the positive range above, every intermediate value fits in a signed 64-bit integer.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is a hash map from value to step count, filled as you go. Walk the chain from n until you hit 1 or a cached value, pushing each visited number onto a stack or list. Then unwind backward, assigning each number its successor's count plus one. That caches every intermediate value, which is exactly what the problem asks for. The pitfall is the type. Use 64-bit longs, because the chain values exceed 32-bit range even though inputs stay under 10^6. Another trap is an array cache indexed by value, which fails once the chain exceeds your bounds. Handle n <= 0 first and return "null" as a string, not a null reference. Output counts as decimal strings. Recursion depth can get ugly, so iterate. If the unwinding logic slips under pressure, StealthCoder can hand you a working version live during the OA.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill Collatz Conjecture with Shared Memoization cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Bloomberg's OA.
Bloomberg reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Collatz Conjecture with Shared Memoization FAQ
What's the trick in the Bloomberg Collatz memoization problem?+
Cache every number you touch along the chain, not just the queried ones. Use a hash map from value to steps. Walk until you reach 1 or a cached value, then fill counts backward. Later queries then reuse long suffixes instead of recomputing them.
Why can't I just use an array for the cache?+
Inputs are capped at 10^6, but 3n+1 pushes intermediate values well above that. An array indexed by value will go out of bounds or waste memory. A hash map keyed by long handles any intermediate value safely. You could mix both, but a map is simpler.
How should I handle nonpositive queries?+
Check before any Collatz logic. If the query is zero or negative, output the literal string "null" at that position. Zero would loop forever if you let it through, and negatives never reliably reach 1. Keep output order matching input order.
Should I use recursion or iteration?+
Iteration is safer. Chains can run a few hundred steps, and recursion adds stack risk and overhead. Collect the path in a list until you hit a known value, then loop backward assigning counts. It's also easier to debug when a test fails.
How do I prepare for this in 48 hours?+
Write the solution once from scratch with a map and a path list. Test it on [5,8,4,-3] and [1,2,3]. Check the long type, the base case of 1 equal to 0 steps, and string output. That covers nearly every way this problem goes wrong.