Remove elements to avoid k-prefix duplicates
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
Given two lists listA and listB and an integer k, delete elements from listB so that the first k elements of the new listB share no value with the first k elements of listA. Follow-up: design an O(n) time solution. Follow-up: extend to a list of lists, an integer k, and an integer d such that for each list its first k elements share no value with the first k elements of any of the previous d lists.
Quick Answer: This question evaluates algorithmic design and data-structure proficiency in the Coding & Algorithms domain, focusing on list and sequence manipulation with uniqueness constraints and attention to time complexity. It is commonly asked because it measures practical ability to implement efficient (e.g.
Given two integer lists listA and listB and an integer k (0 <= k <= len(listA)), delete elements from listB (while preserving the order of the remaining elements) so that the first k elements of the new listB share no value with the first k elements of listA. Among all such results, return the one with the minimum number of deletions (equivalently, keep the earliest k elements of listB that are not in listA[:k], and then keep all remaining elements). If listB contains fewer than k values not present in listA[:k], return an empty list.
Constraints
- 0 <= k <= len(listA) <= 2 * 10^5
- 0 <= len(listB) <= 2 * 10^5
- -10^9 <= values in listA, listB <= 10^9
- Time target: O(len(listA) + len(listB)); Space target: O(k)
Hints
- Build a set of the first k elements of listA for O(1) membership checks.
- Greedily scan listB: keep elements not in the forbidden set until you have collected k safe elements; delete forbidden ones encountered before that.
- After you have k safe elements, keep all remaining elements since they do not affect the first k.
- If you cannot collect k safe elements from listB, return an empty list.
- Follow-up: For a list of lists with window d, maintain a sliding union (via a frequency map) of the first k elements from the last d processed lists and apply the same greedy selection to each new list.