Memoize an expensive lookup function

Python data engineering interview problem. Difficulty: intermediate. Pattern: Recursion. About 15 minutes. Part of the Pro drill bank.

An expensive lookup (here, a Fibonacci-style recurrence) is called with the same n many times. Memoization should make repeated calls cheap.

Some calculations call themselves many times with the same input. Storing results the first time (memoization) turns slow code into fast code. Return the nth Fibonacci number, where fib(0) = 0, fib(1) = 1 and every other number is the sum of the two before it. Use a dictionary to remember results so each value is computed once. Write fib_memo(n). fib_memo(0) is 0 and fib_memo(1) is 1. For larger n, like fib_memo(10), the answer is 55. The starter file already has the function name and its print lines. Keep them and fill in the body.

Requirements

• Return 0 for n = 0 and 1 for n = 1.
• Otherwise add the previous 2 values.
• Remember results so no value is computed twice.

Constraints

• n is a whole number, 0 or more.
• The call must not take exponential time.

Examples

Input: fib_memo(0) Output: 0 This input follows the stated rules and produces this output.

Topics: lakebench, python, decorators.

More Python interview questions · All interview problems · Learn data engineering