Sort Signal Data - 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 sort an array of integers signals based on the frequency of the values in increasing order. If multiple values have the same frequency, they should be sorted in decreasing order of their values.

• Q: What are the inputs?

  • A: An array of integers signals.

• Q: What are the outputs?

  • A: A sorted array of integers based on the specified criteria.

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

  • A: The values are integers and may appear multiple times in the array.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

For this problem, we can begin by reading through the given code and translating the code into plain English to ensure we understand how the code is working.

General Idea: Use a dictionary to count the frequency of each value in the array and then sort the array using a custom sort key.

1. Count the frequency of each value in the array `signals`.
   - Initialize an empty dictionary `freq`.
   - Iterate through `signals` and update `freq` with the frequency of each value.

2. Sort the array `signals` using a custom sort key.
   - The primary key should be the frequency (in ascending order).
   - The secondary key (for ties) should be the value (in descending order).

3. Return the sorted array.

Once we understand the existing code, add function calls using happy and edge cases to find example input where the current code does not match the expected output.

Then, we can add print() statements and use the Stack Trace to debug.

I-mplement

def frequency_sort(signals):
    # Step 1: Count frequencies of each signal
    freq = {}
    for signal in signals:
        if signal in freq:
            freq[signal] += 1
        else:
            freq[signal] = 1 # Fixed Bug: This should initialize to 1, not 0

    # Step 2: Sort the signals based on frequency and value 
    sorted_signals = sorted(signals, key=lambda x: (freq[x], -x)) # Fixed Bug: This should sort x in decreasing order

    return sorted_signals