Final Communication Hub - codepath/compsci_guides GitHub Wiki

Unit 2 Session 1 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the problem asking for?

  • A: The problem asks to find the final communication hub in an array paths where each element represents a direct communication path from one hub to another. The final hub is the one without any outgoing path to another hub.

• Q: What are the inputs?

  • A: An array paths where paths[i] = [hubA, hubB] represents a direct communication path from hubA to hubB.

• Q: What are the outputs?

  • A: The hub (a string or integer) that is the final communication hub, without any outgoing paths.

• Q: Are there any constraints on the values in the array?

  • A: It is guaranteed that the paths form a line without any loops, ensuring exactly one final communication hub.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use sets to track the hubs that have outgoing paths and all hubs. The final hub will be the one that is present in the set of all hubs but not in the set of hubs with outgoing paths.

1. Initialize two sets: `start_hubs` to keep track of hubs with outgoing paths, and `all_hubs` to keep track of all hubs.
2. Iterate through each path in `paths`.
   - Add the starting hub (`path[0]`) to `start_hubs`.
   - Add both the starting hub (`path[0]`) and the destination hub (`path[1]`) to `all_hubs`.
3. Iterate through each hub in `all_hubs`.
   - If a hub is not in `start_hubs`, it is the final communication hub.
4. Return the final communication hub.

I-mplement

def find_final_hub(paths):
    start_hubs = set()
    all_hubs = set()

    for path in paths:
        start_hubs.add(path[0])
        all_hubs.add(path[0])
        all_hubs.add(path[1])

    for hub in all_hubs:
        if hub not in start_hubs:
            return hub