Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.
This week’s challenge is a very common interview question and was reported to have been asked in interviews at many top companies including Google:
Basic Difficulty
Write a function, fibonacciFinder50, that will find the 50th number in the Fibonacci Sequence.
Function Name: fibonacciFinder50
Input: There are no parameters to this function
Output: an integer, the 50th number in the Fibonacci Sequence
Example: fibonacciFinder50() => 7778742049
In the Fibonacci Sequence, the first two numbers are 0 and 1 and every number thereafter is the sum of the previous two numbers in the sequence
For this challenge, consider 0 to be the 1st Fibonacci Number, not the 0th (i.e. do not zero-index)
Can you solve this challenge in O(n) time complexity?
Many of you will still find that this challenge is too easy (and this is not unusual), so see how you can stretch yourself further. Can you solve this problem in an unorthodox or elegant way? How about in a different language? Take this opportunity to show off your scripting skills and creative outside-the-box thinking!
Reply to this thread with a link to your code on repl.itand paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.
As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.
Hard
This is solved pretty straight on with Python3. Now to explore some alternative ways maybe! https://repl.it/IwYR/0
def fibonacciFinderN(n):
# if n < 1, n is rejected
if n < 1:
return
# if n == 1, 0 is returned right away because the initial state of x, y, z already
# move the sequence past n == 1
if n == 1:
return 0
x = 0
y = 1
z = 1
i = 3
# Here the while loop will do a single pass for 1-n, while accumulating the fibonacci number
# and thus making the algorithm directly proportional with the size of n.
# This makes the time complexity O(n).
while i <= n:
z = x + y
x = y
y = z
i += 1
return z
print(fibonacciFinderN(300))
#Basic difficulty
#simply execute the Fibbonnaci Sequence until the 50th number is found
def fibonacciFinder50():
fibonacci_number = 2 #this variable will show the place of the current fibonacci_number in the sequence of results; in this case what matter is when this variable reaches 50; it starts at 2 because we already know the 1st and 2nd numbers of the sequence: 0 and 1
a = 0 #first value of the sequence
b = 1 #second value of the sequence
c = b #holds the value of b
while fibonacci_number != 50:
fibonacci_number += 1 #increment the count along with getting the next fibonacci number
b += a #b just gets added the current value of a
a = c #a becomes the previous value of b; which is held in c
c = b #now "reset" c to the current value of b
else:
return b #in this case it returns the 50th number in the Fibbonnaci Sequence
print('fibonacciFinder50() =>', fibonacciFinder50())
#Intermediate difficulty
#basically the same as basic difficulty, except the sequence is executed until the nth number is found, in this example it's the 300th number
def fibonacciFinderN(n):
fibonacci_number = 2 #this variable will show the place of the current fibonacci_number in the sequence of results; in this case what matter is when this variable reaches 50; it starts at 2 because we already know the 1st and 2nd numbers of the sequence: 0 and 1
a = 0 #first value of the sequence
b = 1 #second value of the sequence
c = b #holds the value of b
if n < 1: #if n is lower than 1 prompt the user for another n until n is 1 or higer
while n < 1:
n = int(input('That\'s not a valid number. Choose a number higher than 1. '))
if n == 1:
return a
elif n == 2:
return b
else:
while fibonacci_number != n:
fibonacci_number += 1 #increment the count along with getting the next fibonacci number
b += a #b just gets added the current value of a
a = c #a becomes the previous value of b; which is held in c
c = b #now "reset" c to the current value of b
else:
return b #in this case it returns the 50th number in the Fibbonnaci Sequence
print('fibonacciFinderN(300) =>', fibonacciFinderN(300))
// Hard difficulty
// Even though most every recursive lesson works on the Fib sequence
// it is much more efficient AND easier to solve this problem with
// a simple for loop.
function fibonacciFinderN(n) {
"use strict";
let pre = 0, // Fib(1)
cur = 1, // Fib(2)
fib = 0; // Usually 'next' but given a semantic name here
// an n of 0 will return early
if (n === 0) return;
// an n of 1 will return '0'
// an n of 2 will return '1'
if (n === 2) return cur;
// this solution is similar to array.prototype.reduce
// 'i' starts at 2 since our first two fibs are provided
for (let i = 2; i < n; i++) {
fib = pre + cur;
pre = cur;
cur = fib;
}
return stringIt(fib);
}
function stringIt(num) {
"use strict";
let n = num, // n starts as full number and is shaved down
x = 0, // x becomes the digit shaved and added to string
s = ""; // the string accumulator
while(n > 0) {
x = n % 10; // get the ones digit
s = x + s; // prepend it to the string accumulator
n = Math.trunc(n / 10); // shave/shift the number by one digit
}
return s;
}
console.log(fibonacciFinderN(300));
I’ve been working on learning C++ but don’t yet know how to implement a large enough integer to output the 300th fib. Here is my C++ solution though it still cannot express large enough numbers.
EDIT: apparently my comments weren’t in the initial link.
EDIT 3: Upon being prompted I have reviewed the submission guidelines and adapted my answer accordingly.
EDIT 4: Ok, I think I have finally conformed to the submission requirements.
# There is no reason to calculate a constant
def fibonacciFinder50():
return 7778742049
def fibonacciFinderN(N):
a,b,n = 0,1,2
if N==1:
return a
if N==2:
return b
if N>50:
a,b,n=4807526976,7778742049,50
while n < N:
a,b,n = b,a+b,n+1
return b
print 'fibonacciFinder50() =>', fibonacciFinder50()
print 'fibonacciFinderN(300) =>', fibonacciFinderN(300)
function fibonacciFinderN(n) {
if( typeof n !== "number" || n%1 !== 0 || n <= 0 ) return;
let [last, fib] = [0, 1];
for( let i = 2, next = 0; i < n; i++ ) {
next = fib + last;
last = fib;
fib = next;
}
return n > 1 ? fib : 0;
}
console.log(fibonacciFinderN(103)); // last with regular notation
console.log(fibonacciFinderN(300));
I’m assuming that first number is 0, so fibonacciFinderN(1) is equal to 0.
Instead of using recursion, which was very slow I decided to use a simple for loop to run n times and calculate each fibonacci number up to N-th. This function also checks if user input is actually integer.
It could mean doing digit by digit math on two strings to create the mathematical result in a thrid string. Long additon on strings, as it were.
Edit
function fib(n) {
let a = 0;
let b = 1;
let f = '';
let i = 2;
let c;
while (i++ < n) {
c = a + b;
a = b;
b = c;
console.log(i,c);
}
/* accurate to 15 digits
x = c;
while (x > 0) {
f = (x % 10).toString(10) + f;
x = Math.floor(x / 10);
}
return [f, c, i];
*/
return c;
}
console.log(fib(104));
The code above generated our example. In comments is the modulo discovery of the number which proves out the limitations of natural tracking. Stings are the only sure way to preserve integrity.
class Fibonacci{
public void fibonacciFinder50(){
long n=0, m=1,x=0;
for(int i=0;i<50;i++){
if(i<=1)
x=i;
else{
x=n+m;
n=m;
m=x;
}
}
System.out.println(x);
}
}
class Main{
public static void main(String[]args){
Fibonacci f = new Fibonacci();
f.fibonacciFinder50();
}
}
Everybody, please read the posting guidelines to this challenge. Your formatted (markdown) code must be in the submission. The repl.it link is only so readers can explore. Please precede the link with at least one space or some text so the applet does not have to download. Thanks.
Math Behind:
If you workout the formula for f3 to f11 as a function of f1 & f2, e.g.
f3 = f1+f2
f4 = f3 + f2 = (f1+f2) + f2 = f1 + 2f2
f5 = f4 + f3 = (f1 + 2f2) + (f1+f2) = 2f1+3f2
…
f11 = 34f1 + 55f2
f12 = 55f1 + 89f2
This means that, given f1 & f2, f11 & f12 can be obtain using formula above
Notice that, f12 = 55 * f1 + 89 * f2
55 = #11 Fibonacci Number
89 = #12 Fibonacci Number
Here is my submission for all difficulties, Python 3:
I initially considered a recursive solution, as being more intuitive.
After all the Fibonacci formula is; F(n) = F(n-1) + F(n-2).
But I dismissed it as being too inefficient.
I went with the following ( O(N), I believe ) iterative solution instead :
def fibonacciFinder50():
a,b = 1,0
for i in range(49):
a,b = a+b,a
return b
def fibonacciFinderN(n):
a,b = 1,0
for i in range(n-1):
a,b = a+b,a
return b
print("fibonacciFinder50()=")
print(fibonacciFinder50() )
print("fibonacciFinderN(300)=")
print(fibonacciFinderN(300) )
I realize that there is an unused addition, a+b in the last iteration,
But I find this acceptable compared to adding more complication to avoid it.
Python 3 for Basic, Intermediate, and Hard difficulty
# Make algorithm to find fibonacci 50
def fibonacciFinder50():
# Create counter
z = 1
# Start the fibonacci sequence
x = 0
y = 1
# Loop through while less than 50
while z < 50:
# Make x = y at the same time that y = x + y, and increase counter by 1
x, y, z = y, x + y, z + 1
# Return fibonacci at index 50
return x
fibonacciFinder50()
print(fibonacciFinder50())
# Make algorithm to find fibonacci 50
def fibonacciFinderN(n):
# Start the fibonacci sequence
x = 0
y = 1
# Loop through while number is greater than 1 because of index starting at 1 instead of 0
while n > 1:
# Make x = y at the same time that y = x + y, and decrease n by 1
x, y, n = y, x + y, n - 1
# Return fibonacci at index n
return x
fibonacciFinderN(300)
print(fibonacciFinderN(300))
#fibonacciFinder50 finds the 50th number in the fibonacci sequence
#(where 0 is the first number)
def fibonacciFinder50():
z = 0 #arbitrary counter
seq = [0, 1]
while z < 48: #first two given thus stops after 48 loops
seq.append(seq[z] + seq[z+1]) #creates a running sum
z += 1
return seq[-1]
print(fibonacciFinder50())
This was a pretty straightforward program to write. I would also just like to say I really enjoy these math based challenges!
from time import time
#fibonacciFinderN finds the Nth number in the Fibonacci sequence
#(where 0 is the first number)
def fibonacciFinderN(n):
z = 0 #arbitrary counter
seq = [0, 1]
while z < n - 2: #first two given thus stops after 48 loops
seq.append(seq[z] + seq[z + 1]) #creates a running sum
z += 1
return seq[-1]
start = time()
f = fibonacciFinderN(100)
end = time()
print("Function1: %s\nTime: %s" % (f, end - start))
```
Thank you @b-twin looking at your code in the last challenge I learned how to test run time and format it how I liked. Again, a pretty straightforward program to write.
https://repl.it/IxyG/7
Hard difficulty in Java
I used the golden ratio to solve the challenge. the complexity depends on how efficient Math.pow() is.
It seems to overflow for large values due to that function though.
public class Main
{
public static final double phi = 1.61803398875;
public static void main(String[] args)
{
System.out.println(fibonacciFinderN(49));
}
public static long fibonacciFinderN(int n)
{
n--;
return (long)(Math.pow(phi,n)/Math.sqrt(5)-Math.pow(1-phi,n)/Math.sqrt(5));
}
}
#include<iostream>
using namespace std;
// This will work for the 50th Fibonacci number but an unsigned long
// long int is not large enough for the 300th.
long int fibonacciFinder50()
{
long int pre = 0;
long int cur = 1;
long int fib = 0;
for (int i = 2; i < 50; ++i) {
fib = pre + cur;
pre = cur;
cur = fib;
}
return fib;
}
int main()
{
cout << fibonacciFinder50() << '\n';
return 0;
}
Intermediate, Python 3
I started with the list[None, 0, 1] so the list index will match the number in the fibonacci sequence(not necessary but makes the code look nicer) , then I just added the last two numbers in the list and appended that to the end of the list and repeated until I reach the fibonacci number I need.
def fibonacciFinderN(n):
"""Returns nth item in fibonacci sequence"""
# started list with None to imitate the list starting with index 1 so fibonacci_list[1] and the first fibonacci number will match up
fibonacci_list = [None, 0, 1]
# if n <= 2, return the value already in the table
if n <= 2:
return fibonacci_list[n]
while len(fibonacci_list) <= n:
# adds the last two items in fibonacci_list then appends the sum to the list
fibonacci_list.append(fibonacci_list[-1] + fibonacci_list[-2])
return fibonacci_list[n]
print(fibonacciFinderN(300))