1378. Replace Employee ID With The Unique Identifier
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 90.3%
Problem Breakdown
The problem requires us to replace employee IDs in a given table with unique identifiers. The inputs are two tables: Employees and EmployeeUniqueness. The Employees table contains columns for employee_id, name, and other attributes, while the EmployeeUniqueness table contains columns for employee_id and unique_identifier. The output should be a modified Employees table where each employee_id is replaced with its corresponding unique_identifier.
Inputs:
Employeestable:employee_idname- Other attributes
EmployeeUniquenesstable:employee_idunique_identifier
Outputs:
- Modified
Employeestable withemployee_idreplaced byunique_identifier.
Implicit Constraints/Edge Cases:
- Empty Input: If either of the tables is empty, the output should be an empty table.
- Duplicates: There might be duplicate
employee_ids in theEmployeestable, but eachemployee_idshould map to a uniqueunique_identifier. - Missing IDs: Some
employee_ids in theEmployeestable might not have a corresponding entry in theEmployeeUniquenesstable.
Intuition
The brute-force approach would involve iterating through each row of the Employees table, searching for the corresponding unique_identifier in the EmployeeUniqueness table, and replacing it. This approach is inefficient with a time complexity of O(n * m), where n is the number of rows in the Employees table and m is the number of rows in the EmployeeUniqueness table.
A better approach involves using a hash map (dictionary) to store the mapping from employee_id to unique_identifier. This allows for constant-time lookups, reducing the time complexity to O(n + m).
Approach
- Create a Mapping: Iterate through the
EmployeeUniquenesstable and create a dictionary that maps eachemployee_idto its correspondingunique_identifier. - Replace IDs: Iterate through the
Employeestable and replace eachemployee_idwith its correspondingunique_identifierfrom the dictionary. - Handle Missing IDs: If an
employee_idin theEmployeestable does not exist in the dictionary, it can be left unchanged or handled as per specific requirements (e.g., setting to a default value).
Complexity Analysis
- Time Complexity: O(n + m), where n is the number of rows in the
Employeestable and m is the number of rows in theEmployeeUniquenesstable. This is because we iterate through both tables once. - Space Complexity: O(m) for storing the dictionary, where m is the number of unique employee IDs.
Solution
def replace_employee_id(employees, employee_uniqueness):
# Step 1: Create a mapping from employee_id to unique_identifier
id_map = {row['employee_id']: row['unique_identifier'] for row in employee_uniqueness}
# Step 2: Replace employee_id with unique_identifier in the Employees table
for emp in employees:
if emp['employee_id'] in id_map:
emp['employee_id'] = id_map[emp['employee_id']]
return employees
# Example usage:
employees = [
{'employee_id': 1, 'name': 'Alice'},
{'employee_id': 2, 'name': 'Bob'}
]
employee_uniqueness = [
{'employee_id': 1, 'unique_identifier': 'UID001'},
{'employee_id': 2, 'unique_identifier': 'UID002'}
]
modified_employees = replace_employee_id(employees, employee_uniqueness)
print(modified_employees)
Edge Cases Handled
- Empty Input: If either
employeesoremployee_uniquenessis empty, the function will return an empty list. - Duplicates: The dictionary ensures that each
employee_idmaps to a uniqueunique_identifier. - Missing IDs: Any
employee_idinemployeesthat does not have a corresponding entry inid_mapremains unchanged.