# Where discrete mathematics meets an interview question

Last week, I was sitting behind my desk at work, surfing hacker news and and at the top of the website floated an article by the co founder of “Daily Coding Program”, a small tech start up that e-mails daily newsletters with a programming question.  The article shared some of their insights over the past year and how they bootstrapped the company and eventually grew to \$2,000 in monthly revenue.

Although I was interested in reading the blog post, I ended skipping over most of it and navigated to their front page, where I scrolled up and down and read more about the company’s product.  When I reached the end of the front page, I was confronted with a sample interview question:

There’s a staircase with N steps, and you can climb 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

This question, I had initially thought, could be solved using some techniques that I recently learned from taking my discrete mathematics course. But to confirm whether or not I could apply permutations and combinations, I hollered at my colleague, repeating the question out loud and asking him how this problem could be solved. And as I started reading the question out loud, “There’s a staircase with N steps, and you can climb …” he interrupted me, finishing my sentence with, “1 or 2 steps at a time.”

Apparently, while preparing for interviews with Google and Microsoft, he had stumbled across this same practice problem.

So after letting him interrupt me, I asked him if this particular problem could be solved with permutations or combinations. In other words, do these two mathematical concepts apply to the problem. He confidently answered, “No — dynamic programming.” He then proceeded to step me through his solution, scribbling down his work on a white piece of 8.5 x 11 that sat on my desk.

Fast forward to now.

I’m at home, starting the next lesson for my discrete mathematics course, the lesson title: “Counting using Recurrence Relations” and “Solutions to Recurrence Relations.” I’m skimming the chapter, building a mental model of what the entire chapters entail, an overview.  And when I reached the end of the first chapter, where exercise problems live, I couldn’t help but form a little grin.

To my surprise, the following chapters cover topics relating to the interview question that I had just read. In fact, the exercise in the chapter is phrased almost identically:

Sal climbs stairs by taking either one, two, or three steps at a time. Determine a recursive formula for the number of different ways Sal can climb a flight of n steps.

So, I find it always nice and serendipitous when what you are learning, either in school or on your own, can be applied to real life examples. Albeit, this application was only for an interview question.

But I’ll still consider that as a victory.

Matt Chung