Necessary and Sufficient

Questions: Given that you can take 1 or 2 steps forward from a given step, what is the total number of ways of reaching the Nth step?

Solution: Firstly, let us consider an arbitrary step, i. This step can be reached by:

1. being on the (i-1)-th step and advancing forward 1 step, OR
2. being on the (i-2)-th step and advancing forward 2 steps.

If we let f be a function which defines the total number of ways of reaching a given step, we can mathematically express the scenario described above as follows:

In other words, the total number of ways of reaching step i is a function of the total number of ways you can reach each of the 2 previous steps. This is, of course, a recurrence relationship describing the Fibonacci-like sequence. By their nature, recurrence relationships are amenable to recursive solutions - although it is often more efficient to find a closed-form solution! To solve the above equation recursively one only needs to know the seed values f(1) and f(2). In this case, f(0) is not required, f(1)=1 and f(2) = 2 and for n>2 the above formula can be used. QED

Problem: You have 1 million objects in memory (it's a big machine). Each object represents a customer and therefore has a Name and AgeInYears property. You need to sort the customers by AgeInYears.

Solution: Many technical folks immediately rack their brain over the various sorting algorithms and if they are any good will offer up quickSort, or maybe mergeSort, and tell you it has O(n.log₂n) running time. But you need to stop and think about the problem for a minute and not be constrained by textbook knowledge. What's the age range of the customers? It couldn't be more than a hundred or so right (0-100)? So how about we create 100 lists - one for each age in this range - and then make a single pass through all 1 million customers adding them to the relevant list. That involves precisely n comparisons thus this has O(n) run time complexity. Of course we still need to merge the 100 lists to get the end result but that is trivial to do and doesn't add to the run time complexity. Now that's thinking outside the box!