Converting Flight Representations - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graphs, Adjacency List, Edge List, Graph Conversions

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 list of edges represent?
    • A: Each pair [a, b] indicates a bidirectional flight between cities a and b.
  • Q: What is the goal of this problem?
    • A: Convert the list of edges into an adjacency dictionary where each key represents a city, and the value is a list of cities connected to that key city by direct flights.
  • Q: Can cities have multiple connections?
    • A: Yes, cities can have multiple bidirectional flights to different cities.
HAPPY CASE
Input: flights = ['Cape Town', 'Addis Ababa'], ['Cairo', 'Lagos'], ['Lagos', 'Addis Ababa'], ['Nairobi', 'Cairo'], ['Cairo', 'Cape Town'](/codepath/compsci_guides/wiki/'Cape-Town',-'Addis-Ababa'],-['Cairo',-'Lagos'],-['Lagos',-'Addis-Ababa'],-['Nairobi',-'Cairo'],-['Cairo',-'Cape-Town')
Output: {
            'Cape Town': ['Addis Ababa', 'Cairo'],
            'Addis Ababa': ['Cape Town', 'Lagos'],
            'Lagos': ['Cairo', 'Addis Ababa'],
            'Cairo': ['Cape Town', 'Nairobi'],
            'Nairobi': ['Cairo']
        }
Explanation: The list of flights is converted into an adjacency dictionary, representing the bidirectional connections.

EDGE CASE
Input: flights = []
Output: {}
Explanation: There are no flights, so the output is an empty dictionary.

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:

  • Edge List to Adjacency List Conversion: This problem is about converting a list of edges (flights) into an adjacency dictionary where each city is connected to other cities by direct flights.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to iterate through the list of edges and build the adjacency dictionary by adding connections for both cities a and b since the flight is bidirectional.

1) Create an empty dictionary `adj_dict`.
2) Iterate through the `flights` list. For each flight `(a, b)`:
    a) Add `b` to `adj_dict[a]` if `a` is already in the dictionary, otherwise create a new entry for `a` and add `b`.
    b) Add `a` to `adj_dict[b]` if `b` is already in the dictionary, otherwise create a new entry for `b` and add `a`.
3) Return the completed adjacency dictionary.

⚠️ Common Mistakes

  • Forgetting to add bidirectional connections (i.e., adding the flight in both directions).
  • Failing to handle an empty list of flights correctly.

4: I-mplement

Implement the code to solve the algorithm.

def get_adj_dict(flights):
    adj_dict = {}
    
    # Iterate through each flight (edge)
    for a, b in flights:
        # Add bidirectional flight from a to b
        if a not in adj_dict:
            adj_dict[a] = []
        adj_dict[a].append(b)
        
        # Add bidirectional flight from b to a
        if b not in adj_dict:
            adj_dict[b] = []
        adj_dict[b].append(a)
    
    return adj_dict

5: R-eview

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

  • Input: flights = ['Cape Town', 'Addis Ababa'], ['Cairo', 'Lagos'], ['Lagos', 'Addis Ababa'], ['Nairobi', 'Cairo'], ['Cairo', 'Cape Town'](/codepath/compsci_guides/wiki/'Cape-Town',-'Addis-Ababa'],-['Cairo',-'Lagos'],-['Lagos',-'Addis-Ababa'],-['Nairobi',-'Cairo'],-['Cairo',-'Cape-Town')

  • Expected Output:

    {
    'Cape Town': ['Addis Ababa', 'Cairo'],
    'Addis Ababa': ['Cape Town', 'Lagos'],
    'Lagos': ['Cairo', 'Addis Ababa'],
    'Cairo': ['Cape Town', 'Nairobi'],
    'Nairobi': ['Cairo']
}

  • Input: flights = []

  • Expected Output: {}

6: E-valuate

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

  • Time Complexity: O(E), where E is the number of edges (flights). We iterate through the list of flights once.
  • Space Complexity: O(V + E), where V is the number of vertices (cities) and E is the number of edges. We store the adjacency dictionary which holds all cities and their connections.