Chapter 8: Data Structures Used in Algorithms
8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms
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!
8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms
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!
8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms
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!
8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms
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!