Problem1 -> 

Quality Assurance Bug Sorting Solution

Topics Involved / Prerequisites

• Hash Maps (Frequency Counting)
• Custom Sorting (Comparators)

Overview

To sort the bugs according to the QA team's specific rules, we need to know exactly how many times each bug appears before we rearrange them. By first counting the frequencies of all bug codes, we can then pass a custom sorting rule to our algorithm: sort primarily by frequency in ascending order, and break any ties by sorting the bug codes themselves in ascending order.

Approach

1. Counting Frequencies

We traverse the array once and use a Hash Map (unordered_map in C++) to keep a running tally of how many times each bug code appears in the logs.

2. Custom Sorting Logic

We use the standard sorting function but provide it with a custom lambda function (comparator). When the sorting algorithm compares two bug codes, a and b, our custom rule dictates:

• If freq[a] is not equal to freq[b], place the one with the smaller frequency first.
• If freq[a] equals freq[b], place the one with the smaller code value first.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> sortBugs(vector<int>& bugs) {
    unordered_map<int, int> freq;
    
    // Step 1: Count the frequency of each bug code
    for (int bug : bugs) {
        freq[bug]++;
    }
    
    // Step 2: Sort using a custom lambda comparator
    sort(bugs.begin(), bugs.end(), [&](int a, int b) {
        if (freq[a] != freq[b]) {
            return freq[a] < freq[b]; // Less frequent first
        }
        return a < b; // Lower code number first on tie
    });
    
    return bugs;
}

int main() {
    vector<int> bugs = {8, 4, 6, 5, 4, 8};
    vector<int> sortedBugs = sortBugs(bugs);
    
    cout << "Sorted Bugs: ";
    for (int bug : sortedBugs) {
        cout << bug << " "; 
    }
    // Output: 5 6 4 4 8 8
    cout << "\n";
    
    return 0;
}

Time Complexity

• Time: O(N log N) - Counting the frequencies takes linear time, but sorting the array dictates the overall time complexity.
• Space: O(N) - To store the frequencies in the hash map.

Problem2 

Package Sorting Optimization Solution

Topics Involved / Prerequisites

• String Traversal

• Greatest Common Divisor (GCD) Math

Overview

This problem initially sounds like a complex string-partitioning challenge, but there is a brilliant mathematical catch! If you want to divide a collection of characters into K parts such that every part has the exact same character counts, then the total frequency of every character must be perfectly divisible by K. Therefore, the maximum number of parts K is simply the Greatest Common Divisor (GCD) of all the current character frequencies.

Approach

1. Tracking Frequencies on the Fly

Instead of processing each prefix from scratch (which would be too slow), we iterate through the string character by character. We maintain an array of size 26 to continuously track the frequencies of the uppercase letters as our prefix grows.

2. Calculating the GCD

For every new character we add to our prefix, we want to find the maximum possible divisions. We do this by calculating the GCD of all the non-zero frequencies currently in our tracking array. We append this GCD to our results array and move to the next character.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Helper function to calculate GCD of two numbers
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

vector<int> maxEqualParts(string packages) {
    int n = packages.length();
    vector<int> result;
    vector<int> freq(26, 0);
    
    for (int i = 0; i < n; i++) {
        // Update the frequency of the current character
        freq[packages[i] - 'A']++;
        
        int current_gcd = 0;
        
        // Find the GCD of all non-zero frequencies
        for (int count : freq) {
            if (count > 0) {
                current_gcd = gcd(current_gcd, count);
            }
        }
        
        result.push_back(current_gcd);
    }
    
    return result;
}

int main() {
    string packages = "ABAB";
    vector<int> ans = maxEqualParts(packages);
    
    cout << "Maximum parts per prefix: ";
    for (int parts : ans) {
        cout << parts << " ";
    }
    // Output: 1 1 1 2
    cout << "\n";
    
    return 0;
}