0

I'm learning about memoization and although I have no trouble implementing it when it's needed in Python, I still don't know how to identify situations where it will be needed.

I know it's implemented when there are overlapping subcalls, but how do you identify if this is the case? Some recursive functions seem to go deep before an overlapping call is made. How would you identify this in a coding interview? Would you draw out all the calls (even if some of them go 5-6 levels deep in an O(2^n) complexity brute force solution)?

Cases like the Fibonacci sequence make sense because the overlap happens immediately (the 'fib(i-1)' call will almost immediately overlap with the 'fib(i-2)' call). But for other cases, like the knapsack problem, I still can't wrap my head around how anyone can identify that memoization should be used while at an interview. Is there a quick way to check for an overlap?

I hope my question makes sense. If someone could point me to a good resource, or give me clues to look for, I would really appreciate it. Thanks in advance.

rexorsist
  • 97
  • 5
  • 1
    This is not so black and white. Even when the function's time complexity is in O(1), you may still want to memoize it so that you don't perform same action twice if the function is called multiple times (e.g. billing your users twice in the same transaction). As for the interview question (which I am not a fan of), if your algorithm has exponential time complexity, that is a good sign for considering memoization (assuming the other conditions are met). Knapsack and fibonacci are toy examples so 'everyone' knows that you can implement memoization to make them 'kind of better'. – Matus Dubrava Jul 23 '20 at 20:30

1 Answers1

1

In order to reach the "memoization" solution, you first need to identify the following two properties in the problem:

  1. Overlapping subproblems
  2. Optimal substructure

Looks like you do understand (1). For (2):

Optimal Substructure: If the optimal solution to a problem, S, of size n can be calculated by JUST looking at optimal solution of a subproblem, s, with size < n and NOT ALL solutions to a subproblem, AND it will also result in an optimal solution for problem S, then this problem S is considered to have optimal substructure.

For more detail, please take a look at the following answer:

https://stackoverflow.com/a/59461413/12346373

aamir
  • 76
  • 1
  • 4