Graphing Flights - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Graphs, Adjacency List

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 kind of graph representation should be used?
    • A: The problem explicitly asks for an adjacency dictionary to represent the graph.
  • Q: Is the graph directed or undirected?
    • A: The graph is undirected.
  • Q: Do all airports need to have at least one connection?
    • A: Yes, every airport in the example has at least one connection.
HAPPY CASE
Input: Create an adjacency list for a graph with nodes representing airports (JFK, LAX, DFW, ATL) and flights between them.
Output: {
  'JFK': ['LAX', 'DFW'],
  'LAX': ['JFK'],
  'DFW': ['ATL', 'JFK'],
  'ATL': ['DFW']
}
Explanation: Each airport has flights to the airports listed in its adjacency list.

EDGE CASE
Input: A graph with no edges between airports.
Output: {
  'JFK': [],
  'LAX': [],
  'DFW': [],
  'ATL': []
}
Explanation: Airports have no connections.

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 Graph Representation problems, we want to consider the following approaches:

  • Adjacency List: Since the problem requires an adjacency dictionary, we can represent each airport as a key in the dictionary and the connected airports as a list of neighbors.
  • Adjacency Matrix: Not required here, but another common graph representation.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to represent the graph, where each airport is a key, and the values are lists of airports that have direct flights from the key airport.

1) Create a dictionary where each key is an airport and each value is a list of airports it has a direct flight to.
2) For each flight between two airports, add the destination to the adjacency list for the source and vice versa (because the graph is undirected).
3) Return the completed adjacency dictionary.

⚠️ Common Mistakes

  • Forgetting to make the graph undirected (i.e., adding the connection in both directions).
  • Failing to include all airports, even those with only one flight connection.

4: I-mplement

Implement the code to solve the algorithm.

flights = {
  'JFK': ['LAX', 'DFW'],
  'LAX': ['JFK'],
  'DFW': ['ATL', 'JFK'],
  'ATL': ['DFW']
}

5: R-eview

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

  • Input: Print out the keys and values of the adjacency list.
  • Check if the flight connections are correctly established in both directions.

Example:

print(list(flights.keys()))  # ['JFK', 'LAX', 'DFW', 'ATL']
print(list(flights.values()))  # ['LAX', 'DFW'], ['JFK'], ['ATL', 'JFK'], ['DFW'](/codepath/compsci_guides/wiki/'LAX',-'DFW'],-['JFK'],-['ATL',-'JFK'],-['DFW')
print(flights[""JFK""])  # ['LAX', 'DFW']

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 vertices (airports) and E is the number of edges (flights). We need to process each vertex and each edge once.
  • Space Complexity: O(V + E) as we store the adjacency list, which takes space proportional to the number of vertices and edges.