cppadvanced10 minutes

Implement a High-Performance Memoized Fibonacci Calculator in C++

Build a highly optimized C++ function to compute Fibonacci numbers using memoization to minimize time complexity for very large inputs without stack overflow or excessive memory usage.

Challenge prompt

Write a C++ function named `fib` that takes an unsigned 64-bit integer n and returns the nth Fibonacci number. Your implementation must use memoization to optimize repeated calls and handle inputs up to at least 10^7 efficiently. The function should avoid recursion depth issues and optimize memory usage. Implement your own caching mechanism without using global or static variables to ensure thread safety and reentrancy.

Guidance

• Use an efficient data structure such as an unordered_map or vector with dynamic resizing for caching intermediate results.
• Consider using an iterative approach combined with memoization to avoid deep recursion stack overflow.
• Design the cache to be local to the function or passed explicitly to maintain thread safety.
• Optimize memory usage by clearing unneeded cache entries dynamically if possible.

Hints

• Avoid naive recursion; combine iteration with memoization for better performance.
• Think about passing cache storage structures as function arguments or keeping them within a class.
• Carefully handle large data types since Fibonacci numbers grow exponentially; consider using a 64-bit integer for results.

Starter code

uint64_t fib(uint64_t n) {
    // Your memoized Fibonacci implementation here
    return 0;
}

Expected output

fib(10) = 55 fib(50) = 12586269025 fib(100) = 354224848179261915075

Core concepts

memoizationdynamic programmingoptimizationiterative algorithms

Challenge a Friend

Send this duel to someone else and see if they can solve it.