Practice1.py

# Recursion
def fibonaci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonaci(n-1) + fibonaci(n-2)

def factorial(n):
    if n == 1 or n == 0:
        return 1
    return factorial(n-1)*n
    
def factorialIter(n):
    product = 1
    while n > 1:
        product = product*(n)
        n -= 1
    return n
    
def powerset(arr):
    lis = []
    for i in range (0, len(arr)+1):
        for j in range (i+1, len(arr)+1):
            lis.append(arr[i:j])
    return (lis)
arr = [3,-9,2,5,1]
print(powerset(arr))

# Binary Search

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1
        
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo+hi)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
    
def searchRotatedArray(arr, target):
    lo = 0
    hi = len(arr) - 1
    while (lo <= hi):
        mid = (lo+hi)//2
        if arr[mid] == target:
            return mid
        # case 1 arr[lo] > arr[mid] -> we have pivot in between
        if arr[lo] > arr[mid]:
            if target >= arr[lo] or target <= arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # case 2 arr[lo] < arr[mid] -> no pivot normal binary search
        else:
            if target > mid:
                lo = mid + 1
            else:
                hi = mid - 1

def searchRotatedArrayWithDuplicates(arr, target):
    # worst runtime: O(N)
    # space = O(1)
    # avg.runtime = O(log N)
    lo = 0
    hi = len(arr) - 1
    while (lo <= hi):
        mid = (lo+hi)//2
        if arr[mid] == target:
            return mid
        while (lo != mid and arr[mid] == arr[lo]):
            lo += 1
        # case 1 arr[lo] > arr[mid] -> we have pivot in between
        if arr[lo] > arr[mid]:
            if target >= arr[lo] or target <= arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # case 2 arr[lo] < arr[mid] -> no pivot normal binary search
        else:
            if target > mid:
                lo = mid + 1
            else:
                hi = mid - 1

def binarySearchCompare(nums):
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = (lo+hi)//2 
        if nums[mid] > nums[mid+1]:
            hi = mid
        else:
            lo = mid + 1
    return lo
    
    


def binarySearchlo(nums, target):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target and (mid == 0 or nums[mid-1] < target):
            idx =  mid
            break
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    
    lo, hi = idx, len(nums)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target and (mid == hi or nums[mid+1] > target):
            idx2 = mid
            break
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return [idx, idx2]
        
nums = [7,2,6,8,8,9]
target = 8

print(binarySearchlo(nums, target))

def findMin(nums):
    
    lo, hi = 0, len(nums-1)
    while lo < hi:
        mid = (lo + hi)//2
        if nums[mid] < nums[mid+1]:
            lo = mid + 1
        else:
            hi = mid 
nums = [4,5,6,7,0,1,2]
print(findMin(nums))

def binaryMatrix(numbers, target):
    n = len(matrix[0])
    lo, hi = 0, len(matrix) * n
    while lo < hi:
        mid = (lo + hi) // 2
        x = matrix[mid//n][mid%n]
        if x < target:
            lo = mid + 1
        elif x > target:
            hi = mid
        else:
            return True
    return False

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 30
print(binaryMatrix(matrix, target))
    
# BST

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
class BST:
    def __init__(self):
        self.root = None
    #prints our BST in string format
    def __str__(self):
        return binaryTreeToStr(self.root)
    
    # return true if value exists in BST
    def getIterative(self, val):
        cur = self.root
        while(cur):
            if cur.val == val:
                return true
            elif cur.val > val:
                cur = cur.left
            else:
                cur = cur.right
        return False
    
    def getRecursive(self, val):
        return self._getRecursive(val, self.root)

    def _getRecursive(self, val, curNode):
        if not curNode:
            return False
        if curNode.val == val:
            return true
        elif curNode.val > val:
            return _getRecursive(val, curNode.left)
        else:
            return _getRecursive(val, curNode.right)
    
    def insertRecursive(self, val):
        self.root = self._insertRecursive(val, self.root)
        
    def _insertRecursive(self, val, curNode):
        if not curNode:
            return Node(val)
        if curNode.val > val:
            curNode.left = self._insertRecursive(val, curNode.left)
        else:
            curNode.right = self._insertRecursive(val, curNode.right)
        return curNode

def maximum_depth(root):
    if root is null:
        return 0
    left_depth = maximum_depth(root.left)
    right_depth = maximum_depth(root.right)
    return max(left_depth, right_depth) + 1

def validateBST(tree):
    return self._validateBST(tree, float("-inf"), float("inf"))

def _validateBST(tree, minValue, maxValue):
    if tree is None
        return True
    if tree.value < minValue or tree.value >= maxValue:
        return False
    leftIsValid = _validateBST(tree.left, minValue, tree.value)
    return leftIsValid and _validateBST(tree.right, tree.value, maxValue)