8.5 Practice Problems

Problem 1: Arrays - Maximum Subarray Sum

Problem: Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Solution: We can solve this problem using Kadane's algorithm. Here is a Python code for this problem.

def max_subarray(nums):    if not nums:        return 0     curr_sum = max_sum = nums[0]     for num in nums[1:]:        curr_sum = max(num, curr_sum + num)        max_sum = max(max_sum, curr_sum)     return max_sum print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # output: 6

Problem 2: Linked Lists - Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution: We can solve this problem by iteratively reversing the pointers of the linked list.

class ListNode:    def __init__(self, x):        self.val = x        self.next = None def reverseList(head):    prev = None    curr = head    while curr:        next_temp = curr.next        curr.next = prev        prev = curr        curr = next_temp    return prev

Problem 3: Stacks - Valid Parentheses

Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and open brackets must be closed in the correct order.

Solution: This problem can be solved by using a stack.

def isValid(s):    stack = []    mapping = {")": "(", "}": "{", "]": "["}    for char in s:        if char in mapping:            top_element = stack.pop() if stack else '#'            if mapping[char] != top_element:                return False        else:            stack.append(char)    return not stack print(isValid("()[]{}"))  # output: True

Problem 4: Trees - Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution: This problem can be solved by using a depth-first search (DFS) algorithm.

class TreeNode:    def __init__(self, x):        self.val = x        self.left = None        self.right = None def maxDepth(root):    if root is None:        return 0    else:        left_height = maxDepth(root.left)        right_height = maxDepth(root.right)        return max(left_height, right_height) + 1

Remember to take some time to understand these problems and their solutions. Practice is the key to mastering the use of these data structures. Happy coding!