Common Signals Between Space Probes

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 sets, check out the Common-Signals-Between-Space-Probes-II solution guide.

General Idea: Use dictionaries to store the frequency of each element in both arrays and then count the occurrences of elements from one array in the other.

1. Initialize two empty dictionaries `freq_signals1` and `freq_signals2` to store the frequency of elements in `signals1` and `signals2`.
2. Populate `freq_signals2` with the frequency of each element in `signals2`.
3. Populate `freq_signals1` with the frequency of each element in `signals1`.
4. Calculate `answer1` by counting the elements in `signals1` that exist in `freq_signals2`.
5. Calculate `answer2` by counting the elements in `signals2` that exist in `freq_signals1`.
6. Return the list `[answer1, answer2]`.

I-mplement

def find_common_signals(signals1, signals2):
    # Create frequency dictionaries for both signals1 and signals2
    freq_signals1 = {}
    freq_signals2 = {}

    # Populate frequency dictionary for signals2
    for signal in signals2:
        if signal in freq_signals2:
            freq_signals2[signal] += 1
        else:
            freq_signals2[signal] = 1

    # Populate frequency dictionary for signals1
    for signal in signals1:
        if signal in freq_signals1:
            freq_signals1[signal] += 1
        else:
            freq_signals1[signal] = 1

    # Calculate answer1: the number of indices i such that signals1[i] exists in signals2
    answer1 = 0
    for signal in signals1:
        if signal in freq_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 freq_signals1:
            answer2 += 1

    return [answer1, answer2]