Python Interview Questions For Beginners – Nth Fibonacci

Lately, I am starting to feel the impostor syndrome creeping up in my thoughts. So, I have decided to work on brushing up my python interview skills. I am starting with a popular python exercise for beginners: Solving for the Nth Fibonacci number. A small step towards convincing myself that I am good enough to move up to the next level of my career. There is a lot of other tutorials on how to do this online already. However, I believe it still worth it to go over my approach solving this problem. When I first started coding, I struggled with this problem. I wished that I could peek into a professional software developers mind understanding how to dissect a problem like this so that it is easy to solve. Hence, I feel a deep dive into what goes on inside my mind when I am coding will be interesting to see.

My favorite approach to solving programming challenges is to do it in three stages. In the first stage, I focus on being the architect. As an architect, I want to ensure that I fully understand the scope of the problem. This is important as I want to make sure that I am not just solving the problem blindly and that I am heading in the right direction. I do this by making sure that I capture the requirements of the problem. Some questions that I like to ask myself at this stage is what we are trying to achieve? What sort of input am I dealing with? What sort of output do we want from solving this problem?

For the Nth Fibonacci programming challenge, let us start with understanding what a Fibonacci sequence is. Fibonacci sequence is the series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 …

Where the nth Fibonacci number in a Fibonacci sequence is found by the sum of the two Fibonacci numbers before it. For example:

• 2 is found by adding (1 +1)
• 3 is found by adding (2 +1)
• 5 is found by adding (3+2)

The goal of the programming challenge then is to compute the Fibonacci number for a given input. For this programming challenge, I think using a table here to visually see the input and output is helpful.

The second stage is to focus on being an engineer. At this stage, my only worry is to come up with an algorithm to solve the problem. One interesting thing to observe about the Fibonacci problem is that we can solve for the nth Fibonacci number if we know the (n-1)th Fibonacci number and the (n-2)th Fibonacci number. In other words, we can solve for the original Fibonacci number by recursively solving for previous Fibonacci numbers. This is a good programming problem to solve with recursion.

The first step in coming up with a recursion algorithm is to come up with a base case. In this case, the base case I can think of is:

if n <=1 we know that the Fibonacci number is just the same as n. This is because Fibonacci (0) = 0 and Fibonacci (1) = 1.

Otherwise, I want to solve for Fibonacci(n). Fibonacci(n) is just Fibonacci(n-1) + Fibonacci(n-2). Now that I have the basic algorithm, I can translate this to actual Python code.

def fibonacci(n):
    if(n<=1):
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

The third stage is focusing on being a QA tester. Now that I have an algorithm to solve the problem, I want to test for the correctness and efficiency of my coding solution. This is where I come up with test cases to verify that my solution above is correct. The order of testing here matters, I first want to test if my algorithm is correct. Once that is done, I want to test for the efficiency of my algorithm. The fastest solution is not very useful if it does not solve the problem correctly. One way to test for my algorithm is to simply verify that my function returns the correct Fibonacci sequence for a given input n. So, I will test for the Fibonacci sequence I gave as an example above: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

def test_fibonacci(self):
    assertEquals(fibonacci(0), 0)
    assertEquals(fibonacci(1), 1)
    assertEquals(fibonacci(2), 1)
    assertEquals(fibonacci(3), 2)
    assertEquals(fibonacci(4), 3)
    assertEquals(fibonacci(5), 5)
    assertEquals(fibonacci(6), 8)
    assertEquals(fibonacci(7), 13)
    assertEquals(fibonacci(8), 21)
    assertEquals(fibonacci(9), 24)

Now that I have verified that my solution is correct, I want to test for the efficiency of my solution. This is because a correct solution can be unusable if it is too slow. At this stage I want to explore questions like: How does my algorithm behave for very large n or very small n? Do I need to worry about memory overflow? For production grade code, I will also ask questions like is there any edge cases that I need to handle. How will the algorithm behave for invalid input? What happens if a user passes an invalid character like & or * for example?

One inefficiency of my algorithm above is that for each n that I am solving, I need to recalculate all previous Fibonacci numbers. There is a lot of overlap in solving the same problems when I call fibonacci(n-1) and fibonacci(n-2).  Instead of computing each number from scratch, I can solve this by storing the result of a Fibonacci number so that I do not have to compute for it at every step of the recursion. This is what I came up with:

def fibonacci(n, result={0:0, 1:1}):
    if n in result:
        return result[n]
    else:
        result[n] = fibonacci(n-1, result) + fibonacci(n-2, result)
    return result[n]

If I am worried about stack overflow when computing for a large n, I can also use an iterative approach instead of using recursion. Although I find that the iterative solution for the fibonacci problem a bit less intuitive to understand than the recursion solution. Therefore, I did not mention this solution first. One thing I like to keep in mind when programming is how easy is it for other people to read and understand my code? In other words, keep in simple. Complexity is a trade off. It is only worth it if there is a use case for it. In this case, stack overflow is a concern so I will code an iterative solution to the problem.

def fibonacci(n):
    a , b = 0 , 1
    for i in range(n):
        a , b = b, a+b
    return a

There are many ways to approach solving a programming problem. The approach I mention here is something that personally works for me. I find that this approach where I focus on one thing a time lessens the cognitive burden on my mind and makes it easier for me to code. Another popular approach is Test Driven Development (TDD) where you focus on software testability first. I like using that approach when I am refactoring existing code rather than when I am trying to come up with a new code from scratch. Through finding an approach that works for me, I feel more confident at solving interview questions and am better able to ignore my impostor syndrome.