Common Signals Between Space Probes II - 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 calculate two values:
    • answer1: the number of indices i such that signals1[i] exists in signals2.
    • answer2: the number of indices j such that signals2[j] exists in signals1.

• Q: What are the inputs?

  • A: Two integer arrays signals1 and signals2 of sizes n and m, respectively.

• Q: What are the outputs?

  • A: A list [answer1, answer2] where:
    • answer1 is the count of elements in signals1 that exist in signals2.
    • answer2 is the count of elements in signals2 that exist in signals1.

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

  • A: The values are integers, and the arrays can be of different lengths.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

Note: Like many interview questions, this problem can be solved in many ways. If you chose to approach this using dictionaries, check out the Common Signals Between Space Probes solution guide.

General Idea: Use sets to find common elements between the two arrays and count occurrences.

1. Convert `signals1` and `signals2` to sets `set_signals1` and `set_signals2`.
2. Initialize `answer1` to 0 to count elements in `signals1` that are in `signals2`.
3. Initialize `answer2` to 0 to count elements in `signals2` that are in `signals1`.
4. Iterate through `signals1` and increment `answer1` for each element found in `set_signals2`.
5. Iterate through `signals2` and increment `answer2` for each element found in `set_signals1`.
6. Return the list `[answer1, answer2]`.

I-mplement

def find_common_signals(signals1, signals2):
    # Convert signals to a set
    set_signals1 = set(signals1)
    set_signals2 = set(signals2)

    # Calculate answer1: the number of indices i such that signals1[i] exists in signals2
    answer1 = 0
    for signal in signals1:
        if signal in set_signals2:
            answer1 += 1

    # Calculate answer2: the number of indices j such that signals2[j] exists in signals1
    answer2 = 0
    for signal in signals2:
        if signal in set_signals1:
            answer2 += 1

    return [answer1, answer2]