Unit 10 Session 2 Standard (Click for link to problem statements)
Unit 10 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?
venue_map represent?
venue_map[i] contains j, there is a hallway between room i and room j.target?
None.HAPPY CASE
Input:
```python
venue_map = [
[1, 2],
[0, 3],
[0, 4],
[1, 5],
[2],
[3]
]
target = 5
```
Output:
```markdown
[0, 1, 3, 5]
Explanation: The path from room 0 to room 5 is 0 -> 1 -> 3 -> 5. This is one valid solution, though other paths may also exist.
```
EDGE CASE
Input:
```python
venue_map = [
[1],
[0],
]
target = 1
```
Output:
```markdown
[0, 1]
Explanation: Room 1 is directly connected to room 0, so the path is simply [0, 1].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 Path Finding problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use DFS to explore all possible paths from room 0 (entrance) to the target room. Start from room 0 and attempt to visit all connected rooms, backtracking if necessary. If the target room is found, return the current path.
1) Define a recursive DFS function that takes the current room and the current path as parameters.
2) Add the current room to the path.
3) If the current room is the `target`, return the current path.
4) For each connected room, if it has not been visited yet (not in the path), recursively explore the path.
a) If a valid path is found, return it.
b) If no valid path is found, backtrack by removing the current room from the path.
5) Start DFS from room 0.⚠️ Common Mistakes
Implement the code to solve the algorithm.
def find_path(venue_map, target):
def dfs(room, path):
# Add the current room to the path
path.append(room)
# If we've reached the target, return the path
if room == target:
return path
# Explore all connected rooms
for neighbor in venue_map[room]:
if neighbor not in path: # Avoid revisiting rooms
result = dfs(neighbor, path)
if result: # If we found the target, return the path
return result
# Backtrack if this path doesn't lead to the target
path.pop()
return None
# Start DFS from room 0
return dfs(0, [])Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
venue_map = [
[1, 2],
[0, 3],
[0, 4],
[1, 5],
[2],
[3]
]
print(find_path(venue_map, 5)) # Expected output: [0, 1, 3, 5]
print(find_path(venue_map, 2)) # Expected output: [0, 2][0, 1, 3, 5]
[0, 2]Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(V + E), where V is the number of rooms (vertices) and E is the number of connections (edges). Each room and its connections are explored once.O(V) for storing the current path and recursion stack.