TIP102 Unit 9 Session 2 Standard (Click for link to problem statements)
TIP102 Unit 9 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input:
pumpkin_sizes = [1, 3, 2, 5, 3, None, 9]
pumpkin_patch = build_tree(pumpkin_sizes)
Output:
[1, 3, 9]
Explanation:
The largest pumpkins in each row are 1, 3, and 9, respectively.
EDGE CASE
Input:
pumpkin_sizes = [7]
pumpkin_patch = build_tree(pumpkin_sizes)
Output:
[7]
Explanation:
There is only one row with a single pumpkin of size 7.Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Level Order Traversal problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a BFS approach to traverse the tree level by level. For each level, track the maximum value of the nodes. Append the maximum value to the result list after processing all nodes at that level.
1) Define a function `largest_pumpkins(pumpkin_patch)`:
- If `pumpkin_patch` is `None`, return an empty list.
- Initialize an empty list `result` to store the largest pumpkin sizes.
- Initialize a queue with the root node of the tree.
- While the queue is not empty:
- Determine the number of nodes at the current level (`level_size`).
- Initialize a variable `max_val` to negative infinity to track the maximum pumpkin size at this level.
- For each node in the current level:
- Dequeue a node and update `max_val` if the node's value is greater.
- Enqueue the left and right children of the node if they exist.
- Append `max_val` to the `result` list.
- Return `result`.⚠️ Common Mistakes
Implement the code to solve the algorithm.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def largest_pumpkins(pumpkin_patch):
if not pumpkin_patch:
return []
result = []
queue = deque([pumpkin_patch])
while queue:
level_size = len(queue)
max_val = float('-inf') # Initialize to negative infinity for comparison
for _ in range(level_size):
node = queue.popleft()
max_val = max(max_val, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(max_val)
return result
# Example Usage:
pumpkin_sizes = [1, 3, 2, 5, 3, None, 9]
pumpkin_patch = build_tree(pumpkin_sizes)
print(largest_pumpkins(pumpkin_patch)) # [1, 3, 9]Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
- Example 1:
- Input:
`pumpkin_sizes = [1, 3, 2, 5, 3, None, 9]`
`pumpkin_patch = build_tree(pumpkin_sizes)`
- Execution:
- Perform BFS to traverse the tree level by level.
- Track the maximum pumpkin size at each level.
- Output:
[1, 3, 9]- Example 2:
- Input:
`pumpkin_sizes = [7]`
`pumpkin_patch = build_tree(pumpkin_sizes)`
- Execution:
- Perform BFS to traverse the tree level by level.
- Track the maximum pumpkin size at each level.
- Output:
[7]Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(N) where N is the number of nodes in the tree.
O(W) where W is the maximum width of the tree.
W nodes at the widest level of the tree.
~~~