Find Nth Fibonacci Number

Daily Coding Problem: Problem #1790 [Easy]

Implement the function fib(n), which returns the n^th number in the Fibonacci sequence, using only O(1) space.

Analysis

The “using only O(1) space” stipulation is important. It means you’re supposed to use only a fixed number of variables in calculating the n^th Fibonacci number.

The usual definition of Fibonacci number F_n is almost a definition of a primitive recursive function:

F_n = F_n-1 + F_n-2

F₀ = 0

F₁ = 1

This invites a recursive function:

func fib(n int) int {
    if n == 1 { return 1 }
    if n == 0 { return 0 }
    return fib(n-1) + fib(n-2)
}

The function above looks like it uses only the formal argument n, which is a fixed number of variables. I don’t think that’s what the interviewer wants here. Each function call ends up causing the allocation and use of a “stack frame”, some amount of memory to hold formal arguments, where in the program to resume execution when a function returns, and keep track of the value of fib(n-1) while the computer calculates fib(n-2).

Here’s a non-recursive version of fib(n):

func fib(n int) int {
    x, y := 0, 1
    for i := 0; i < n; i++ {
        t := x + y
        x,y = y,t
    }
    return x
}

Only 5 integers worth of working storage, plus a single stack frame since it does not recurse or call any other functions.

I was amused to find that you can’t write the body of the for-loop with a single assignment like t, x, y = x+y, y, t and get correct answers.

This Problem in Job Interviews

At face value, this is a very simple coding problem meriting the “[Easy]” rating.

I reckon that most job candidates have fiddled with Fibonacci numbers and the sequence in a way that makes the O(1) extra space version the natural version to write. I recall producing the Fibonacci Sequence on a simple electronic calculator that had one “memory” location by a repetitious series of three or four key presses. Additionally, specifying O(1) space means the interviewer doesn’t get to see if the job candidate understands recursion.

These observations make the problem seem flawed.

It’s possible that an interviewer could use this problem as one of several questions in an interview. I’d suggest asking for a recursive version after doing this one, and asking for memoizing the recursive version after that. Not all coding problems could be used in this fashion. Some coding problems have an explicit “What about” extra question, “what about finding a palindrome doubly-linked list?” for example.

I wonder if the point of the problem is to get at the job candidate’s knowledge of language implementation details. This problem could be a jumping off pointer for discussion of stack frames, scopes of variables, the differences between formal arguments and local variables, and even comp sci theory, like recursion can be implemented via iteration and vice versa. This would have been a great problem for the Daily Coding Problem book, if the authors of that book had bothered to include any discussion about alternatives, or why the phrasing of the problem matters.

Thinking about this question from the viewpoint of an interviewer reveals faults in the grinding leetcode approach to coding problems. An interviewer uses coding problems to get insight into what a job candidate has to offer in many areas, code quality, imagination, depth of comp sci knowledge, writing testable code, program design, communication skills. If you solve a leetcode problem by getting a single solution, you’re missing out on practicing all those areas.

It turns out that someone has an article doing exactly what I describe above.