Python refresher - 1
SORT
#Bubble sort
#Runtime O(n^2) Memory O(1)- working in place without additional DS
def bubbleSort(arr): n = len(arr) swapped = False for i in range(n - 1): swapped = False for j in range(n - i - 1): if arr[j] > arr[j + 1]: swapped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] print(arr)# more detailed print if not swapped: #if the first iteration in the inner loop don't swap the elements # means they are all in order already? return#Test 1 #arr = [64, 34, 25, 12, 22, 11, 90] # [64, 34, 25, 12, 22, 11, 90] # [34, 25, 12, 22, 11, 64, 90] # [25, 12, 22, 11, 34, 64, 90] # [12, 22, 11, 25, 34, 64, 90] # [12, 11, 22, 25, 34, 64, 90] # [11, 12, 22, 25, 34, 64, 90] # Sorted array is: # 11 12 22 25 34 64 90
#Test 2
# arr = [5, 3, 12, 34]
# 5, 3, 12, 34]
# [3, 5, 12, 34]
# [3, 5, 12, 34]
# Sorted array is:
# 3 5 12 34
#Test 3
# arr= [10, 1, 10,20,0]
# [10, 1, 10, 20, 0]
# [1, 10, 10, 0, 20]
# [1, 10, 0, 10, 20]
# [1, 0, 10, 10, 20]
# Sorted array is:
# 0 1 10 10 20
#Test 4#arr = []
#Sorted array is:
#Test 5 #arr = [0,1,2,3,4,5,6]
# [0, 1, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6]
# Sorted array is:
# 0 1 2 3 4 5 6
#If we add the swapped- logic : we catch the pre-sorted arrays : test 5:
# [0, 1, 2, 3, 4, 5, 6]
# Sorted :
# 0 1 2 3 4 5 6
#Test 6, with the swap logic# arr = [1,0,2,3,4,5,6]
#[1, 0, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 4, 5, 6]
# Sorted :
# 0 1 2 3 4 5 6
#Test 7 with the swap logic# arr = [0,1,3,2,3,4,5,6]
# [0, 1, 3, 2, 3, 4, 5, 6]
# [0, 1, 2, 3, 3, 4, 5, 6]
# Sorted :
# 0 1 2 3 3 4 5 6
#Test 8 with more detailed print *
# arr = [7,5,6,10,4,1]
# [5, 7, 6, 10, 4, 1]
# [5, 6, 7, 10, 4, 1]
# [5, 6, 7, 4, 10, 1]
# [5, 6, 7, 4, 1, 10]
# [5, 6, 4, 7, 1, 10]
# [5, 6, 4, 1, 7, 10]
# [5, 4, 6, 1, 7, 10]
# [5, 4, 1, 6, 7, 10]
# [4, 5, 1, 6, 7, 10]
# [4, 1, 5, 6, 7, 10]
# [1, 4, 5, 6, 7, 10]
# Sorted :
# 1 4 5 6 7 10
bubbleSort(arr)
print("Sorted :")
for i in range(len(arr)):
print("% d" % arr[i], end=" ")Recursion
"""
RECURSION
Recursive function is made of two parts :
at least one base case
that directly specify the output for some special cases
at least one recursive case
that defines the output of in terms of
the output of a simpler version of the case
"""
#Example 1: natural numbers factorial (N + 1)! = (N + 1) * N! where 1! = 1
#N is a natural number => N > 0
def factorial(n):
if type(n) != int or n < 1 :
return print(f'Invalid input {n}') #O(1) const
if n == 1:
print(f' base case n = {n}') #O(1) const
return n
else:
print(f' recursive case n = {n}')
return n * factorial(n - 1) #O(n-1)
#O = O(1) + O(1) + O(n-1) => O(n)
#Test cases
factorial(5)
factorial(1)
factorial(0)
factorial(-1)
factorial("a")
factorial(3.14)#Example 2 - finding Big O
def recursiveFun1( n):
if (n <= 0):
print(f'base case for {n}') #O(1)
return 1
else:
print(f'recursive case for {n}')
return 1 + recursiveFun1(n-1) #(O(n-1) => O(n))
recursiveFun1(5)
# Returns:
# recursive case for 5
# recursive case for 4
# recursive case for 3
# recursive case for 2
# recursive case for 1
# base case for 0
###########################################################Example 3 - finding Big O
def recursiveFun2(n):
if (n <= 0):
print(f'base case for {n}') #O(1)
return 1
else:
print(f'recursive case for {n}')
return 1 + recursiveFun2(n-5) #O(n/5)
recursiveFun2(25)
#Returns:
# recursive case for 25
# recursive case for 20
# recursive case for 15
# recursive case for 10
# recursive case for 5
# base case for 0
##########################################################
#Example 4 - finding Big O
def recursiveFun3(n):
if (n <= 0):
print(f'base case for {n}') #O(1)
return 1
else:
print(f'recursive case for {n}')
return 1 + recursiveFun3(n/5) # O(log5(n))
#
#recursiveFun3(1) #returns 463+ 1 cases
#recursiveFun3(5) #returns 464+ 1 cases
#recursiveFun3(10) #returns 465+ 1 cases
#recursiveFun3(20) #returns 465+ 1 cases
#recursiveFun3(50) #returns 466+ 1 cases
#recursiveFun3(100) #returns 466+ 1 cases
#recursiveFun3(1000) #returns 468+ 1 cases
#Example 4A - Simplified example 4 for clearer logic.
def recursiveFun4(n):
if (n < 1):
print(f'base case for {n}') #O(1)
return 1
else:
print(f'recursive case for {n}')
return 1 + recursiveFun4(n/5) #0(log5(n))
#Note about logarithms loga(n) = x => ax = n ; e.g. log2(8) = x, 2x=8 =>x =3
#recursiveFun4(1) log5(1) = x ; 5x = 1 => x=0
#recursive case for 1
# base case for 0.2
#recursiveFun4(5)
#returns
# recursive case for 5
# recursive case for 1.0
# base case for 0.2
#recursiveFun4(10)
#returns
#recursive case for 10
# recursive case for 2.0
# base case for 0.4
#recursiveFun4(20)
# recursive case for 20
# recursive case for 4.0
# base case for 0.8
#recursiveFun4(50)
#returns
# recursive case for 50
# recursive case for 10.0
# recursive case for 2.0
# base case for 0.4
#recursiveFun4(100)
# recursive case for 100
# recursive case for 20.0
# recursive case for 4.0
# base case for 0.8
#recursiveFun4(1000)
# returns
# recursive case for 1000
# recursive case for 200.0
# recursive case for 40.0
# recursive case for 8.0
# recursive case for 1.6
# base case for 0.32
##########################################################
Example for recursion, inspired by Google's coding interview questions, and returned by Gemini in response to a prompt about recursion( beside the Fibonacci numbers) :Here's an example of a Google-style recursion question, focusing on both recursion and dynamic programming:
Problem:
Given a staircase with n steps, a person can climb either 1 or 2 steps at a time. How many distinct ways can they climb the entire staircase?
Example:
n = 3 (3 steps)
They can climb: 1 step, 1 step, 1 step (1 way)1 step, 2 steps (1 way)2 steps, 1 step (1 way)
Total ways for n = 3: 3