Domain 2MediumMEDIUM

Project Employees III

Aggregates employee salaries by project ID using a hash map for O(N) efficiency, handles nulls safely, and sorts results descending.

Domain: medium•Updated: 2026-09-08
#aggregation#hashmap#O(N)#sorting

Problem Breakdown

Restatement: The problem involves analyzing salary data associated with projects. Although the schema is defined in SQL terms (Employees, Projects), this solution implements an algorithmic simulation using Python to perform aggregation tasks typically solved via SQL’s GROUP BY. The goal is to calculate metrics like total salary per project and filter based on thresholds (e.g., minimum total salary).

Inputs:

  • A list of dictionaries representing joined employee-project records.
  • Keys expected: employee_id, project_id (or similar unique identifier), salary.
  • Threshold parameter (min_total_salary).

Outputs: A sorted list of aggregated project statistics containing the project ID, total salary sum, and count of employees/projects contributing to that sum.

Implicit Constraints & Edge Cases:

  1. Empty Input: Must return an empty list if no data exists.
  2. Null Salaries: Salary fields might be None or missing; these must not crash the summation logic (treated as 0).
  3. Key Ambiguity: The original code attempted to fallback from project_id to a generic id. This is risky if an employee ID and project ID share the same column name conventionally, potentially aggregating by Employee instead of Project. We assume distinct keys per schema definition.
  4. Sorting Requirement: SQL problems often require results sorted descending; this adds O(Klog⁡K)O(K \log K) complexity to the post-processing step.

Intuition

Naive Approach: Iterate through every record and for each project, maintain a list of salaries. Summing at the end would be inefficient (O(N2)O(N^2) or worse depending on implementation). Nested loops are strictly avoided in optimal solutions.

Key Insight: Use Hash Maps (Dictionaries) to group data by project_id. This allows O(1)O(1) amortized updates during a single pass through the dataset, mirroring SQL’s internal hash-based aggregation engine. Filtering and sorting happen after aggregation (KK is number of unique projects).

Optimal Approach:

  • Aggregation Phase: Single loop over input data to populate sums/counts in dictionary.
  • Filtering Phase: Iterate through aggregated values, keeping only those meeting the threshold.
  • Sorting Phase: Sort final list by total salary descending (common requirement for ranking).

Approach

  1. Initialize Aggregation Map: Use defaultdict to store {total_salary: float, count: int} keyed by project ID. This handles missing keys automatically without raising errors during the loop.
  2. Single Pass Processing: Iterate through each record in employee_data. Extract salary and key (project_id). Update map values only if salary is valid numeric type to avoid TypeErrors with non-numeric data or nulls.
  3. Filtering & Formatting: Construct a result list from the aggregated dictionary, applying the minimum total salary threshold check. Round floating point numbers for consistency.
  4. Sorting: Sort the final results by total_salary in descending order to match typical SQL output expectations (ORDER BY).

Complexity Analysis

  • Time Complexity: O(N+Klog⁡K)O(N + K \log K), where NN is the number of employee records and KK is the number of unique projects.
    • Aggregation loop: O(N)O(N).
    • Filtering/Formatting loop: O(K)O(K).
    • Sorting results: O(Klog⁡K)O(K \log K).
    • Since K≤NK \le N, worst case is dominated by sorting if output size approaches input size. The original claim of strictly O(N)O(N) was slightly optimistic regarding the sort step, though often acceptable in interview contexts where linear scan dominates logic cost.
  • Space Complexity: O(K)O(K). We store one entry per unique project ID plus a small constant overhead for result list construction.

Solution

from collections import defaultdict
import typing as t

def project_employees(
    employee_data: list[t.Dict[str, int]], 
    min_total_salary: float = 0.0
) -> t.List[dict]:
    """
    Aggregates employee salaries by project ID and filters based on total salary threshold.
    
    Args:
        employee_data: List of dicts with 'employee_id', 'project_id', 'salary'.
                       Assumes a pre-joined structure or flat list containing necessary keys.
        min_total_salary: Threshold to filter projects/employees (default 0).

    Returns:
        A sorted list of aggregated dictionaries for qualifying groups, descending by salary.
    """
    
    # Handle empty input gracefully
    if not employee_data:
        return []
        
    # Dictionary to store aggregates per project
    # Key: Project ID, Value: {'total_salary': float, 'employee_count': int}
    aggregation_map = defaultdict(lambda: {
        "total_salary": 0.0, 
        "count": 0
    })

    for record in employee_data:
        # Safely extract project_id; assume schema guarantees this key exists per problem constraints
        # If 'project_id' is missing or None, skip to prevent aggregation errors on wrong keys
        project_id = record.get("project_id")
        
        if not project_id: 
            continue
            
        salary = record.get("salary", 0)
        
        # Ensure salary is numeric before adding; handles explicit nulls safely
        if isinstance(salary, (int, float)) and not str(salary).strip() == "":
             aggregation_map[project_id]["total_salary"] += salary
            aggregation_map[project_id]["count"] += 1

    # Filter based on criteria and format output
    result = []
    
    for project_id, stats in aggregation_map.items():
        if stats["total_salary"] >= min_total_salary:
            result.append({
                "project_id": project_id,
                "total_salary": round(stats["total_salary"], 2), # Standardize precision to avoid float errors
                "employee_count": stats["count"]
            })

    return sorted(result, key=lambda x: x['total_salary'], reverse=True)