Replace Employee ID With The Unique Identifier — LeetCode #1378 (Easy)
Tags: Database
Related patterns: Hash Map, Array
Brute Force approach
Time complexity: O(n²). Space complexity: O(1).
The brute force approach involves checking each employee in the Employees table against every entry in the EmployeeUNI table to find a match. This is straightforward but inefficient, especially with larger datasets.
The time complexity is O(n²) because for each employee, we are potentially scanning through all unique IDs, leading to a nested loop scenario.
- Step 1: For each employee in the Employees table, initialize a variable to hold the unique_id as null.
- Step 2: Loop through each entry in the EmployeeUNI table to find a matching id.
- Step 3: If a match is found, update the unique_id variable; if no match is found after checking all entries, it remains null.
- Step 4: Store the result for each employee in a result list.
- Step 5: Return the result list.
1. Start with Alice (id 1), unique_id is null. Check EmployeeUNI, no match found. Result: (null, Alice)
2. Check Bob (id 7), unique_id is null. No match in EmployeeUNI. Result: (null, Bob)
3. Check Meir (id 11), unique_id is null. Match found (unique_id 2). Result: (2, Meir)
4. Check Winston (id 90), unique_id is null. Match found (unique_id 3). Result: (3, Winston)
5. Check Jonathan (id 3), unique_id is null. Match found (unique_id 1). Result: (1, Jonathan)
6. Final result: [(null, Alice), (null, Bob), (2, Meir), (3, Winston), (1, Jonathan)]
Optimal Solution approach
Time complexity: O(n). Space complexity: O(n).
The optimal solution uses a HashMap to store the unique IDs for quick lookups. This significantly reduces the time complexity by allowing us to find unique IDs in constant time.
The time complexity is O(n) because we are iterating through the EmployeeUNI table once to create the HashMap, and then we perform a single pass through the Employees table.
- Step 1: Create a HashMap to store the unique_id for each id from the EmployeeUNI table.
- Step 2: Populate the HashMap with entries from EmployeeUNI.
- Step 3: Select the name from Employees and look up the unique_id in the HashMap.
- Step 4: If the id is not found in the HashMap, return null for unique_id.
- Step 5: Return the results.
1. Create HashMap from EmployeeUNI: {3: 1, 11: 2, 90: 3}
2. Check Alice (id 1), not in HashMap. Result: (null, Alice)
3. Check Bob (id 7), not in HashMap. Result: (null, Bob)
4. Check Meir (id 11), found in HashMap. Result: (2, Meir)
5. Check Winston (id 90), found in HashMap. Result: (3, Winston)
6. Check Jonathan (id 3), found in HashMap. Result: (1, Jonathan)
7. Final result: [(null, Alice), (null, Bob), (2, Meir), (3, Winston), (1, Jonathan)]
Key Insights
- Using a HashMap allows for O(1) lookups, significantly speeding up the process.
- LEFT JOIN in SQL is a powerful tool for combining data from two tables based on a common key.
Common Mistakes
- Not handling cases where there are no matches properly, leading to incorrect outputs.
- Overlooking the use of JOINs which can simplify the solution.
Interview Tips
- Always consider the data structure that can optimize your lookups.
- Think about edge cases, such as employees without unique IDs.
- Practice writing SQL queries to become comfortable with JOIN operations.
