Frontend interview question - Fibonacci all the question variations

In this tutorial, I would like to go over Fibonacci sequence questions for frontend interviews. I want to go over different possibilities because there is different option and I would like to cover as much as possible in this tutorial. So let's define first Fibonacci sequence. So the sequence is, uh, It's a sequence of numbers that start with 0, then 1. Some might argue that in some variations it starts with 1, so, but we're gonna go with this version when it starts with 0, 1, and then every next number is a summary of previous two. So Then it is 1, then it is 2, then it is 3, then it is 5. And now Copilot, um, autocompleted it. Okay, so we have our sequence. And now let's, uh, let's ask different questions. So some question might be, return me a number, um, a number 5 in a sequence of Fibonacci. Okay, so what does it mean? It means that it starts with 0. So 0, 1, 2, 3, 4, 5. It will be 5. Okay, so it's also important to define the number, the n. The n goes from 0, um, and start with 0. This is the main idea. Okay, so let's start with the functions that return us an Fibonacci number. Okay, const get, um, getFibonacci, let's call it num, number. Okay, so, so this is a perfect example for recursive function, and it's actually the simplest implementation of the recursive function. So if n is less or equal than 1, so when it's 0, it it's 0, when it's 1, it's 1. Then we return n, else we return, uh, the getFibonacciNum— number, um, the previous one plus, uh, the one before that. And this is the full implementation, uh, really 2 lines. So console Let's see, console.log. Uh, we're gonna get just, um, fifth number. Uh, we don't need to get this large number. Okay, let's clear the console here, and the number is 5. Let's get the 6 and 6 is 8 because it's 5 plus 3. Okay, so, so what is the complexity of this solution? The complexity is because we, we're getting called on twice for this function, so, so we have 2 calls. So the complexity, the time complexity grows because we we're getting a tree here of calls of Fibonacci. So the complexity in this case is O. Okay, so if we had another call, it will— it would be 3 power— sorry, 2^n. It will, it will be 3^n. Okay, so this is this case. So let's see how, how we can, how we can improve this time. Okay, so this is another question. So let's get, create another function where we want to improve it to O, which means that we won't be able to use recursion. Okay, so let's create a function const and getFibonacciNum. I would call this one rec so that I, I can use after. Okay, I would call this one rec and I'm going to close this one meanwhile. So we're having regular Fibonacci function. So we, um, we're gonna do now the function again. If n equal or less than 1, we return n. And now we're gonna initiate array, const fib that we initialize, and now we create a for, a for loop that is not equal to n because n again, n start with 0. Okay, so in our case we return the last element here, fib, fib . 1, okay, because just the last element, okay. So, um, in this function we're calculating, uh, Fibonacci, but now we have an, a loop and And this means that our time complexity is— no, sorry, the 6 should be— start with 0, 1, I'm sorry, so I do need here up to n. Yes, so we calculated up to n and we return 8. Let's clear it here. Okay, so in this scenario our time complexity dropped. So now the time complexity is O, okay, O, which is very good. But what, what, what happened here is that our space complexity— now we, we're having an array as a full array, so we're calculating the full array while we need only one number. So let's see how we can optimize this time complexity. So how can we do it? Because we don't need to hold full array, we can just hold the numbers that we need for calculation. How many numbers do we need to calculate every number? It's only 2, so we only need a space of 2. Okay, so in this case So we can just create const. So our next number is, uh, well, uh, it's basically we're gonna hold array of 0 and 1. So it will be 0 1. That will be my next, um And now I'm gonna define my prev, my const myPrev. Well, I, I could, I could actually use first and second, so I could, I could use this syntax sugar. So let's, let's really use it. So we take first and second from the fib, and we say the first is this, and the second is this. So this is my next, and my, um, and my prev is, um, is, um, the second. So the second is my prev, and actually can make it third, third, so it will be even more clear. Okay, so now I'm gonna, I'm gonna do a fib. I'm gonna update position. So fib is second and fib is third, and we're done here. Okay, so we will always have array of only two elements. It's start with 2, and then, um, we will return fib. Okay, and let's run that. It's 8. Uh, let's see just another one. 6, 7, just run it. 13. Um, so, uh, it's good. Let's go back to 6. Okay, so now our, uh, we have all of one space Because we only have array of 2 elements and our time complexity is O, okay? And, and in this case we are returning, um, the number n in the sequence, okay? Now what other questions can be asked? We also can ask the questions is return me all the n numbers, um, all of them in the array. Okay, so if we want, if we want that, so we're gonna create const getAllFibonacciNumbers, and actually I'm gonna Well, this is not, this is not what I, I really, um, now, now we really need to, um, I'm gonna create result. Result that start with 0 and 1, and it's gonna be actually the same function. Yes, so we push, we start i from 2 to n, and we push to the array previous number and the next number, and then we return res. Okay, and in this case we return the full sequence, get all Fibonacci numbers. Okay, this I'm gonna go— I'm gonna close this. Yeah, okay, so this is our sequence for 6 numbers. Um, well, it's, it's actually 7 numbers. I want to return 6 numbers. Okay, I want to return 6 numbers. Yeah, so okay, I want to return 6 numbers. In this case, the number that is passed is greater than 0. So n will be greater than 0, but in this case I can— you know, this number will be greater than 2. Um, yeah, because it doesn't make sense, uh, 0, 2. We can— we could do that, but Let's make this case when a number is greater than 2. And yeah, so we have our 6 Fibonacci numbers. Okay, great. So now also What also can be, what questions can be asked? Um, let's go back to previous number. So, um, getting Fibonacci number recursive and non-recursive. Um, so also it is O. Yes, so in But also, but also in this case, so actually for all of them, how can I, if I already made the calculations, how, how can I, how can I prevent calculating the same number again. Okay, so to prevent it is, is to use, to use cache, or it's called memoization. So we're gonna store the values that were already calculated in in the memo. And, and this way, so if we already calculated, for example, um, number of, um, it's also related to recursive and non-recursive, to all of them. So if we already calculated the number, can we get the same number with O, okay? And we can use memoization. So how can, how can we do that? So we can do it by, um, by using memo. So let's, let's create the same function but just call it memoized. const memoized. Okay, and here, and here we pass not, not only n, but we pass memo. Okay, so, and, and the memo is is_object. Okay, so here we ask if, if memo of n, return memo n. Okay, um, this is if it's, uh, exists there, so we return it. Else, we put to memo newly calculated value and we return it. Okay, so now I'm gonna, I'm gonna close this console. So now with memoized function, so which we also, we need to pass the memo to all our functions. Okay, um, so we will, um, we will define memo here. So memo needs to be external in order for us in order for us not to start it every time the function is calculated. So we do need memo to be external, and we, we're going to pass the memo to the function, um, like this. So it's 8, and then again It's 8, but if we will do maybe something more complex, maybe, maybe 10 will take— might take longer. Okay, so 10, it was pretty fast. Let's do 100. I think I'm gonna kill it. 50, let's do 50. Okay, now we can see It takes longer. Okay, I think I— it was not good. Too long. And it's recursive, so, or of 2^n. I think I killed it. Yeah, I don't know how to— okay, let's do 20 already big. Okay, maybe 2. Code is already running. Ah, cannot kill it now. It was not good. Ah, okay, I stopped it, stopped it here. Okay, let's run. Okay, it was 0.95. And now we go again. So how come? That's strange. And because every time— okay, every time we run it, start with empty array. Okay, so that makes sense. But let's clean it now and then I run it. Not sure if we can, if we can see that, but what we can do is we can print the memo. Okay, that's a good idea. So you can print the memo. Let's print the memo here and here. Memo, nothing. Memo 1. Yeah, okay, let's clean this and now let's print memo. We will start the— 40. Okay, so first took time, but the second one was— went straight ahead. So we can see that memo is working. So yes, just bear in mind that the memo should be outside. If you creating some service, so you can create a class where you will have the memo like a cache, and then you have the functions that gonna be using this memo. So you can, you wrap together as a function and the memo together and export from a singleton service your functions, and it will help the memo, and then it will actually contain all the, um, all the values and won't need to calculate it again. So in this case, case, we can see it very clearly because As a recursive function, gonna take much more time. But again, we can also do the memo on the, um, O calculation. So it will be very similar. Here we add in memo, and we also ask if our number is in memo. Then we return memo. Else, when you calculate, when you calculate the third number, um, so actually, um, every time we calculate the third number, uh, which is i We're gonna put the third in order to, to have it. And yes, and our memo will be full here. Again, by the end it returns the last one, but we set the memo. So the same here, Fibonacci with the memo. We will not see it that clear, but we can, we can try. Um, so, uh, here now we're passing. If we don't pass, it start with nothing, but the idea is to use the external memo. Um, so I'm going to just copy this. Sorry, I'm just going to copy this part. Let's copy this part and print it here. Just instead of it, Fibonacci num, um, Yeah, this one. And let's try that. Okay, so it also takes a calculation. I think there is another print somewhere here, didn't close it. Okay, let's clear again. Oh, we have a full memo, that's nice. So first it started with 0, but then we have a full memo, and now any number that is less than that will be with O. Okay, so this is, um, this is good how we can use the memo. So, and the same we can do for all the numbers. So we're gonna create here const memo R. We started with 0 and 1, it will be initial state, and we also pass it here. So if— so the way we're gonna fill it is, uh, we're filling, um, all the numbers, and because we're going from i 0 to n, then we fill in, uh, the array. So which means if i is 5, we know that all the numbers up to 5 were filled because we need them to calculate the next number. So const nextNumber, yeah, so this is our next Fibonacci number and we push it in the result array, but also we, um, we add to the memo. memo . Okay, so we're pushing them all the time. This is why, um, if Yeah, so if memo array at the place n— if memo array at the place n exists and it's a number, then we return, um, values from memo array but we slice it from 0 to n. Okay, so we slice it from 0 to n. Um, yeah, and then we return the result. So let's see, for 6, and we also want to print— let's console.log, um, the memo array. Memo array before, after, and I want to add maybe 20 numbers. Let's clear that for 20 numbers, and then I want to print it again. And then I want to do less, like 4 numbers. Let's run that. Cannot read. So, memo array. Okay, so yeah, so we want to ask first if, if memory length bigger or equal to n, and also memory. So let's clear that and go again. Length— I'm sorry, I didn't, I didn't pass memory here. Okay, I didn't pass, so it's actually not gonna fall, it's gonna say undefined. So this check is okay, that's fine. Okay, so first we return 6 items, yes, then we return 20, and then we return 4. So we can see that our array started with 2, then it grew, then it grew again. So we're still receiving the slice from this array and we don't need to calculate it, which is good. Okay, another question that is asked in relation to Fibonacci is— and yes, it's O. To calculate the same number second time will be obviously O. So, another question is asked is if the given number is a number from Fibonacci sequence. Okay, so how, how can we, how can we do it? We can go for through, we can loop through numbers calculating Fibonacci numbers, and if the next number that we're calculating is larger, then we missed it and then it doesn't exist. So let's, let's do what I mean. So I'm gonna take this function that calculating Fibonacci number. So for example, is we need to do function is_fibonacci_num. So I'm not gonna— well, we can use the memo, it doesn't really matter. But in this case, if we're receiving— we're receiving a number and we need to check— we're receiving a number, let's say so we're receiving a number and we need to check if this number is a Fibonacci number. So the first— well, we know if it is true and if it is equal to 0 or 1, it is true. This, this we know. It is 1, then it is true. And then we can loop while. So we are looping through numbers and we start with, um, let next Fibonacci number. So, so we start with two, um, const first, second, and, uh, the next going to be, uh, going to the next but we're gonna ask, um, while, while the next is smaller, um, or equal the number. So if next equals the number, we return true, then everything is let here. Let, let. Okay, then we're calculating next Fibonacci. First plus, first plus second. Yes, so if it's true and, and then if it's not, then we return false. Okay, so let's go console.log here isFibonacci, and I want to remove all the previous ones. Okay, it's gonna clear here. And memo array, is it used somewhere? Hmm, there is console.log somewhere. I'm gonna save it. Okay, let's clear and run again. Okay, it's true. What about 8? True too. What about 9? False. Okay, but the complexity of this function is, um, actually, you know what, I have already— it should be do-while. Okay, so do, uh, do and then while. Yeah, so So first I want to calculate the next one because I started with undefined. Okay, so I calculate the next one, and I do this, and I do this. Let's Close it. Yeah, because do-while, isn't it like that? Do-while. Yeah, let's try again. This is false. 8, this is true. 5. This is true. Okay, so because the second one, I'm calculating it here. Okay, so this is obviously gonna be, uh, O of, uh, um, I guess square of this number, um because we need to know which number it is. So we're obviously gonna, gonna be doing loops, I guess, all of O number of— yes, O when n is— what is the closest number to this. Okay, so that will be our complexity. But there is a mathematical way to, to check if the number is Fibonacci, and there is a sequence that goes like that. So if, um, if a number is a perfect square of this multiplied by the number, again by the number, minus 4, or 4. And, and this is the equation. So all, all we need to do is to implement this function. So Fibonacci number, so it's a perfect square, but now we need to implement const isPerfectSquare which will be calculating a square, and if this multiplied by this equals number. Another way to do it is also to ask if, if a square root of the number modulo 1 is 0. So it's also So we can also do it like that, like return is integer. Exactly, if, if mass square of the number is integer. Okay, so now, now we can compare our Fibonacci and Fibonacci mass. So I'm gonna do the mouse here. Yeah, this and, and this. So they both should have the same numbers because this is what we want to see. Want to just compare them for 5. You know what, we can just loop. Let's do for loop. For loop. Exactly. So the second one will be mass. And let's print it. Let's go. So both of them give the same result, it's just one of them is calculating it faster. So obviously the mass— and you can also do like If, if they are not equal, if this not equal to this, return what happened. What happened. So let's see if we're gonna get what happened. Oh, I didn't get what happened. So, um, okay, so this is the last one to check if number is a Fibonacci. So this is a specific equation, um, that you apply on a number, and, um, and then pretty much we went through all the variations of Fibonacci recursive loop with memoization, without memoization, and is_number_is_fibonacci. I hope you enjoyed it. Bye-bye.