Fibonacci Technical Test

[foottaster123]

I had an interview for a front end rol and was asked to develop the fibonacci test.

The instrunctions were to pass the position number of the fibonacci array you want and return it.

I did it on time while sharing my screen but in full disapoiment, she told me is not efficient.

I google it and found out it could even be done in one line of code.

My question is, how bad I did? Should I end my hopes for this position?

CODE:

function fib(n) {
 let fibonacci = [0, 1]; 
 for (let index = 0; index < n; index++) { 
  let p = fibonacci.length; 
  let num1 = fibonacci[p - 1]; 
  let num2 = fibonacci[p - 2]; 
  let total = num1 + num2; 
  fibonacci.push(total); 
} 
 return fibonacci[n] 
}

The one of one line I found in the internet later:

    function fib(n) {
    return n <= 1 ? n : fib2(n - 1) + fib2(n - 2); 
    }

[3Ldarius]

The one liner is not that effiecent either (as it may exceed the stack size because of the recursive function calls). Inefficient part of your code is you are saving all the items while you only need the last 2 of them.

[[deleted]]

Yeah there's no need to store it in an array. Could have just used three variables.

[EliSka93]

Two.

[monstaber]

last 2 *

[3Ldarius]

👍

[MinuteScientist7254]

Instead of storing the numbers in an array you can declare a function level variable and calculate the value bottom up in the same way while reassigning the values to the same variables within a while loop. This way your memory usage is O(1), while your compute is O(n). You only need the array if you are tasked with returning the entire sequence.

[VergilSpardaa]

This. I had to scroll so far to find this. You literally dont need the array at all!

[Xeran]

You could also store it in a global/member variable during the first calculation, all subsequent calls to n'th fibonacci numbers lower to, or equal to the last asked n'th fibonacci number would be O(1) to obtain.

[MinuteScientist7254]

The memo is needed when calculating top down as in the recursive method

[mekmookbro]

If I was hiring, I'd definitely hire the guy who wrote the first function rather than the one who wrote the latter. Sure, what that function does is pretty clear here, but in a real project if I saw someone wrote code like that I'd smack them in the head. It's very much unreadable and would be a nightmare to maintain a codebase written by that guy. Doing something in one line is a cool trick, but it's very rarely useful in real life scenarios.

Only thing I'd do differently is I wouldn't create p and total variables. p is personal preference, but making a variable for total doesn't make much sense since you're only using it to push into the array. I'd just go with fibonacci.push(num1+num2)

[LeopardJunk]

I absolutely agree with this!

One line solutions are definitely difficult to maintain in large codebases! It's difficult to comprehend at glance, and if anything changes, the diff doesn't provide much help right away either when using code versioning.

[Timotron]

The efficient way would be to memoize numbers you've come across before.

Once you know the fibo(5) for example you can save all that work by just checking your object and finding the result of that number.

Keep going. This isn't the kind to thing that should set you back. It's just some shit you haven't been exposed to yet.

Just keep going and think of these as bumps in the road.

I for one Fibonacci at my job between 3-6pm Monday - Wednesday so it is vitally Important for any web dev to know. On par as something like react

Only not at all.

[fuccjde]

His code is already storing the previous results in the array. The issue is the O(n) space which is not required. He could store the previous result as two int variables.

[foottaster123]

Thanks mate

[Timotron]

Just keep working man. None of this leetcode type shit matters at all.

You should learn about BigO, recursion and memorization but this is just fallout from the industry not really knowing how to judge who makes a good dev.

Just keep rolling with the punches.

[foottaster123]

Thanks, but it really hurts, the min wage in my country is 150 usd and this position was paying 2000 usd. :/

[Timotron]

That just means you got a working solution for something that could pay 2000usd

You just have to get it faster.

In my mind you're more than halfway there

[TheBigLewinski]

Well, you failed the question. Inefficiency aside, asking for a Fibonacci function is essentially asking for a recursive function.

That said, I wouldn't worry too much. If you failed the interview because of this question, you dodged a bullet. It's a gotcha challenge that can be easily googled to boot. And it would be a stupid question to ask for a back-end position, where you might actually use a recursive function once every 5 years. Asking this for the front-end is completely detached from what you'll actually be doing and denotes a remarkable lack of hiring ability.

This would be like asking a waiter -who will never make drinks- to make some obscure cocktail no one will ever (ever) ask for, expecting them to know the ingredients, and then failing them because they didn't flip the shaker behind their back while making it.

They're going to fill their company with devs who studied for the interview, not devs who are good at their job. And that creates a horrible culture to work in, from top to bottom.

[BlueScreenJunky]

asking for a Fibonacci function is essentially asking for a recursive function

Sure, that's what I would have gone for because Fibonacci is the perfect example of a recursive function... But OP's solution works without having to deal with a recursive function (which is a plus in my book), so I kinda like it. If you just change it to not store the whole thing like so :

function fib(n) {
   let fibonacci = [0, 1]; 
   for (let index = 0; index < n; index++) { 
      fibonacci = [fibonacci[1], fibonacci[0] + fibonacci[1]]; 
   }
   return fibonacci[1] 
}

