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)
Solution
from typing import List
def remove_k_prefix_overlap(listA: List[int], listB: List[int], k: int) -> List[int]:
# If k is zero, the constraint is vacuously satisfied; return listB unchanged.
if k <= 0:
return listB.copy()
forbidden = set(listA[:k])
result: List[int] = []
safe = 0
for x in listB:
if safe < k:
if x not in forbidden:
result.append(x)
safe += 1
# else: delete (skip) this element
else:
# Already have k safe elements at the front; keep the rest unchanged
result.append(x)
# If we couldn't gather k safe elements, it's impossible; return empty list
if safe < k:
return []
return result
Explanation
Create a hash set of the first k values from listA to act as the forbidden set. Scan listB left-to-right: keep elements not in the forbidden set until you have collected k such elements; skip any forbidden elements encountered before that. After collecting k safe elements, simply append all remaining elements because they cannot change the first k of the output. If there are fewer than k safe elements in listB, return an empty list since no valid configuration exists.
Time complexity: O(len(listA) + len(listB)). Space complexity: 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.