Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Be sure that you clarify the input and output parameters of the problem:
O(n)
time and O(n)
space will do. Run through a set of example cases:
HAPPY CASE
Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
EDGE CASE
Input: n = 0
Output: 0
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
Plan the solution with appropriate visualizations and pseudocode.
Solution 1:
General Idea: Bottom-Up DP Technique, we will build up our answer.
1. Create a array to store fibonacci numbers to build upon
a. Set the given numbers fibonacci at 0 is 0 and fibonacci at 1 is 1.
2. From the given numbers we can build up to any number of fibonacci.
a. Fibonacci is the result of the addition of the two previous numbers.
b. Append such numbers to array until array has reached target number
4. Return the target fibonacci number stored in our array
Solution 2:
General Idea: Top-Down DP Technique, we will recursively build up to our answer.
1. Create helper function to process fibonacci numbers
a. Basecase: Fibonacci number was found in our cache
b. Recursively call for the answer to our target fibonacci number
2. Create cache by using dictionary to store past result for quick look up when recursively asking for answer to the target fibonacci number
3. Call our helper function and return the answer
Solution 3:
General Idea: Top-Down DP Technique, we will recursively build up to our answer using a functool called @cache to store our past results from recursive calls used to calculate our target fibonacci nunber.
1. Declare that we would like to cache for our function
2. Set basecase 0 and 1
3. Return the recursive call to obtain our target fibonacci number
Solution 4:
General Idea: Bottom-Up DP Technique, we will build up our answer.(Using O(1)
space)
0. Set basecase if target is 0 or 1 return n
1. Create a variable for fibonacci numbers to build upon
a. Set the given numbers fibonacci at n-2 to be 0 and fibonacci at n-1 to be 1.
2. From the given numbers we can build up to any number of fibonacci.
a. Fibonacci is the result of the addition of the two previous numbers.
b. Set n-2 to be n-1 and set n-1 to be n-2 + n-1
3. Return the n-2 + n-1 as the target fibonacci number
⚠️ Common Mistakes
O(n)
runtime expectations. Otherwise it will be O(n!)
.Implement the code to solve the algorithm.
Solution 1:
class Solution:
def fib(self, n: int) -> int:
# Create a array to store fibonacci numbers to build upon
# Set the given numbers fibonacci at 0 is 0 and fibonacci at 1 is 1.
fib = [0,1]
# From the given numbers we can build up to any number of fibonacci
for i in range(2, n+1):
# Fibonacci is the result of the addition of the two previous numbers
# Append such numbers to array until array has reached target number
fib.append(fib[i-1] + fib[i-2])
# Return the target number stored in our array
return fib[n]
class Solution {
public int fib(int N) {
// Create a array to store fibonacci numbers to build upon
int[] map = new int[N+2];
// Set the given numbers fibonacci at 0 is 0 and fibonacci at 1 is 1
map[0] = 0;
map[1] = 1;
// From the given numbers we can build up to any number of fibonacci
for (int i = 2; i <= N; i += 1) {
map[i] = map[i-1] + map[i-2];
}
// Return the target number stored in our array
return map[N];
}
}
Solution 2:
class Solution:
def fib(self, n: int) -> int:
# Create helper function to process fibonacci numbers
def helper(i) -> int:
# Basecase: Fibonacci number was found in our cache
if i in fibMemo:
return fibMemo[i]
else:
# Recursively call for the answer to our target fibonacci number
fibMemo[i] = helper(i-1) + helper(i-2)
return fibMemo[i]
# Create cache by using dictionary to store past result for quick look up when recursively asking for answer to the target fibonacci number
fibMemo = {0:0, 1:1}
# Call our helper function and return the answer
return helper(n)
class Solution {
public int fib(int N) {
// initialize our memoization map and put our base cases
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// Create cache by using dictionary to store past result for quick look up when recursively asking for answer to the target fibonacci number
map.put(0, 0);
map.put(1, 1);
// call helper function
return fib(N, map);
}
// Create helper function to process fibonacci numbers
private int fib(int N, HashMap<Integer, Integer> map) {
// Basecase: Fibonacci number was found in our cache
if (!map.containsKey(N)) {
// Recursively call for the answer to our target fibonacci number
int currentFib = fib(N - 1, map) + fib(N - 2, map);
map.put(N, currentFib);
}
return map.get(N);
}
}
Solution 3:
class Solution:
@cache
def fib(self, n: int) -> int:
if n == 0 or n == 1:
return n
return self.fib(n-1) + self.fib(n-2)
Solution 4:
class Solution:
def fib(self, n: int) -> int:
# Set basecase if target is 0 or 1 return n
if n == 0 or n == 1:
return n
# Create a variable for fibonacci numbers to build upon
# Set the given numbers fibonacci at n-2 to be 0 and fibonacci at n-1 to be 1
n_minus_two, n_minus_one = 0, 1
# From the given numbers we can build up to any number of fibonacci
# Fibonacci is the result of the addition of the two previous numbers
for i in range(2, n):
# Set n-2 to be n-1 and set n-1 to be n-2 + n-1
n_minus_two, n_minus_one = n_minus_one, n_minus_two + n_minus_one
# Return the n-2 + n-1 as the target fibonacci number
return n_minus_two + n_minus_one
class Solution {
public int fib(int N) {
// Set basecase if target is 0 or 1 return n
if (N==0 || N==1) {
return N;
}
// Create a variable for fibonacci numbers to build upon
// Set the given numbers fibonacci at n-2 to be 0 and fibonacci at n-1 to be 1
int nMinusTwo = 0, nMinusOne = 1;
int sum = 0;
// From the given numbers we can build up to any number of fibonacci
// Fibonacci is the result of the addition of the two previous numbers
while (N > 2) {
// Set n-2 to be n-1 and set n-1 to be n-2 + n-1
int temp = nMinusTwo + nMinusOne;
nMinusTwo = nMinusOne;
nMinusOne = temp;
// decrement counter
N -= 1;
}
return nMinusTwo + nMinusOne;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the target fibonacci number
O(N)
, because we need to dig down or build up to the N
fibonacci number and require n-1 and n-2 fibonacci numbers of which require n-1 and n-2 fibonacci, until the base case.O(N)
/O(1)
, because for the Top-Down approach we need to store fibonacci numbers until N
. However for the Bottom-Up approach we could push the space complexity to O(1)
by reusing the n-2 and n-1 variables.