Quick Overview

This Coding & Algorithms question evaluates recursion and dynamic programming concepts by asking for the count of distinct ways to climb n steps, framed at an algorithmic/implementation level. It is commonly asked because it probes recognition of overlapping subproblems and the ability to optimize naive recursive approaches through subproblem reuse and improved time/space efficiency.

Compute ways to climb n steps

Company: Paradromics

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a function that returns the number of distinct ways to reach the top of a staircase with `n` steps if you can climb either 1 or 2 steps at a time. - Input: integer `n` (assume `1 <= n <= 45`) - Output: number of distinct ways Discuss how you would improve a naive recursive solution using dynamic programming (top-down memoization or bottom-up iteration).

Overview: This Coding & Algorithms question evaluates recursion and dynamic programming concepts by asking for the count of distinct ways to climb n steps, framed at an algorithmic/implementation level. It is commonly asked because it probes recognition of overlapping subproblems and the ability to optimize naive recursive approaches through subproblem reuse and improved time/space efficiency.

Return the number of ways to climb n steps taking 1 or 2 steps at a time.

Constraints

  • 1 <= n <= 45

Examples

Input: (1,)

Expected Output: 1

Explanation: One step.

Input: (2,)

Expected Output: 2

Explanation: Two ways.

Hints

  1. ways[n] = ways[n-1] + ways[n-2].

Ways to Climb Stairs

mediumParadromicsSoftware Engineer

Return the number of ways to climb n steps taking 1 or 2 steps at a time.

View full question (all parts)

Implement a function that returns the number of distinct ways to reach the top of a staircase with n steps if you can climb either 1 or 2 steps at a time.

  • Input: integer n (assume 1 <= n <= 45)
  • Output: number of distinct ways

Discuss how you would improve a naive recursive solution using dynamic programming (top-down memoization or bottom-up iteration).

Examples

Example 1
Input
(1,)
Output
1
Notes
One step.
Example 2
Input
(2,)
Output
2
Notes
Two ways.

Constraints

  • •1 <= n <= 45

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def solution(n: int) -> int:
Sample call
solution(1)
Language
Case 1
Input
(1,)
Expected
1
Case 2
Input
(2,)
Expected
2

Browse More Questions