How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Min deletions to avoid overlap in first k

Q: Min deletions to avoid overlap in first k

This question evaluates array and sequence manipulation skills, set-based reasoning about value overlap, and the ability to compute minimal edits while preserving relative order constraints.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given two integer arrays `list1` and `list2` and an integer `k`. You may **delete elements from `list2`** (deletions can be at any positions). The **relative order of the remaining elements of `list2` must stay the same**. After deletions, `list2` must still contain **at least `k` elements**. Let: - `A` be the **first `k` elements** of `list1` (i.e., `list1[0..k-1]`). - `B` be the **first `k` elements** of the modified `list2`. Requirement: **No value may appear in both `A` and `B`** (i.e., the sets of values used in the first `k` positions must be disjoint). Return the **minimum number of deletions** needed in `list2` to satisfy the requirement. If it is impossible (i.e., you cannot obtain `k` valid elements for `B`), return `-1`. **Clarifications** - Duplicates may exist in either array. - The constraint is about value overlap between `A` and `B`; duplicates inside `B` itself are allowed unless they also appear in `A`. **Example** - `list1 = [5,1,2,9]`, `list2 = [1,3,5,4,3]`, `k = 3` - `A = {5,1,2}`. - Delete `1` and `5` from `list2`, remaining `[3,4,3]` → `B = [3,4,3]` has no overlap with `A`. - Answer: `2` deletions. **Constraints (reasonable interview scale)** - `1 <= k <= min(len(list1), len(list2))` - `len(list1), len(list2) <= 2 * 10^5`

Quick Answer: This question evaluates array and sequence manipulation skills, set-based reasoning about value overlap, and the ability to compute minimal edits while preserving relative order constraints.

You are given two integer arrays `list1` and `list2` and an integer `k`. You may delete any elements from `list2`, but the relative order of the remaining elements must stay the same. After deletions, `list2` must still contain at least `k` elements. Let `forbidden` be the set of values appearing in the first `k` elements of `list1`. Your goal is to make sure that every one of the first `k` elements of the modified `list2` is not in `forbidden`. Return the minimum number of deletions needed. If it is impossible to obtain `k` valid elements for the front of `list2`, return `-1`.

Constraints

1 <= k <= min(len(list1), len(list2))
len(list1), len(list2) <= 2 * 10^5
Array values may be negative and may contain duplicates

Examples

Input: ([1, 2, 3], [2, 1, 4, 5], 2)

Expected Output: 2

Explanation: The forbidden set is {1, 2}. In `list2`, the first two values must be deleted, then 4 and 5 become the first two remaining elements.

Input: ([1, 2, 3, 4], [2, 5, 3, 6], 2)

Expected Output: 1

Explanation: The forbidden set is {1, 2}. Delete 2, then 5 and 3 become the first two elements, and both are allowed.

Input: ([4, 5, 6], [7, 4, 8, 5], 2)

Expected Output: 1

Explanation: The forbidden set is {4, 5}. Keep 7, delete 4, keep 8. Now the first two remaining elements are 7 and 8. The last 5 may stay because it is after the first k elements.

Input: ([1, 2], [1, 2, 1], 2)

Expected Output: -1

Explanation: The forbidden set is {1, 2}. There are no valid elements available, so it is impossible to obtain 2 valid front elements.

Input: ([7, 7, 8], [7, 9, 7, 10, 11], 3)

Expected Output: 2

Explanation: The forbidden set is {7, 8}. Delete the two 7s before collecting 9, 10, and 11 as the first three remaining elements.

Input: ([1, 2, 3], [1], 0)

Expected Output: 0

Explanation: If k = 0, there is no requirement on the front of `list2`, so no deletions are needed.

Input: ([-1, 2], [-1, -2, 2, -3], 2)

Expected Output: 2

Explanation: The forbidden set is {-1, 2}. Delete -1 and 2, then -2 and -3 become the first two remaining elements.

Hints

Only the part of `list2` before the k-th kept valid element can affect the answer. Once you have k valid front elements, everything after that can stay.
Build a set from `list1[:k]`, then scan `list2` from left to right. Count valid elements you can keep and forbidden elements that must be deleted before you reach k valid ones.

Quick Overview

This question evaluates array and sequence manipulation skills, set-based reasoning about value overlap, and the ability to compute minimal edits while preserving relative order constraints.