Find Center of Airport - codepath/compsci_guides GitHub Wiki

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

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

Problem Highlights

💡 Difficulty: Easy
⏰ Time to complete: 10-15 mins
🛠️ Topics: Graphs, Star Graphs, Degree of Nodes

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 is a star graph?
- A: A star graph has one center node connected to all other nodes, and all other nodes are connected only to the center.
Q: How can we find the center of a star graph?
- A: The center of the star graph is the node that appears in all edges (or has the highest degree).
Q: Can there be more than one center?
- A: No, a star graph has only one center node.

HAPPY CASE
Input: terminals = [1,2],[2,3],[4,2](/codepath/compsci_guides/wiki/1,2],[2,3],[4,2)
Output: 2
Explanation: Terminal 2 is connected to all other terminals, so it is the center.

EDGE CASE
Input: terminals = [1,2],[3,1],[4,1],[5,1](/codepath/compsci_guides/wiki/1,2],[3,1],[4,1],[5,1)
Output: 1
Explanation: Terminal 1 is the center because it is connected to all other terminals.

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

Node Degree: In a star graph, the center node will have a degree of n-1 (connected to all other nodes), while all other nodes will have a degree of 1.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: The center node in a star graph appears in every edge. We can iterate over the list of edges, count how often each node appears, and return the node with the highest count.

1) Create an empty dictionary `count` to store the frequency of each terminal.
2) Iterate through the list `terminals`, and for each edge `[u, v]`, increment the count of both `u` and `v`.
3) The center terminal will have a count of `n-1` (because it is connected to all other terminals).
4) Return the terminal that appears in more than 1 edge.

⚠️ Common Mistakes

Misinterpreting the center node as any node with multiple connections, rather than the node connected to all others.
Not handling the input correctly when n is small (e.g., 2 terminals).

4: I-mplement

Implement the code to solve the algorithm.

def find_center(terminals):
    # Create a dictionary to count occurrences of each terminal
    count = {}
    
    for u, v in terminals:
        count[u] = count.get(u, 0) + 1
        count[v] = count.get(v, 0) + 1
    
    # The center node is the one with the highest count (appears n-1 times)
    for terminal, c in count.items():
        if c > 1:  # Appears in more than 1 edge, must be the center
            return terminal

5: R-eview

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

Input: terminals = [1,2],[2,3],[4,2](/codepath/compsci_guides/wiki/1,2],[2,3],[4,2)
Output: 2
Explanation: Terminal 2 is connected to all other terminals (1, 3, and 4), so it is the center.
Input: terminals = [1,2],[5,1],[1,3],[1,4](/codepath/compsci_guides/wiki/1,2],[5,1],[1,3],[1,4)
Output: 1
Explanation: Terminal 1 is connected to all other terminals (2, 3, 4, and 5).

6: E-valuate

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

Time Complexity: O(n), where n is the number of edges (terminals). We iterate through all edges once.
Space Complexity: O(n), where n is the number of terminals. We store the count of each terminal in a dictionary.