# CSPT13 Hash Tables IV
## [Fibonacci](https://leetcode.com/problems/fibonacci-number/)

"""
Understand

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Input: 5
Output:
Explanation: F(5) = F(4) + F(3) = 3 + 2 = 5

Show them that things are being recomputed again

Plan
Use memoization to cache previously computed values to avoid recomputing them again

Runtime: O(N) Each number, starting at 2 up to and including N, is visited, computed and then stored for O(1)O(1) access later on.
Space: O(N) The dictionary will have at most N key-value pairs
"""
def fib(self, N: int) -> int:
        computedValues = {1: 1, 0: 0}
        return self.memoizedFib(N, computedValues)

    def memoizedFib(self, N, computedValues):
        if N in computedValues:
            return computedValues[N]
        computedValues[N] = self.memoizedFib(N - 1, computedValues) + self.memoizedFib(N - 2, computedValues)
        return computedValues[N]

## [Climbing Stairs](https://leetcode.com/problems/climbing-stairs/)

"""
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Plan

Use top-down approach and memoization to avoid pre-computing values.
To get the number of ways to reach the Nth step, add the number of ways
to reach the n - 1th step + n - 2nd step.

Runtime: O(n)
Space: O(n)
"""
def climbStairs(self, n: int) -> int:
        computedValues = {0: 0, 1: 1, 2: 2}
        return self.memoizedClimbStairs(n, computedValues)

    def memoizedClimbStairs(self, n, computedValues):
        if n in computedValues:
            return computedValues[n]
        computedValues[n] = self.memoizedClimbStairs(n - 1, computedValues) + self.memoizedClimbStairs(n - 2, computedValues)
        return computedValues[n]

## Caching Example

import random
import time

class Server:
    # url -> response
    cache = {}

    def processGETRequest(self, url):
        if url in self.cache:
            print(url + ' is already in the cache')
            return self.cache[url]
        print(url + ' is not cached yet. Computing...')
        self.cache[url] = self.doExpensiveComputation(url)
        print('caching ' + url + ' with value ' + str(self.cache[url]))
        return self.cache[url]

    def processPUTRequest(self, url):
        # update DB with new values
        # evict url from the cache

    def doExpensiveComputation(self, url):
        time.sleep(5)
        return random.randint(0, 101)


server = Server()
server.processGETRequest("google.com")
server.processGETRequest("google.com")
server.processGETRequest("facebook.com")