Find normalized list difference efficiently
Company: Palo Alto Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Quick Answer: This question evaluates competency in computing normalized list differences, including string normalization, collection comparison, duplicate handling, and time and space complexity reasoning.
Constraints
- 0 <= len(list1), len(list2) <= 100000
- 0 <= len(s) <= 1000 for every string s in list1 and list2
- Normalization is exactly: s.strip().lower()
Examples
Input: ([' Apple ', 'banana', 'BANANA', 'Cherry'], ['apple', ' Durian '])
Expected Output: ['banana', 'cherry']
Explanation: After normalization, list1 becomes ['apple', 'banana', 'banana', 'cherry'] and list2 becomes {'apple', 'durian'}. The values in list1 but not list2 are 'banana' and 'cherry', with duplicates removed.
Input: ([' one', 'Two', ' two ', 'THREE', 'three ', 'Four'], ['TWO'])
Expected Output: ['one', 'three', 'four']
Explanation: The normalized value 'two' is excluded because it appears in list2. 'three' appears twice in list1 after normalization but is included only once.
Hints
- Normalize all strings in list2 first and store them in a hash set for fast membership checks.
- Use another set to track which normalized strings from list1 have already been added to the result so you can avoid duplicates while preserving order.