There’s a staircase
Start simple. You’re standing on the landing and want to reach the first step, #1. There’s just one
way to do it—take one step up.
Now let N = 2. There are two ways to get to the second step. Either you take two single steps in
succession or you take one double step.
This is practically all you need to solve the problem. To see why, imagine your goal is step #3.
For the first time, you can’t get there in a single bound. It’s got to be a combination of steps. But there are only two ways of arriving at step #3—either by taking a single step (from step #2) or by taking a double step (from step #1). We already know that there is only one way to get from the landing to step #1. We also know that there are only two ways to get from the landing to step #2. Add these (1 + 2 = 3) to get the number of ways to arrive at step #3.
The same logic applies to every higher step. There are two ways to get to step #4, from step #2 or from step #3. Add the number of ways of getting to step #2 (2) to the number of ways of getting to step #3 (3). That gives 5, the number of ways of getting to step #4.
It’s easy to continue the series. The number of ways to climb quickly snowballs, looking like this:
For anyone with a math background, the lower series will look familiar. It’s the Fibonacci
sequence. (More on that in a moment.) The interviewer wants an answer for the general case of N stairs. It’s simply the Nth Fibonacci number.
Leonardo Fibonacci, also known as Leonardo Pisano, was the most influential Italian mathematician of the late Middle Ages. It was Fibonacci who realized the incredible superiority of the Arab-Hindu system of numeration, with its place notation, over the roman numerals still used in medieval Europe. With the Arab-Hindu system, multiplication and division could be reduced to an algorithm (another Arab word). With roman numerals, these operations were impractically hard.
Merchants had to seek out expensive experts to perform calculations on an abacus. In 1202, Fibonacci wrote a guide to the abacus, Liber abaci, in which he pitches “Arabic” numerals to what must have been a skeptical audience. The book also describes what we now call the Fibonacci sequence.
Fibonacci didn’t invent it; the sequence was known to sixth-century Indian scholars.
Start by writing 1, then another 1 after it. Add them to get the sum (2) and append that sum to the series.
1 1 2
To generate each new number, just add the last two numbers in the series. The series becomes:
1 1 2 3 5 8 13 21 34 55 89 144…
Conspiracy theorists will find that the Fibonacci series turns up in all sorts of unexpected places.
Want to convert between miles and kilometers? Use adjacent Fibonacci numbers (55 miles per hour = 89 kilometers per hour). The next time you’ve got too much time on your hands, count the little fruitlets making up a pineapple. You’ll find that they form two intersecting sets of helices running in opposite directions. One set has eight helices; the other, thirteen.
Both are Fibonacci numbers. Similar patterns are seen with pinecones, sunflowers, and artichokes. Coincidence? Not likely, nor is the fact that the Fibonacci sequence turns up in The Da Vinci Code (it’s a combination to a safe)—and in this interview question, used at an information company bent on world domination.