Python Master

Posted on Edited on In , Symbols count in article: 6.1k Reading time ≈ 6 mins.

Summary

Advanced Python Usage.

References

functools — Higher-order functions and operations on callable objects

Cache

Fibonacci Number

509. Fibonacci Number

Recursion

As you can see, recursion is very slow since each step it calculates the pervious step again.

Python
1
2
3
4
5
6
7
8
9
10
%%time
# Recursion
# O(2^n), O(n)
class Solution:
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib(N - 1) + self.fib(N - 2)
    
Solution().fib(35)
1
2
3
CPU times: user 3.2 s, sys: 13.3 ms, total: 3.21 s
Wall time: 3.23 s
9227465

Top-Down Approach using Memoization (caching)

Python
1
from functools import cache
Python
1
2
3
4
5
6
7
8
9
10
11
12
13

```py Python
%%time
# Recursion - Cache
# O(2^n), O(n)
class Solution:
    @cache
    def fib(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib(N - 1) + self.fib(N - 2)
    
Solution().fib(35)
1
2
3
CPU times: user 72 µs, sys: 1 µs, total: 73 µs
Wall time: 77 µs
9227465

Top-Down Approach using Memoization

The above cache solution is the same as this one, the implementation of Memoization.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
%%time
# Memoization
# O(n), O(n)
class Solution:
    cache = {0: 0, 1: 1}

    def fib(self, N: int) -> int:
        if N in self.cache:
            return self.cache[N]
        self.cache[N] = self.fib(N - 1) + self.fib(N - 2)
        return self.cache[N]

Solution().fib(35)
1
2
3
CPU times: user 63 µs, sys: 1e+03 ns, total: 64 µs
Wall time: 67 µs
9227465

Iterative Bottom-Up Approach

Python
1
2
3
4
5
6
7
8
9
10
11
%%time
# Iterative Bottom-Up Approach
# O(n), O(1)
class Solution:
    def fib(self, n: int) -> int:
        f0, f1 = 0, 1
        for _ in range(n):
            f0, f1 = f1, f0 + f1
        return f0
    
Solution().fib(35)
1
2
3
CPU times: user 45 µs, sys: 1e+03 ns, total: 46 µs
Wall time: 50.1 µs
9227465

Staircase

70. Climbing Stairs

Recursion

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
%%time
# Recursion
# O(2^n), O(n)
class Solution:
    def climbStairs(self, n: int) -> int:  
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
    
Solution().climbStairs(35)
1
2
3
CPU times: user 2.3 s, sys: 11.1 ms, total: 2.31 s
Wall time: 2.32 s
14930352

Recursion - Caching

Python
1
from functools import cache
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
%%time
# Recursion - Cache
# O(n), O(n)
class Solution:
    @cache
    def climbStairs(self, n: int) -> int:  
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
    
Solution().climbStairs(35)
1
2
3
CPU times: user 74 µs, sys: 0 ns, total: 74 µs
Wall time: 78 µs
14930352

Iteration

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
%%time
# Iteration
# O(n), O(1)
class Solution:
    @cache
    def climbStairs(self, n: int) -> int:  
        if n == 1:
            return 1
        elif n == 2:
            return 2
        
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)
    
Solution().climbStairs(35)
1
2
3
CPU times: user 74 µs, sys: 0 ns, total: 74 µs
Wall time: 78 µs
14930352

Staircase II

Suppose there is a staircase that you can climb in either 1 step, 2 steps, or 3 steps. In how many possible ways can you climb the staircase if the staircase has n steps? Write a recursive function to solve the problem.

Example:

  • n == 1 then answer = 1

  • n == 3 then answer = 4

    The output is 4 because there are four ways we can climb the staircase:

    • 1 step + 1 step + 1 step
    • 1 step + 2 steps
    • 2 steps + 1 step
    • 3 steps

  • n == 5 then answer = 13

Recursion

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
%%time
"""
param: n - number of steps in the staircase
Return number of possible ways in which you can climb the staircase
"""
# O(2^n), O(n)
def staircase(n):
    '''Hint'''
    # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps.
    
    # Recursive Step - Split the solution into base case if n > 3.
    if n == 1: # 1
        return 1
    elif n == 2: # 1 - 1, 2
        return 2
    elif n == 3: # 1 - 1 - 1, 1 - 2, 2 - 1, 3
        return 4
    
    return staircase(n - 1) + staircase(n - 2) + staircase(n - 3)

staircase(30)
1
2
3
CPU times: user 3.93 s, sys: 24.3 ms, total: 3.95 s
Wall time: 3.98 s
53798080

Recursion - Caching

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
%%time
"""
param: n - number of steps in the staircase
Return number of possible ways in which you can climb the staircase
"""
# O(n), O(n)
@cache
def staircase(n):
    '''Hint'''
    # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps.
    
    # Recursive Step - Split the solution into base case if n > 3.
    if n == 1: # 1
        return 1
    elif n == 2: # 1 - 1, 2
        return 2
    elif n == 3: # 1 - 1 - 1, 1 - 2, 2 - 1, 3
        return 4
    
    return staircase(n - 1) + staircase(n - 2) + staircase(n - 3)

staircase(30)
1
2
CPU times: user 42 µs, sys: 5 µs, total: 47 µs
Wall time: 49.8 µs

Recursion II

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
%%time
"""
param: n - number of steps in the staircase
Return number of possible ways in which you can climb the staircase
"""
# O(2^n), O(n)
def staircase(n):
    '''Hint'''
    # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps.
    
    # Recursive Step - Split the solution into base case if n > 3.
    def _staircase(i, n): # i current staircases
        if i > n:
            return 0
        elif i == n:
            return 1
        return _staircase(i + 1, n) + _staircase(i + 2, n) + _staircase(i + 3, n)
    
    return _staircase(0, n)

staircase(30)
1
2
3
CPU times: user 24.1 s, sys: 90.9 ms, total: 24.2 s
Wall time: 24.4 s
53798080

Recursion II - Caching

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
%%time
"""
param: n - number of steps in the staircase
Return number of possible ways in which you can climb the staircase
"""
# O(n), O(n)
def staircase(n):
    '''Hint'''
    # Base Case - What holds true for minimum steps possible i.e., n == 0, 1, 2 or 3? Return the number of ways the child can climb n steps.
    
    # Recursive Step - Split the solution into base case if n > 3.
    @cache
    def _staircase(i, n): # i current staircases
        if i > n:
            return 0
        elif i == n:
            return 1
        return _staircase(i + 1, n) + _staircase(i + 2, n) + _staircase(i + 3, n)
    
    return _staircase(0, n)

staircase(30)
1
2
3
CPU times: user 59 µs, sys: 5 µs, total: 64 µs
Wall time: 66 µs
53798080

Iteration

Python
1
2
3
4
5
6
7
8
9
10
11
12
%%time
# Iteration
# O(n), O(1)
def staircase(n):
    # F0, F1, F2, F3
    #  1,  1,  2, F3 + F2 + F1
    a, b, c = 1, 1, 2
    for _ in range(n):
        a, b, c = b, c, a + b + c
    return a

staircase(30)
1
2
3
CPU times: user 25 µs, sys: 1e+03 ns, total: 26 µs
Wall time: 28.8 µs
53798080

Caching(manual)

Python
1
2
3
4
5
6
7
8
9
10
11
%%time
class Solution:
    cache = {1: 1, 2: 2, 3: 4}

    def staircase(self, N: int) -> int:
        if N in self.cache:
            return self.cache[N]
        self.cache[N] = self.staircase(N - 1) + self.staircase(N - 2) + self.staircase(N - 3)
        return self.cache[N]

Solution().staircase(30)
1
2
3
CPU times: user 64 µs, sys: 1e+03 ns, total: 65 µs
Wall time: 67.9 µs
53798080
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
%%time
def staircase(n):
    # Initiate cache
    cache = {1: 1, 2: 2, 3: 4}
    return staircase_func(n, cache)

def staircase_func(n, cache):
    if n in cache:
        return cache[n]
    cache[n] = staircase_func(n - 1, cache) + staircase_func(n - 2, cache) + staircase_func(n - 3, cache)
    return cache[n]

staircase(30)
1
2
3
CPU times: user 40 µs, sys: 1 µs, total: 41 µs
Wall time: 44.1 µs
53798080