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?
flights represent?
i to j, then there is also a flight from j to i.HAPPY CASE
Input:
flights = {
'JFK': ['LAX', 'SFO'],
'LAX': ['JFK', 'SFO'],
'SFO': ['JFK', 'LAX'],
'ORD': ['ATL'],
'ATL': ['ORD']
}
Output:
1
Explanation: The airports form two connected components: {'JFK', 'LAX', 'SFO'} and {'ORD', 'ATL'}. Only one flight is needed to connect the two components.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 Graph Connectivity problems, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We need to find the number of connected components in the graph. The minimum number of flights required to connect all airports will be equal to the number of components minus one. Use DFS to explore each component and count how many components exist.
1) Build an undirected graph from the `flights` dictionary. Make sure all airports are properly connected in both directions.
2) Initialize a `visited` set to track the airports that have already been explored.
3) Use DFS to traverse through each connected component.
a) For each unvisited airport, perform a DFS to explore all airports in its component.
b) Increment the number of components whenever a new component is found.
4) The minimum number of flights needed to connect all components is `(number of components - 1)`.⚠️ Common Mistakes
Implement the code to solve the algorithm.
def min_flights_to_expand(flights):
# Step 1: Build an undirected graph from the flights dictionary
graph = {}
for airport in flights:
if airport not in graph:
graph[airport] = set()
for destination in flights[airport]:
graph[airport].add(destination)
if destination not in graph:
graph[destination] = set()
graph[destination].add(airport)
# Step 2: Use DFS to find connected components
def dfs(airport, visited):
stack = [airport]
while stack:
node = stack.pop()
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)
visited = set()
num_components = 0
# Step 3: Traverse through each airport and find new connected components
for airport in graph:
if airport not in visited:
# New component found, run DFS
visited.add(airport)
dfs(airport, visited)
num_components += 1
# Step 4: The minimum number of flights needed is (number of components - 1)
return num_components - 1Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
flights = {
'JFK': ['LAX', 'SFO'],
'LAX': ['JFK', 'SFO'],
'SFO': ['JFK', 'LAX'],
'ORD': ['ATL'],
'ATL': ['ORD']
}
print(min_flights_to_expand(flights)) # Expected output: 11Evaluate the performance of your algorithm and state any strong/weak or future potential work.
O(V + E), where V is the number of airports (vertices) and E is the number of flights (edges). We build the graph and then use DFS to explore all vertices and edges.O(V + E) for storing the graph and visited set.