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.
Related Oxbridge Preparation Mentoring answers
All answers ▸lim(x-> 0) sin(x)/x
I've heard that interviewers ask strange, out-of-the-blue questions to catch students off-guard. How do I circumvent this?
If the State could ensure all criminals were convicted 100% of the time, but at the cost of the total loss of privacy of all other civilians, would it be justifiable?
Is it true I can't prepare for the interview?