• #### 科普

SCIENCE

#### 英语

ENGLISH

#### 科技

TECHNOLOGY

MOVIE

FOOD

#### 励志

INSPIRATIONS

#### 社会

SOCIETY

TRAVEL

#### 动物

ANIMALS

KIDS

#### 卡通

CARTOON

#### 计算机

COMPUTER

#### 心理

PSYCHOLOGY

#### 教育

EDUCATION

#### 手工

HANDCRAFTS

#### 趣闻

MYSTERIES

CAREER

GEEKS

#### 时尚

FASHION

• 精品课
• 公开课
• 欢迎下载我们在各应用市场备受好评的APP

点击下载Android最新版本

点击下载iOS最新版本

扫码下载译学馆APP

#### 编程面试题1:在斐波那契数列中寻找第n个数

Interview Question 1: Write a function to find the nth number in a fibonnacci sequence

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

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

so if n is less than or equal to 2

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.

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)返回3
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.
[打字中]
[typing]

Just write no no numbers.
[打字中]
[typing]

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.

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

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

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.

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.

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.

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.
Fib(4)将会等于nth
And fib of four is going to be equal to nth.

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

[B]倔强

B11101001