Unit 9 Session 1 (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?
hotel
is None
?
HAPPY CASE
Input:
hotel = Room("Lobby",
Room(101, Room(201, Room(301)), Room(202)),
Room(102, Room(203), Room(204, None, Room(302))))
Output: {
0: ['Lobby'],
1: [101, 102],
2: [201, 202, 203, 204],
3: [301, 302]
}
EDGE CASE
Input: hotel = None
Output: {}
Explanation: The tree is empty, so return an empty dictionary.
Input: hotel = Room("Lobby")
Output: {0: ['Lobby']}
Explanation: The tree has only one node, so return a dictionary with one key-value pair.
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 problems involving mapping the nodes of a binary tree by level, we can consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
1) Initialize:
hotel
is empty (None
), return an empty dictionary.level_map
to store the mapping of levels to room values.
2) Level Order Traversal:level_map
, add it with an empty list.level_map
.level_map
dictionary.Pseudocode:
1) If `hotel` is `None`, return an empty dictionary.
2) Initialize a queue with `(hotel, 0)` and an empty dictionary `level_map`.
3) While the queue is not empty:
a) Dequeue a node and its level.
b) If `level` is not in `level_map`, add it as a key with an empty list as its value.
c) Append the node's value to `level_map[level]`.
d) If the node has a left child, enqueue it with `level + 1`.
e) If the node has a right child, enqueue it with `level + 1`.
4) Return the `level_map` dictionary.
Implement the code to solve the algorithm.
from collections import deque
class TreeNode:
def __init__(self, value, left=None, right=None):
self.val = value
self.left = left
self.right = right
def map_hotel(hotel):
if not hotel:
return {}
# Initialize the queue and the dictionary
queue = deque([(hotel, 0)])
level_map = {}
while queue:
node, level = queue.popleft()
# Check if the level already exists in the dictionary
if level not in level_map:
level_map[level] = []
# Add the current node's value to the corresponding level in the dictionary
level_map[level].append(node.val)
# Add the children to the queue with the next level
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
return level_map
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
hotel = Room("Lobby", Room(101, Room(201, Room(301)), Room(202)), Room(102, Room(203), Room(204, None, Room(302))))
:
level_map
.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of nodes in the tree.
O(N)
because each node in the tree must be visited to build the level map.O(N)
due to the queue storing nodes at each level during traversal and the level_map
dictionary storing the room values.