Algorithmsmedium

What is memoization and when does it help?

Answer

Memoization caches results of a function for given inputs, so repeated calls reuse the cached value. It helps when you have overlapping subproblems (common in dynamic programming) and the same states are computed many times.

function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

Advanced answer

Deep dive

Expanding on the short answer — what usually matters in practice:

Context (tags): memoization, dynamic-programming, cache
Complexity: compare typical operations (average vs worst-case).
Invariants: what must always hold for correctness.
When the choice is wrong: production symptoms (latency, GC, cache misses).
Explain the "why", not just the "what" (intuition + consequences).
Trade-offs: what you gain/lose (time, memory, complexity, risk).
Edge cases: empty inputs, large inputs, invalid inputs, concurrency.

Examples

Here’s an additional example (building on the short answer):

function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

Common pitfalls

Too generic: no concrete trade-offs or examples.
Mixing average-case and worst-case (e.g., complexity).
Ignoring constraints: memory, concurrency, network/disk costs.

Interview follow-ups

When would you choose an alternative and why?
What production issues show up and how do you diagnose them?

Related questions

Algorithms

What does the Floyd–Warshall algorithm compute and what is its complexity?

#graphs#shortest-path#floyd-warshall

Algorithms

Top-down vs bottom-up dynamic programming — what’s the difference?

#dynamic-programming#memoization#tabulation

Algorithms

What does Kadane’s algorithm solve?

#kadane#dynamic-programming

Answer

function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

Advanced answer

Deep dive

Expanding on the short answer — what usually matters in practice:

Context (tags): memoization, dynamic-programming, cache
Complexity: compare typical operations (average vs worst-case).
Invariants: what must always hold for correctness.
When the choice is wrong: production symptoms (latency, GC, cache misses).
Explain the "why", not just the "what" (intuition + consequences).
Trade-offs: what you gain/lose (time, memory, complexity, risk).
Edge cases: empty inputs, large inputs, invalid inputs, concurrency.

Examples

Here’s an additional example (building on the short answer):

function fib(n: number, memo = new Map<number, number>()): number {
  if (n <= 1) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;

  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

Common pitfalls

Too generic: no concrete trade-offs or examples.
Mixing average-case and worst-case (e.g., complexity).
Ignoring constraints: memory, concurrency, network/disk costs.

Interview follow-ups

When would you choose an alternative and why?
What production issues show up and how do you diagnose them?