# CSPT10 Hash Tables IV

## Fair Candy Swap

"""
https://leetcode.com/problems/fair-candy-swap/solution/

Understand

A = [1,1], B = [2,2]
[1,2]

A = [1], B = [2,3]
[1,3]

A = [1], B = [1]
[1,1]

Plan
For every candy x that Alice gives out, in order to have a fair swap, then she expects to get candy y in return.
Similar to Bob, if he gives out candy y, then he expects candy x in return. Since both of them need to have the same
amount of candies, we get the following equation:

sum(alice) - x + y = sum(bob) - y + x

If we solve for y, then we get the following:
2y = sum(bob) - sum(alice) + 2x
y = (sum(bob) - sum(alice) + 2x) / 2
y = (sum(bob) - sum(alice) / 2) + x

Therefore, if we try each candy x that Alice has, if Bob has candy y then we can do a fair swap. We use a set so that
we don't have to go through all of Bob's candies.

Runtime: O(alice num candies + bob num candies)
Space: O(bob num candies)
"""

class Solution:
    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
        bobCandies = set(B)
        bobSum, aliceSum = sum(B), sum(A)
        for x in A:
            y = ((bobSum - aliceSum) / 2) + x
            if y in bobCandies:
                return [x, y]
        return []

## 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
"""

class Solution:
    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)
"""

class Solution:
    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]

## Server Demo

import random

class Server:
    cache = {}

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

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

server = Server()
server.processGETRequest('hello')
server.processGETRequest('bar')
server.processGETRequest('hello')
server.processGETRequest('baz')
server.processGETRequest('hello')