How many distinct ways can you climb n stairs taking 1 or 2 steps at a time?
Reported in HelloFresh European engineering loops. Introductory dynamic programming problem isomorphic to Fibonacci.
Interview scenario
Often asked in HelloFresh loops at European offices (London, Berlin, Amsterdam, Paris, Stockholm, Dublin, and remote EU). Prepare a clear spoken answer plus key trade-offs.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at HelloFresh: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Define dp[i] = ways to reach step i. From step i you arrive from i-1 or i-2, so dp[i] = dp[i-1] + dp[i-2] with base dp[0]=1, dp[1]=1.
def climbStairs(n: int) -> int:
if n <= 1:
return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bTime O(n), space O(1) with rolling variables. Recognize Fibonacci structure—interviewers may ask for general k steps or memoized recursion top-down.
DP checklist: state definition, transition, base cases, iteration order, and optimization. Extension: climb with cost on steps (min cost path) uses different recurrence.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.