A staircase has n steps. You can scale the stairs by taking steps one or two at a time. How many ways are there to scale the steps?

If there are 0 steps, there is 1 possibility (you are already done).If there is 1 step, there is 1 possibility (you take one step).
If there are n steps, your first choice is either 1 step or 2 steps:Choice 1: the problem now exists for n-1 stepsChoice 2: the problem now exists for n-2 steps
Let f(x) be the number of ways of scaling x steps. You can now say that f(x) = f(x-1) + f(x-2) - the Fibonacci sequence.
This is an example of a dynamic programming question - a computer science topic for first-year Cambridge computer scientists, and my first interview question.

Answered by Oxbridge Preparation tutor

2062 Views

See similar Oxbridge Preparation Mentoring tutors

Related Oxbridge Preparation Mentoring answers

All answers ▸

CLAT: "Parliamentary Sovereignty is a fundamentally positive component within our constitution. Discuss"


“What do I do if I get given an unseen passage during my interview?


How do neurons know when to fire?


What do Oxbridge interviewers look for in a prospective student?


We're here to help

contact us iconContact ustelephone icon+44 (0) 203 773 6020
Facebook logoInstagram logoLinkedIn logo

© MyTutorWeb Ltd 2013–2025

Terms & Conditions|Privacy Policy
Cookie Preferences