DSA interview question

Introduction to DP (Memoization, Tabulation, Space Optimization)

Easy · Algorithms · Topics: dynamic programming, theory

The problem

You're mentoring a junior engineer who keeps writing painfully slow recursive solutions that time out on moderately sized inputs. Rather than jumping straight to a specific problem, you decide to teach them the three-step framework every DP problem follows, using the simplest possible example — computing the nth Fibonacci number — to demonstrate the progression from naive recursion, to memoization (top-down DP), to tabulation (bottom-up DP), to fully space-optimized DP. Your task: implement all four stages for Fibonacci, and be ready to explain the why behind each transformation, since this same progression applies to virtually every DP problem you'll encounter.

Example: fib(5) = 5 (sequence: 0, 1, 1, 2, 3, 5).

Function signature

int fibRecursive(int n);                          // Stage 1: naive recursion
int fibMemoization(int n, vector<int>& memo);      // Stage 2: top-down DP
int fibTabulation(int n);                          // Stage 3: bottom-up DP
int fibSpaceOptimized(int n);                      // Stage 4: O(1) space DP

Test cases

Input `n`	Output	Explanation
0	0	Base case
1	1	Base case
2	1	fib(1) + fib(0) = 1 + 0
5	5	Sequence: 0,1,1,2,3,5
10	55	Standard Fibonacci value
40	102334155	Demonstrates why naive recursion becomes infeasible (exponential blowup) at this size

(Confirm: n is non-negative; this same 4-stage framework generalizes to any DP problem, not just Fibonacci.)

How interviewers phrase it

Rarely asked as a standalone problem in a real interview — instead, this framework is something you're expected to already know and apply when solving any DP problem. Interviewers assess it implicitly by watching how you approach problems like Climbing Stairs, House Robber, or Frog Jump.
Sometimes explicitly asked in a theory/discussion round: "Walk me through how you'd approach a DP problem from brute force to optimized solution."
Occasionally used as a warm-up: "Implement Fibonacci three different ways and explain the trade-offs" — testing whether you understand why each optimization matters, not just that you can code Fibonacci.

Clarifying questions to ask

Are they looking for a specific problem solved with this framework, or a general explanation of the three techniques?
Should I implement all three approaches (recursion+memo, tabulation, space-optimized), or just demonstrate understanding verbally?
Is there a specific problem in mind that this is leading up to, so I can tailor my explanation to that problem's shape (linear DP, grid DP, subsequence DP, etc.)?

Follow-ups to expect

"What's the difference between memoization and tabulation?"
"When would you prefer memoization over tabulation, or vice versa?"
"How do you identify if a problem can be solved with DP?"
"Can you always space-optimize a DP solution?"
"What's the time/space trade-off across the three approaches?"
"Can every recursive solution be converted to DP?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview