Interview Cake

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

Write a function ICKFib that takes an integer n and returns the nth Fibonacci number.

Let's say our Fibonacci series is 0-indexed and starts with 0. So:

ICKFib(0); // => 0 ICKFib(1); // => 1 ICKFib(2); // => 1 ICKFib(3); // => 2 ICKFib(4); // => 3 ...

Our solution runs in n time.

There's a clever, more mathy solution that runs in time, but we'll leave that one as a bonus.

If you wrote a recursive function, think carefully about what it does. It might do repeat work, like computing ICKFib(2) multiple times!

We can do this in space. If you wrote a recursive function, there might be a hidden space cost in the call stack!

The nth Fibonacci number is defined in terms of the two previous Fibonacci numbers, so this seems to lend itself to recursion.

ICKFib(n) = ICKFib(n - 1) + ICKFib(n - 2);

Can you write up a recursive solution?

As with any recursive function, we just need a base case and a recursive case:

  1. Base case: n is 0 or 1. Return n.
  2. Recursive case: Return ICKFib(n - 1) + ICKFib(n - 2).
NSUInteger ICKFib(NSUInteger n) { if (n == 0 || n == 1) { return n; } return ICKFib(n - 1) + ICKFib(n - 2); }

Okay, this'll work! What's our time complexity?

It's not super obvious. We might guess n, but that's not quite right. Can you see why?

Each call to ICKFib makes two more calls. Let's look at a specific example. Let's say n=5. If we call ICKFib(5), how many calls do we make in total?

Try drawing it out as a tree where each call has two child calls, unless it's a base case.

Here's what the tree looks like:

A binary tree showing the recursive calls of calling fib of 5. Every fib of n call calls fib of n minus 1 and fib of n minus 2. So calling fib of 5 calls fib of 4 and fib of 3, which keep calling fib of lower numbers until reaching the base cases fib of 1 or fib of 0.

We can notice this is a binary tree whose height is n, which means the total number of nodes is .

So our total runtime is . That's an "exponential time cost," since the n is in an exponent. Exponential costs are terrible. This is way worse than or even .

Our recurrence tree above essentially gets twice as big each time we add 1 to n. So as n gets really big, our runtime quickly spirals out of control.

The craziness of our time cost comes from the fact that we're doing so much repeat work. How can we avoid doing this repeat work?

We can memoize!

Let's wrap ICKFib in a class with an instance variable where we store the answer for any n that we compute:

@interface ICKFibber : NSObject { @private NSMutableDictionary<NSNumber *, NSNumber *> *_memo; } - (NSUInteger)fib:(NSUInteger)n; @end @implementation ICKFibber -(instancetype)init { if (self = [super init]) { _memo = [NSMutableDictionary new]; } return self; } - (NSUInteger)fib:(NSUInteger)n { // base case: 0 or 1 if (n == 0 || n == 1) { return n; } // see if we've already calculated this if (_memo[@(n)]) { return _memo[@(n)].unsignedIntegerValue; } NSUInteger result = [self fib:(n - 1)] + [self fib:(n - 2)]; // memoize _memo[@(n)] = @(result); return result; } @end

What's our time cost now?

Our recurrence tree will look like this:

A binary tree showing the memos and recursive calls of calling fib of 5. Starting with the calls for fib of n minus 1, fib of 5 calls fib of 4, which calls fib of 3, which calls fib of 2, which calls fib of 1. then, for the fib of n minus 2 calls, fib of 5 gets the memo fib of 3, fib of 4 gets the memo fib of 2, fib of 3 gets the memo fib of 1, and fib of 2 calls fib of 0.

The computer will build up a call stack with ICKFib(5), ICKFib(4), ICKFib(3), ICKFib(2), ICKFib(1). Then we'll start returning, and on the way back up our tree we'll be able to compute each node's 2nd call to ICKFib in constant time by just looking in the memo. n time in total.

What about space? _memo takes up n space. Plus we're still building up a call stack that'll occupy n space. Can we avoid one or both of these space expenses?

Look again at that tree. Notice that to calculate ICKFib(5) we worked "down" to ICKFib(4), ICKFib(3), ICKFib(2), etc.

What if instead we started with ICKFib(0) and ICKFib(1) and worked "up" to n?

We use a bottom-up approach, starting with the 0th Fibonacci number and iteratively computing subsequent numbers until we get to n.

NSUInteger ICKFib(NSUInteger n) { // edge cases: if (n == 0 || n == 1) { return n; } // we'll be building the fibonacci series from the bottom up // so we'll need to track the previous 2 numbers at each step NSUInteger prevPrev = 0; // 0th fibonacci NSUInteger prev = 1; // 1st fibonacci NSUInteger current = 0; // declare and initialize current for (NSUInteger i = 1; i < n; i++) { // Iteration 1: current = 2nd fibonacci // Iteration 2: current = 3rd fibonacci // Iteration 3: current = 4th fibonacci // To get nth fibonacci ... do n-1 iterations. current = prev + prevPrev; prevPrev = prev; prev = current; } return current; }

time and space.

  • If you're good with matrix multiplication you can bring the time cost down even further, to . Can you figure out how?

This one's a good illustration of the tradeoff we sometimes have between code cleanliness and efficiency.

We could use a cute, recursive function to solve the problem. But that would cost time as opposed to n time in our final bottom-up solution. Massive difference!

In general, whenever you have a recursive solution to a problem, think about what's actually happening on the call stack. An iterative solution might be more efficient.

Reset editor

Powered by qualified.io

. . .