Equivalent Species Pairs - 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 determine the number of equivalent species pairs in a list of observed species pairs.
• Q:
  • What input is provided?
    • A list of lists species_pairs where each sublist contains two species.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Normalize each species pair by sorting it, then count the occurrences of each normalized pair. Use this to calculate the number of equivalent pairs.

1) Initialize a dictionary `count` to store occurrences of each normalized species pair.
2) Normalize each pair by sorting it, then update the count.
3) Calculate the number of equivalent pairs using the formula `c * (c - 1) // 2` for each pair count `c`.
4) Return the total number of equivalent pairs.

Hint: For a species pair that appears n times, the number of equivalent pairs that can be formed is given by the formula the formula : c * (c - 1) // 2

⚠️ Common Mistakes

• Not correctly normalizing the species pairs before counting.

I-mplement

def num_equiv_species_pairs(species_pairs):
    # Dictionary to count occurrences of each normalized species pair
    count = {}

    # Normalize each species pair and count its occurrences
    for pair in species_pairs:
        normalized = tuple(sorted(pair))
        if normalized in count:
            count[normalized] += 1
        else:
            count[normalized] = 1

    # Calculate the number of equivalent pairs
    pairs = 0
    for c in count.values():
        if c > 1:
            pairs += c * (c - 1) // 2

    return pairs