How are you guys doing today?
What I wanted to do today was to creat a video on
a coding interview assignment I was asked to complete during an interview.
Here is what they want me to do.
They want me to implement a function that returns the nth number in a Fibonacci sequence.
So the first thing I have to do was break down the problem.
As you can see on the screen, there’s a chart.
This chart is divided up into two sections:
one section will be n which represents a number.
And another section is fib n which represents the Fibonacci number.
So when it comes to the Fibonacci sequence
the current number of the fib sequence will be equal to the sum of previous two numbers.
But there are two base cases.
If the number entered n is one, the Fibonacci number is one
And if the number entered n is two the Fibonacci number is one.
But let’s just say we enter in three if we enter in three
we have to add the Fibonacci the previous two Fibonacci numbers together in order to get that current Fibonacci number.
So next thing I have to do was create a formula.
举例来说 我们有同一张表 但我们不知道第四个斐波那契数是什么
So let’s just say for example we have the same chart but we don’t know what the Fibonacci number of four is
how we go about doing that.
The first thing we need to do is create a formula.
Now with this formula let’s just say we’re looking for Fibonacci number of four
我们代入4 我们得到 Fib(4)=Fib(4-1)+Fib(4-2)
We’ll pass in four and we get Fibonacci 4 equals Fibonacci 4 minus 1 plus Fibonacci 4 minus 2
which pretty much states that the current Fibonacci number is going to be equal to the sum of the previous two numbers.
So we then simplify this we then get Fibonacci 4 equals Fibonacci 3 plus Fibonacci 2.
We already know what Fibonacci 3 is and we also know what Fibonacci 2 is.
If we just look at the chart Fibonacci 3 is going to be equal to 2
Fibonacci 2 is going to be equal to 1.
So we add these two values together.
And we ultimately we ultimately get Fibonacci 4 equals to three.
So let’s get to the code now.
The first thing that I want to do is write a function.
This function is going to return a number.
And the function will also take in a number.
Now when I put together the method
the first thing I want to do is check for the base cases.
Now as I stated in my presentation,
there are two base cases 1 and 2.
So what I want to do is add conditional statement that is
if n is less than or equal to 2 then I want to return 1
所以 “if (n <= 2)"
so if n is less than or equal to 2
然后 “return 1”
then I want to return 1.
Now I also want to write an else condition
and this else condition is going to contain the actual formula for calculating
the Fibonacci number based on the given number.
你要输入 “return fib(n-1)+fib(n-2)”
So you want to return fib n minus 1 plus fib n minus 2
let’s save this.
And basically what we have here is a recursive method
that is going to invoke a method call upon itself until it comes up with
the Fibonacci number that we are looking for.
So what we want to do is to go up to this main method.
And print the value of this method out.
Let’s just say fib of 4.
So if we do this correctly this is what we should get.
Fib 4 is supposed to return 3.
we enter in 4 this is our formula that we have
And now we just simply run the application.
We have 3 exactly what we wanted.
During the interview after implementing the function
I was then asked what are some problems with the function that I have written
my mind went blank and I didn’t know how to respond.
After doing some research I learned there were 3 things I need to take note of after writing the function.
The first thing checking for numbers below 1.
Now let’s go back to the code.
Now the reason I want to check for numbers below 1 is because
when it comes to Fibonacci sequence there is no Fibonacci number associated with
numbers that are negative or any numbers that are less than one.
So how I’m going to fix that is by writing an if condition
if n is lesser than one
then what I want to is throw a new illegal exception.
就写” no numbers”
Just write no no numbers.
或是小于1的数是不允许的 我们就写 ” numbers below one not allowed”
Or just numbers below one not allowed let’s just write that numbers below one not allowed.
And if I’m checking for this condition below one , I also have to change this conditional here.
So you know conflict.
So if n is equal to one or n is equal to two
then I want to return 1.
So from here in this condition, I’m checking for these numbers specifically.
Now let’s just enter in a number below one, let’s just say negative 5.
Save now we run the application.
And we’ll get the illegal argument exception that we were expecting: numbers below one not allowed.
Alright so another thing that I had to take note of was
the number of recursive calls for large numbers.
So it pretty much means that if you enter in a very large number
you’re eventually going to get a stack overflow exception especially if the function is
Well the function has a recursive call.
You’re going to get stack overflow, so let’s try this out in the code.
So let’s just say up here we enter in ten thousand.
We enter in ten thousand, we save it and we run the application.
It’s going to take a while for this application to produce a result.
But due to the fact that the number of recursive calls grows exponentially
is going to eventually lead to a stack overflow exception.
So we’re going to stop this application.
And I’m going back to this and show you how to resolve that.
Let’s go back to the representation.
And another thing you have to take note of is time complexity.
So as I said before if there’s a number of recursive calls.
The function is going to grow exponentially.
And there is a way to resolve that so that
the function can have a time complexity, a linear time complexity.
So I’m going to try to show you how to do that now.
Alright, so the first thing we want to do.
We want to create an another function.
We’re going to name this function fibNumRecursive.
This is also going to take in an interger.
And we want to set this up kind of similar to the way that we set up the first function.
So I’m going to add a conditional statement
if n is less than or equal to 2
then I want to return 1.
Next thing I want to do is add three variables
first second 和nth
first and second and nth.
Now these variables are going to be used in order to calculate the next number or
the number of Fibonacci sequence based on the given number.
So I want to set this first variable equal to one
you want to set this second variable equal to two
and we want to set this nth variable equal to 2 as well.
Now what we want to do next is write a for loop.
在这个for循环里我们将输入 “int i =”
In this for loop we’re going to have int I equals.
And we want to start this at three.
Now a reason that we’re starting at three is because we’ve already handled the base case of two here.
So I just want to start off with three right here, that’s what we are going to be done
现在输入 “if (i <= n-1)" 接着 "i++"
Now if i is lesser than or equal to n minus 1 then i plus plus.
So basically if they if you enter in a number here
it’s going to check this number.
But within this range between 3 and the number that’s passed in.
So the first thing I want to do is say or you know right
“nth = first + second”
nth equals first plus second
“first = second”
first equals second
“second = nth”
and second equals nth
然后 “return nth”
and I want to return nth.
Now what’s going on here
This nth variable is going to be the variable that calculates the Fibonacci number.
So you’re going to add the first and the second.
And that’s ultimately going to give you the number that you are looking for
So this nth value is going to be based on the number of iterations
as well as the current number of the first and the second number.
So you’ll also realize that this fibNonRecursive method
is going to be able to handle this 10000 right here.
Because there are no recursive calls, there’s just a simple loop
which iterates a certain number of times based on the number that’s passed in
in order to eventually split out the Fibonacci number.
So if I were to call this method and then pass in 10000
here’s what we get.
The Fibonacci number of 10000.
There’s no stack overflows, the time of complexity of this is n
which is the way better time complexity than exponential time complexity.
And to explain this a little bit further, I actually want to go back to the presentation that I have.
So for this non recursive method this is how it works.
So for for this non recursive method.
像我以前说的 first等于1 second等于2 nth等于2
As I said before, the first is going to be equal to 1, the second is going to be equal to 2, the nth is going to be equal to 2.
Now what I’m doing here is I’m starting at three.
Because I’ve already handled that case for two up in that first if condition.
Now the best way to explain this is by using an example.
So let’s just say I pass into number 4.
So due to the fact that I started at three, there’s only going to be one iteration since I’m passing in four.
在第一个迭代中 “nth = 1 + 2”
So in this first iteration, n the Nth variable is going to be set equal to one plus two
“first + second” 第1个加第2个 这里你可以看到 “nth = first + second”
first plus second, first plus second which you can see here nth equals first plus second.
现在first设置成等于2 second设置成等于nth 也就是3
Now the first is going to be set equal to two, and the second is going to be set equal to the nth which is 3.
And fib of four is going to be equal to nth.
看 然后我们返回nth 它最终等于3
See and then we’re returning nth which will ultimately be three.
And if you enter in another number, let’s just say you enter in five
you would have to loop through this twice instead of only once.
If you have any questions, leave them in the comments below.
Don’t forget to subscribe and like the video if you found it helpful.
实际上我正在考虑创建一个对话 是特别针对编程面试题的 就像这一题一样
I am actually thinking about creating a chat that is specifically dedicated to coding interview questions just like this one.
如果你认为我应该那样做 在评论里留言 谢谢观看 下次再见
If you think I should do that, leave the comments below, see you next time, thanks for watching