Unit 10 Session 2 Standard (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:
flights = {
'LAX': ['SFO'],
'SFO': ['LAX', 'ORD', 'ERW'],
'ERW': ['SFO', 'ORD'],
'ORD': ['ERW', 'SFO', 'MIA'],
'MIA': ['ORD']
}
start = 'LAX'
destination = 'MIA'
Output:
['LAX', 'SFO', 'ORD', 'MIA']
Explanation: The path LAX -> SFO -> ORD -> MIA is the shortest path with the least layovers.
EDGE CASE
Input:
flights = {
'LAX': ['SFO'],
'SFO': ['LAX'],
'MIA': []
}
start = 'LAX'
destination = 'MIA'
Output:
[]
Explanation: There is no possible path from LAX to MIA.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 Shortest Path problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use BFS to explore the shortest path from the source to the destination. At each step, keep track of the path taken so far. When the destination is reached, return the path.
1) Initialize a queue with the `source` location and the path containing only the `source`.
2) Create a `visited` set to track locations that have already been visited to avoid cycles.
3) While the queue is not empty:
a) Dequeue the current location and its corresponding path.
b) If the current location is the `destination`, return the path.
c) For each neighbor of the current location, if it has not been visited, enqueue it with the updated path and mark it as visited.
4) If the queue is exhausted and no path is found, return an empty list `[]`.⚠️ Common Mistakes
source is the same as the destination for early termination.Implement the code to solve the algorithm.
from collections import deque
def find_shortest_path(flights, source, destination):
queue = deque([(source, [source])]) # Start with source in the path
visited = set()
while queue:
current, path = queue.popleft()
if current == destination:
return path
visited.add(current)
for neighbor in flights.get(current, []):
if neighbor not in visited:
queue.append((neighbor, path + [neighbor])) # Add neighbor to the path
return []Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
flights = {
'LAX': ['SFO'],
'SFO': ['LAX', 'ORD', 'ERW'],
'ERW': ['SFO', 'ORD'],
'ORD': ['ERW', 'SFO', 'MIA'],
'MIA': ['ORD']
}
print(find_shortest_path(flights, 'LAX', 'MIA')) # Expected output: ['LAX', 'SFO', 'ORD', 'MIA']
print(find_shortest_path(flights, 'LAX', 'MIA')) # Should return an empty list if no path is found['LAX', 'SFO', 'ORD', 'MIA']
[]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 vertices (locations) and E is the number of edges (flights). Each location is dequeued and processed once, and each flight (edge) is explored once.
Space Complexity: O(V) for storing the visited set and queue.
Adjacency Matrix vs. Adjacency List: If an adjacency matrix is used, the time complexity would change to O(V^2), since we would need to iterate over all possible locations (V) for each vertex when checking neighbors.
