Sponsored
Sponsored
This approach involves grouping employees by their department and filtering their salaries to get the top three unique salaries for each department. By using structures such as dictionaries in our programming languages, we can mimic SQL-like GROUP BY and LIMIT operations. This involves two major steps: Grouping employees by department and then filtering by top salaries.
Time Complexity: O(n log n), dominated by the sorting step where n is the number of employees. Space Complexity: O(n), to store grouped employees and unique salaries.
1from collections import defaultdict
2
3# Sample data
4employees = [
5 {'id': 1, 'name': 'Joe', 'salary': 85000, 'departmentId': 1},
6 {'id': 2, 'name': 'Henry', 'salary': 80000, 'departmentId': 2},
7 {'id': 3, 'name': 'Sam', 'salary': 60000, 'departmentId': 2},
8 {'id': 4, 'name': 'Max', 'salary': 90000, 'departmentId': 1},
9 {'id': 5, 'name': 'Janet', 'salary': 69000, 'departmentId': 1},
10 {'id': 6, 'name': 'Randy', 'salary': 85000, 'departmentId': 1},
11 {'id': 7, 'name': 'Will', 'salary': 70000, 'departmentId': 1}
12]
13departments = [
14 {'id': 1, 'name': 'IT'},
15 {'id': 2, 'name': 'Sales'}
16]
17
18# Group by department
19dept_employees = defaultdict(list)
20for emp in employees:
21 dept_employees[emp['departmentId']].append(emp)
22
23# Result
24result = []
25
26# Fetch top three salaries per department
27for dept in departments:
28 dept_id = dept['id']
29 dept_name = dept['name']
30 salaries = sorted(list(set(emp['salary'] for emp in dept_employees[dept_id])), reverse=True)[:3]
31
32 # Add high earners
33 for emp in dept_employees[dept_id]:
34 if emp['salary'] in salaries:
35 result.append({'Department': dept_name, 'Employee': emp['name'], 'Salary': emp['salary']})
36
37# Print result
38for r in result:
39 print(r)This solution utilizes Python dictionaries to group employees by department and process their salaries. We maintain a list of top unique salaries per department using a sorted list of unique salaries and filter employees to obtain only those with salaries in this list.
This approach involves using a more sophisticated data structure to keep track of top salaries and employees proactively while grouping the employees by department. In certain languages, this can be achieved efficiently using priority queues or heaps. However, this example shows a simpler method utilizing sorted structures.
Time Complexity: O(n log n), caused by the sort operation on each department's employee list. Space Complexity: O(n), due to storage needs for set and list of employees per department.
1import java.util.*;
2
3public class TopSalaries
This Java solution groups employees by departments and sorts the list by salary to filter the top three unique salaries. The use of lists and sets helps us manage unique top salaries and efficiently output all qualifying employees.