Quick Overview

This question evaluates competency in computing normalized list differences, including string normalization, collection comparison, duplicate handling, and time and space complexity reasoning.

Find normalized list difference efficiently

Company: Palo Alto Networks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given two lists of strings, list1 and list2, return all elements that appear in list1 but not in list2 after applying a consistent normalization step (e.g., lowercase and trimming). Describe and implement an efficient algorithm, including the data structures you would use, handling of duplicates, and the time and space complexities.

Overview: This question evaluates competency in computing normalized list differences, including string normalization, collection comparison, duplicate handling, and time and space complexity reasoning.

Read the full Palo Alto Networks Software Engineer interview experience this question came from

You are given two lists of strings, list1 and list2. Normalize every string by removing leading and trailing whitespace and converting it to lowercase. Return all normalized strings that appear in list1 but not in list2. Rules for duplicates: - If the same normalized string appears multiple times in list1, include it only once in the output. - Preserve the order of first appearance from list1. - Duplicates in list2 do not matter. For example, " Apple ", "apple", and "APPLE" all normalize to "apple".

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

  1. Normalize all strings in list2 first and store them in a hash set for fast membership checks.
  2. 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.

Loading coding console...