Common Signals Between Space Probes - 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 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]