# Coding Book

# DFS&BFS
from collections import deque

class Node:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def dfs(node):
    if not node:
        return None

    dfs(node.left)
    print(node.val)
    dfs(node.right)

def bfs(root):
    if not root:
        return None

    q = deque()
    q.append(root)
    while q:
        node = q.popleft()
        print(node.val)

        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

root = Node(4)
root.left = Node(3)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(2)

dfs(root)
bfs(root)

# DP
def rob(houses):
    h1 = houses[0]
    h2 = max(houses[0], houses[1])
    for i in range(2, len(houses)):
        h3 = max(houses[i]+h1, h2)
        h1 = h2
        h2 = h3

    return h2

def rob_circle(houses):
    return max(rob(houses[1:]), rob(houses[:-1]))

def maxSubArray(nums):
    curr_sum = nums[0]
    max_sum = nums[0]
    for i in range(1, len(nums)):
        curr_sum = max(curr_sum+nums[i], nums[i])
        if curr_sum > max_sum:
            max_sum = curr_sum
    return max_sum

def maxSubArray_circle(nums):
    curr_max = total_max =nums[0]
    curr_min = total_min =nums[0]
    totals = nums[0]

    for i in range(1, len(nums)):
        curr_max = max(curr_max+nums[i], nums[i])
        if curr_max > total_max:
            total_max = curr_max
        curr_min = min(curr_min + nums[i], nums[i])
        if curr_min < total_min:
            total_min = curr_min
        totals += nums[i]
    return max(total_max, totals-total_min) if total_max > 0 else total_max

# Linked List
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge(list1, list2):
    new_head = dummy_head = Node()
    while list1 and list2:
        if list1.val < list2.val:
            dummy_head.next = list1
            list1 = list1.next
        else:
            dummy_head.next = list2
            list2 = list2.next
        dummy_head = dummy_head.next
    if list1:
        dummy_head = list1
    if list2:
        dummy_head = list2
    return new_head.next

list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(4)

list2 = Node(1)
list2.next = Node(3)
list2.next.next = Node(4)

merged_list = merge(list1, list2)
head = merged_list
while head:
    print(head.val)
    head = head.next

# Binary Search
def binary_search(nums, target):
    left = 0
    right = len(nums)-1

    while left <= right:
        mid = (left+right)//2

        if target < nums[mid]:
            right = mid-1
        elif target > nums[mid]:
            left = mid+1
        else:
            return mid

    return left

# Quick Sort
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = []
    right = []
    for i in range(1, len(arr)):
        if arr[i] < pivot:
            left.append(arr[i])
        else:
            right.append(arr[i])
    return quick_sort(left)+[pivot]+quick_sort(right)

###### tags: `interview` `python`