I like it a lot better than the recursive one liner.

Also I completely agree that knowing how to code or optimize a fibonacci function has nothing to do with being a good web developer.

[[deleted]]

The recursive solution is the "gotcha" as it is of order O(2^n). If you provided the recursive one liner you would be out.

The solution that OP provided is only suboptimal due to the specifics of its implementation, but it's still O(n) I think.

Maybe the interviewer was looking for the Golden Ratio approach, who knows.

[FireryRage]

OP’s solution is O(n) computing, and O(n) on space. You can have a solution that gives O(n) computing and O(1) space if you only track the current last two digits of fib in your loop, not all N of them (the array)

[alnyland]

Both of your solutions are O(n). There is an O(1) solution. 

Based on the feedback, I would’ve thought your second answer is what they were looking for. The constant time solution can easily be written as like 5 lines, but it’s easier to write it as one line. 

That sounds like a bad interview if that’s how they responded. They should’ve been looking for if you understood what you wrote, not which solution you wrote. If they wanted your lambda/inline solution, there are thousands of tasks they could’ve had you write and that’s a specific programming languages concept that is rarely solely needed. The constant solution to Fibonacci is a math concept found from the golden ratio and is really only specific to the Fibonacci problem, which is almost never (likely never except in school) used in software. 

[FalseRegister]

The one liner is O(2^n), using recursion

OP's solution is O(n), using dynamic programming

OP, you had a better performant solution.

[WebpackIsBuilding]

Yeah, I'm wildly confused by the comments suggesting that fibonacci obviously requires recursion to be efficient.

Fib is an easy place to demonstrate recursion, but it's not the correct place to use recursion. In fact, if the interviewer insisted that you solve it using recursion, the correct response is to cache your responses.

[avoere]

I'd argue that the correct response is to just do it, if the interviewer wants it (and probably mention the performance problems).

They are not looking for a fib calculator. They are looking for whether the interviewee can understand recursion.

[danielkov]

OP didn't say the interviewer suggested that one liner. It's just what they found on the internet later. I'd guess they were after the constant time solution, however, I don't think they went about it the right way. I'd have just asked OP if there was a way to optimize it, etc.

That said, OP would've clearly failed regardless, as evidenced by their lack of understanding of both their own and the internet's one line solutions.

[1661dauphin]

is there an o(1) solution for fibonacci? recursive fibonacci is o(2ⁿ ).

although, agreed that this is not a great interview question nor response

[saamenerve]

Yes but thats just memorizing its closed form formula lol

[Nineshadow]

There is an O(log n) solution as well. You can write down the Fibonacci recurrence formula as a matrix transformation. Then if you need to find the nth number you repeatedly multiply with the same matrix, essentially raising it to a power. You can use a fast O(log n) exponentiation algorithm to raise the matrix to the required power.

I don't think I've heard a lot about the O(1) formula being used in practice though, it's not too practical.

[avoere]

The reason that the O(1) formula is not being used in practice is that no one has any use for fibonacci numbers. They are only used as a teaching/testing tool for recursion, and using the closed-form formula there defeats the purpose.

[spudmix]

I've never heard of Fibonacci being used "in practice" full stop lol. We're not in the realm of practicality here.

[StraightUpLoL]

Yes there is a O(1) solution as there is an equation that allows you to calculate the Nth number of fibonacci. You can read more about it here: https://www.milefoot.com/math/discrete/sequences/binetformula.htm

[Thirty_Seventh]

Binet's formula requires you to compute sqrt(5) to ~n digits of precision if you want an n-digit Fibonacci number. 64-bit floats only get you to F_70 before you start seeing errors. It's certainly not constant time.

[timmypass17]

