Time Portal Race Rankings - codepath/compsci_guides GitHub Wiki

U-nderstand

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

• Q: What is the desired outcome?

  • To find travelers who have never lost a race, and those who have lost exactly one race.

• Q: What input is provided?

  • A list of race outcomes races, where each element is a pair [winner, loser].

• Q: What constraints or nuances should be considered?

  • Only include travelers who appear in the races list (either as winner or loser).
  • Output two sorted lists:
    • One for those with no losses.
    • One for those with exactly one loss.
  • Ignore travelers who have never raced.

---

M-atch

Match the problem to a common pattern or data structure.

• This is a counting and classification problem:
  • Count how many times each traveler has lost.
  • Track all unique participants.
  • Classify travelers based on loss counts.

---

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Track how many races each traveler lost, and identify all travelers who participated. Then classify them into two categories.

1) Initialize an empty dictionary `loss_count` to store how many times each traveler has lost.
2) Initialize a set `participants` to track all travelers who appeared in races.
3) Iterate through `races`:
   - Add both winner and loser to `participants`.
   - Increment the loss count for the loser in `loss_count`.
4) Initialize two empty lists:
   - `no_losses`: travelers in `participants` not in `loss_count`
   - `one_loss`: travelers in `loss_count` with a count of 1
5) Sort both lists.
6) Return [no_losses, one_loss]

⚠️ Common Mistakes

• Forgetting to include all winners as participants (they may have no losses).
• Including travelers not mentioned in races.
• Miscounting losses (e.g., incrementing winner's losses by mistake).

---

I-mplement

def find_travelers(races):
    # Dictionary to count number of losses per traveler
    loss_count = {}
    # Set of all participants
    participants = set()
    
    for winner, loser in races:
        participants.add(winner)
        participants.add(loser)
        if loser in loss_count:
            loss_count[loser] += 1
        else:
            loss_count[loser] = 1
    
    # Lists for travelers with no losses and exactly one loss
    no_losses = []
    one_loss = []
    
    for traveler in participants:
        if traveler not in loss_count:
            no_losses.append(traveler)
        elif loss_count[traveler] == 1:
            one_loss.append(traveler)
    
    # Sort the results
    no_losses.sort()
    one_loss.sort()
    
    return [no_losses, one_loss]

---

R-eview

Review with sample input/output and verify against edge cases.

races1 = [1, 3], [2, 3], [3, 6], [5, 6], [5, 7], [4, 5], [4, 8], [4, 9], [10, 4], [10, 9](/codepath/compsci_guides/wiki/1,-3],-[2,-3],-[3,-6],-[5,-6],-[5,-7],-[4,-5],-[4,-8],-[4,-9],-[10,-4],-[10,-9)
races2 = [2, 3], [1, 3], [5, 4], [6, 4](/codepath/compsci_guides/wiki/2,-3],-[1,-3],-[5,-4],-[6,-4)

print(find_travelers(races1))  # Expected: [1, 2, 10], [4, 5, 7, 8](/codepath/compsci_guides/wiki/1,-2,-10],-[4,-5,-7,-8)
print(find_travelers(races2))  # Expected: [1, 2, 5, 6], [](/codepath/compsci_guides/wiki/1,-2,-5,-6],-[)

---

E-valuate

Evaluate time and space complexity.

• Time Complexity: O(N log N) due to sorting, where N is the number of unique travelers.
• Space Complexity: O(N) to store loss counts and participant set.