Press Junket Navigation - codepath/compsci_guides GitHub Wiki

Unit 10 Session 2 Standard (Click for link to problem statements)

Unit 10 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-30 mins
🛠️ Topics: Graph Traversal, DFS, Backtracking

1: U-nderstand

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?

Q: What does the adjacency list venue_map represent?
- A: It represents the connections between rooms in the venue. If venue_map[i] contains j, there is a hallway between room i and room j.
Q: Can there be multiple valid paths to the target?
- A: Yes, and the problem allows any valid path to be returned.
Q: What should be returned if no path is found?
- A: If no valid path exists from the entrance to the target room, the function should return 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].

2: M-atch

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:

Depth First Search (DFS) with backtracking: DFS allows us to explore all possible paths from the entrance to the target room. Backtracking helps us undo partial paths when they do not lead to the target.

3: P-lan

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

Forgetting to backtrack by removing the current room from the path when a dead end is reached.
Revisiting rooms, which could lead to cycles and infinite recursion.

4: I-mplement

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, [])

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input:

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]

Output:

[0, 1, 3, 5]
[0, 2]

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity: 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.
Space Complexity: O(V) for storing the current path and recursion stack.