This week I have started my job search and interview preparations. After speaking with a few industry pro’s the top recommendation from them was brush up on your “Whiteboard answers”. If you are relatively new to programming like I am you may be asking what that is, and so my goal this week is to solve a couple of very commonly asked interview questions.
First we need to know what a whiteboard question is. This is a questions designed for you to demonstrate your technical knowledge when presented with a coding problem. Whiteboard interviews are from what I am told very common and is really just a chance for the interviewer to see your problem solving skills. In most cases you will be asked to work out a solution for a coding challenge on the spot using a whiteboard. This demonstrates that you have problem solving skills, and also that you can do this task away from the comfort of a computer screen with all the handy auto-fill functions, tool-tips, and so on. In my search so far I found that one of the most commonly asked questions for a programming interview is something along the lines of the following:
Write a method Fib() 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:
I read this and realized 2 things, first I need to study more math questions, and second I had completely forgotten what the Fibonacci sequence was. You might be asking why this would be important in the world of programming, and I will do my best to answer that question at the end. But for now lets get started and take a deep dive into some math. So I started by looking up the Fibonacci Sequence and then went to work on figuring out our problem.
Okay now that we know what it is lets break it down a little further so we can write it in code form. Below is the same sequence but with a few added variables of (A,B,C). We will use these to represent our equation. Another important note is you will need to know the base cases in order for this to work. Base cases are the 2 static numbers that will never change and in which all other numbers in this sequence will com from. In the Fibonacci sequence those numbers are 0, 1 and we assign those to the variables of A,B.
The formula we need to create is simply C = A + B, and then every time we use this formula we need to swap (A,B) so that (A = B), and (B = C). Are you Confused yet? Its okay because I was too. But lets look at the next picture which should help.
Now we have a full picture of how this formula works, and can move on to the other thing we will need. We have a way to create our Fibonacci sequence, but now we need to find “n”. Looking back at our instructions, we know there are a few things we need to make this work, like a variable for (n), and an array or list of some sort to store our Fibonacci numbers.
Write a method Fib() 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:
I started by doing just that and created a variable for (n) called “_yourNumber” and then decided to use a List<int> because with a list it can dynamic and the size does not need to be established. This allows me to have a sequence of numbers as small or large as I want. I also decided to globalize a variable for the Fibonacci number we are looking for. Looking a bit further we can match up an Array[] of numbers as below to see how we are going to solve for “n”
To help us better understand this I added an additional row to our previous charts that will represent the List<int> _fibNumbers. If we look at the chart below we can start to see how the numbers match up. So if we were looking for the nth Fibonacci number and n = 4. We can now see that would the number 3 in the Fibonacci Sequence.
Now to create our method. Here we have our method of Fib(int n) as required and we are looking to get the equivalent Fibonacci number of n. So to do this we define our base cases of (a = 0), (b = 1), (c = 0). From here we need to assign our base case numbers to the list so we can then calculate the rest of the sequence with an algorithm. The way I chose to solve this was with a for loop “for (int i = 0; i < n; i++)”. Then we write our equation of (c = a + b), and because we are in a loop we can designate that we want we want to change the values of “a” and “b” each time. Before we exit our loop we need to assign the new values to our list by adding “c”. This will ensure that every time this loop is called it will create a new value for “c” and add it to the list until we have reached out desired number of “n”.
Now that we have a list of our Fibonacci numbers that was generated up to the nth we can assign that very number to our variable of “_fibNumber”. If you have used [Serialize Field] for all of your private variables then you are all set and the nth value will now show up in the inspector once you have called your method. I used a global variable for the value of nth because I wanted to give the user the power to choose what number they were looking for. by doing this and then passing “_yourNumber” in as the parameter it completes our equation and makes this method modular. The advantage to this is we have not hard coded in the nth value which means we have control. You can also approach this from a different way and check to see if a particular number is a Fibonacci number. Simply add a variable for the number you wish to check.
Then we will need to write a couple methods to make this work. Without going too deep into the math aspect of the following methods, what we want to do is create a recursive method, or a method that calls itself creating a loop. Recursion is the parent of the Dynamic Programming solution. This is helpful because in order to solve a Dynamic Programming Solution we need to know how to solve a recursive problem.
I added the methods of “private bool IsPerfectSquare(int number)” and “private bool IsFibonacci(int number)”. These methods are return type methods meaning they will return a value, in this case a bool of true or false. They also require a number that we want to check to make them work. First we are checking to see if the number is a perfect square. Then we will use that method in our recursive method of “private bool IsFibonacci(int number)”. Finally using a simply “if” statement we check to see if our number is a number in the Fibonacci sequence.
Why is this useful you ask? Because recursive programing is a form of loops, and loops make things easier to work through. For example we could say solve for “Find our way home” and then create several “if” statements of “if” this then do that etc. or we could write a recursive algorithm that creates a list and continuously checks that list until we have found our answer. I had a lot of fun looking into this and will continue to read up on this topic since it is so vast, but I hope this helps you if you should be given this question for an interview. Mahalo for reading!!