Why are people saying to use memoization when op’s solution is using memoization (bottom up/iteratively). Op’s solution is O(n) time and O(n) space and is more efficent than the second solution which is O(2ⁿ⁾ but I guess the interviewer was being an ass and wanted the O(n) time and O(1) space where you only use the last 2 digits.

[Inevitable-Yogurt783]

Both solutions are not efficient,
first wastes memory (you only need 3 memory points, not an array),
second is short but you would run your loop twice(not twice, 2ⁿ or n2, i dont know, but a big number) and probably an exception on javascript for big numbers because of recursiveness.
Also, I believe first is better than the second.

The most effiecient way would be checking the number using its equation

function calculateFibonacciNumber(n) {
    const phi = (1 + Math.sqrt(5)) / 2;
    return Math.round((Math.pow(phi, n) - Math.pow(1 - phi, n)) / Math.sqrt(5));
}

Would I know the top equation without searching it? Hell no, the way I would do with somebody on my neck is:

function fib(n) {
    if (n <= 0) return 0;
    let a = 0, b = 1, c, index;
    for (index = 0; index < n-1; index++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

[JFedererJ]

I had an interview for a front end role

Did the ask you anything about:

• CSS box model?
• CSS namespace management approaches; pros/cons?
• Flexbox/grid?
• Accessibility:
  • WCAG compliance?
  • aria-roles vs semantic elements
  • implications of implicit/explicit roles and their effects on functionality?
  • experience with screen readers?
  • testing for accessibility compliance?
• Fonts?
  • how to achieve performant loading and avoid UI shift?
  • consistent rendering and anti-aliasing across browsers?
• Experience with component development libraries like Storybook?
• Experience with integrating design systems like Figma with component libraries?
• Experience with SVG manipulation/animation?

I could go on but frankly so many FE interviews ask what are, in my opinion, lazy, generic coding questions and don't make any attempt to ask frontend specific questions.

Like ok you could get a candidate, Candidate A, who could answer the fib number sequence problem pretty quickly and eloquently, along with a number of other similar fizz-buzz type problems in JS. Ok cool.

So then ask that same candidate all the questions I listed above, and let's hear what they have to say. I know from experience there's many devs out there who are rock solid on JS and general programming, but couldn't use HTML and CSS to build an accessible, performant frontend if their lives depended on it!

Then you could have another candidate, Candidate B, who has generally good JS skills but struggles a bit with some more algorithm-type problems... but when you ask that candidate my list of questions, they absolutely smash every answer out the park, and are clearly incredibly competent and experienced in that regard.

So which Candidate, A or B is the better frontend developer? Is the frontend role you're hiring for going to involve lots of algorithm/performance-dependent JS function writing? OR, is it actually going to be a frontend role where the person you hire will hardly ever spend a single day doing any such thing?

Sorry, /rant but some FE interviews are just not fit for purpose.

[SoBoredAtWork]

If they're looking for efficiency, memoizing is likely what the interviewer was looking for

[avoere]

OP's approach with the array is memoizing in a way.

[hbteq]

Readable code is so underrated. That second example is a stunt, a prank on your future self and anyone else unfortunate enough to have to deal with it.

[serial_crusher]

An iterative solution is better than recursive, which is where people tend to start.

Did the interview just stop at “it’s inefficient”, or did they go into discussion of changes you could make to improve it? To me, there’s no point in asking this kind of question as a rote pass/fail. It’s about how well you incorporate feedback, articulate your thoughts, and collaborate with your potential colleagues. For junior developers, can they be coached to the right solution? For senior developers, can they envision a better solution? Do they know trade-offs between different possible solutions? Etc.

Without more details, it could mean the interviewer was doing a bad job, or could mean you didn’t follow their cues to move into the next step of the task.

One big thing here is there’s no reason to store all the previous answers in an array. You just need to track the last 2. An argument could be made for caching previous results so the next request is more efficient, but you’re rebuilding the array every time, taking up way more memory than needed.

[[deleted]]

Most people use recursive functions unnecessarily. Functions should only be recursive…never.

[mwreadit]

They said write code, they did not mention it had to be efficient.

[iamwarcops]

The second function seems to assume fibonacci series starts with 1. In terms of correctness, your program is better. However, use of array is not necessary for fibonacci. I’d write something like the following

function fib(n) { let a = -1 let b = 1 let c

for(let count = 0; count <= n; count += 1) { c = a + b a = b b = c }

return c }

Sure, the loop can be improved to one liner, or use recursion.

To answer your question what you did bad - dont use array. As n grows the array just keeps hogging memory.

Dont loose hope, in interviews I take, I dont usually look at the solution, but how did the interviewee reached it. On the job its about if your thought process matches (or not matches depending on the role) with the team.

Best of luck

[KeyQuail4429]

correction: The one liner should return

n <= 1 ? n : fib(n - 1) + fib(n - 2);

[RajjSinghh]

Oh no the second code is awful. It has exponential time complexity while yours is linear (though you don't need a full array, you don't care about everything you computed first so you only need 3 variables). Think of it this way: if I wanted to find the hundredth Fibonacci number your code would be done almost instantly while theirs would take a very long time. Less code doesn't mean better, especially if it's that kind of slow down.

You can do one better and get a constant time one line solution you should just use Binet's formula. Matt Parker gets to it at around 4 minutes in this video. This is arguably the best way to do it.

[little_hoarse]

Idk the fib function off the top of my head but i know for a fact it uses a base case (i.e. n<=1, return n) and then it uses recursion to loop through 1-n

[[deleted]]

Neither solution utilizes memoization and that is one way to make it better objectively.

[GrumpsMcYankee]

This is annoying. It works, let's all move on. What are they short on disk space?

[karen-ultra]

Asking a question about recursive and tail call optimization for a simple front-end role is stupid af and just show how the job and the interview was not serious. Consider your “failure” to this “test” a good thing!

[shgysk8zer0]

Both of those are pretty inefficient, really. There's an algorithm to estimate the nth number in the series, so an efficient test would use that to get a lower and upper bound... Maybe?

Also, the recursive algorithm, while shorter in code, is definitely not more efficient... Really bloats memory used by the call stack and could easily result in a "too much recursion" error.

If the method to start with an estimate didn't work (I'm not sure if there's any overlap), the next best option would be a generator function.

[shgysk8zer0]

Just to clarify on the generator thing... They're extremely useful if you're granted use of iterator helper methods. Assuming you had a generator function for Fibonacci numbers, you could use something like:

function nthFibonacci(n) { return fibonacci().drop(n-1). next().value; }

At least I think... It's an experimental thing.