
"""
Calculate the nth fibonacci number in O(n) time
note that the formula for the nth fibonacci number is fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
The base case: Fibonacci(n) = 1 if n <= 2
"""
def fibonacci(n):
	pass



"""
Determine the frequency of each element in the list. 
Return a dictionary where the keys are the elements, and their frequencies are the values.
This should run in linear time.
"""
def count_freqs(array):
	pass

"""
Determine if 3 elements of the array can sum to the target value.
Note, that your solution should be faster than O(n^3)
"""
def three_sum(array, target):
	pass

"""
Given an array, determine the distance (difference) between the closest two values
Your algorithm should be as efficient as possible
Input:
	[5,14,3, 77]
Output:
	2, since 5 and 3 have a distance of 2
"""
def find_closest(array):
	pass



"""
Let A and B be two sorted arrays. Assume all the numbers in both arrays are unique. 
We define a greater pair as a pair of elements (a,b) where a is an element of A and b is element of B and a < b.
Describe an efficient algorithm to determine the number of pairs given arrays A and B. 
Make your solution as fast as possible
Input:
	A = [9,14]
	B = [5,11,16]
Output:
	3
	Since we have hte pairs (11,9), (16,9), (16, 14)
as
"""
def count_greater_pairs(A, B):
	pass