Quick Overview

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.

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.

Overview: 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

  1. Build a set of the first k elements of listA for O(1) membership checks.
  2. Greedily scan listB: keep elements not in the forbidden set until you have collected k safe elements; delete forbidden ones encountered before that.
  3. After you have k safe elements, keep all remaining elements since they do not affect the first k.
  4. If you cannot collect k safe elements from listB, return an empty list.
  5. 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.

Community answers

Answer by Luna

def delete_conflicts(listA, listB, k): forbidden = set(listA[:k]) result = [] for i, value in enumerate(listB): if len(result) < k: if value in forbidden: continue result.append(value) else: result.extend(listB[i:]) break return result if len(result) >= k else []

Loading coding console...

Show the approach

Approach

Goal. Delete the fewest elements from listB (keeping the order of survivors) so the new listB[:k] shares no value with listA[:k]. The key observation: the minimum-deletion result keeps the earliest k elements of listB that avoid the forbidden values, then keeps everything after them untouched.

Why that's optimal. Any valid answer needs k "safe" values (values not in listA[:k]) sitting at the front. Greedily taking the earliest such safe values minimizes how many unsafe elements we must skip — every unsafe element seen before we've collected k safe ones must be deleted, and none of them could ever be kept without violating the prefix constraint. Once k safe values are in place, no later element can affect the first k positions, so deleting any of them would only add unnecessary deletions; we keep them all.

Steps in the code.

  • Edge case: if k <= 0 the constraint is vacuous, so return a copy of listB.
  • Build forbidden = set(listA[:k]) for O(1) membership tests.
  • Scan listB once with a counter safe. While safe < k: append x and increment safe if x not in forbidden; otherwise skip (delete) it. Once safe == k, append every remaining element unconditionally.
  • If the scan ends with safe < k, there aren't enough safe values, so no valid configuration exists — return [].

The set gives constant-time forbidden checks, and the single linear pass produces exactly the minimum-deletion ordering. Test 3 illustrates the subtlety: k=1, listA[:1]={1}, listB=[3,1,2,4,5] → 3 is immediately safe, so the rest (including 1) is kept verbatim, yielding [3,1,2,4,5].

Time complexity:
O(len(listA) + len(listB))
Space complexity:
O(k)