Different companies can have very different emphasis on algorithms during coding interview. Nevertheless, if I had only 10 minutes to prepare for recruitment meeting, I would most definitely spend it on learning recursive version of Fibonacci sequence - it simply turns up the most often. In this post, I am providing you with “transcript” of the first time I was asked to implement Fibonacci sequence algorithm in Python few years ago. Take a look at the way I was thinking out loud and try to mimic this approach during your job interview even when different algorithmic task appears!
RECRUITER: Can you write a function, which takes a positive integer n as an argument and returns n-th element of Fibonacci sequence? So, for example for 6 this function should return 8.
ME: Sure! Let me start by defining a function you specified. For now it’ll return a placeholder (-1). I’ll just write first few elements of Fibonacci sequence in a comment to have them in mind. As far as I remember, every consecutive element is a sum of the previous two.
def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 return -1
I started with revisiting definition of the problem and small study of an example, which I wrote in a comment.
I will implement a solution to a simpler problem - writing Fibonacci sequence algorithm for zeroth, first and second element. Actually, we can omit zeroth since you said, that my function should take a positive integer as an argument. So, below solution will produce bad result for n larger than 2. Otherwise it’s fine.
def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 if n == 1 or n == 2: return 1 return -1 # Good result print(fibonacci(1)) # Good result print(fibonacci(2)) # Bad result print(fibonacci(3))
Simplifying a problem is an important step towards its further exploration and better understanding. Recruiters love that!
I think I need a visual assistance. I’ll try to dissect an example with n = 6. The output should be 8 (8 is sixth element of Fibonacci sequence). But how exactly was that calculated? Let me quickly draw a simple diagram to find that out. Oh, now I see - tree perfectly fits this use case, so I will probably need to use recursion.
Don’t forget to visualize examples using diagrams like charts, trees, graphs or tables.
To implement recursion we need recurrence definition and a termination step. The latter can be defined by looking at leaf nodes of the tree diagram I drew. Oh, the if statement I’ve written for the first two elements is already a termination step! Let me say out loud what I want my recurrence step to look like: In order to calculate a Fibonacci element at n-th position I need to take Fibonacci elements from previous two positions and sum them up. In other words, I need to sum Fibonacci elements from position n - 1 and n - 2, which can also be calculated using my Fibonacci function.
def fibonacci(n): # 0, 1, 1, 2, 3, 5, 8, 13, 21 if n == 1 or n == 2: return 1 return fibonacci(n - 1) + fibonacci(n - 2) # Good result print(fibonacci(1)) # Good result print(fibonacci(2)) # Good result print(fibonacci(6))