Google·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE coding round, got a list manipulation problem that looked deceptively simple but had some tricky edge cases around impossibility conditions. Not much else to say about the context, no outcome info shared.

Questions Asked (1)

Given two integer arrays and a value k, delete the minimum number of elements from the second array (preserving order) so that the first k elements of each array share no common values. Return -1 if it's impossible.

Algorithms & Data Structures

Author's notes

My first instinct was greedy: collect the values in list1's first k elements into a set, then scan list2 and count how many elements you need to skip before you've accumulated k non-conflicting ones.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: we need to delete elements from the second array so that the first k elements of both arrays have no common values. Then, identify the elements in the first k of the first array and the first k of the second array, and determine which elements in the second array's prefix must be removed. Finally, compute the minimum deletions by finding the longest subsequence of the second array's prefix that avoids all values present in the first array's prefix, and subtract its length from k; if no such subsequence exists, return -1.

Pro tip: Discuss edge cases like k larger than either array length, or when the first array's prefix contains all possible values, making it impossible. Also, mention that preserving order means we can only delete elements, not rearrange, so the problem reduces to finding a subsequence with certain constraints.

1. Clarify the problem and constraints

Restate the problem in your own words and ask clarifying questions about k, array sizes, and what 'first k elements' means if arrays are shorter than k. Confirm that deletion preserves order and that we want to minimize deletions.

2. Identify the forbidden set

Extract the first k elements of the first array and collect all distinct values into a set. These values cannot appear in the first k elements of the second array after deletions.

3. Find the longest valid subsequence

Scan the first k elements of the second array and find the longest subsequence that contains no values from the forbidden set. This is equivalent to counting elements not in the forbidden set, since we can keep all such elements while preserving order.

4. Compute minimum deletions

If the longest valid subsequence has length L, then the minimum deletions needed is k - L. If L < k, it's impossible to have k elements without common values, so return -1.

5. Handle edge cases and return result

Check if k is larger than either array length; if so, return -1. Also, if the first array's prefix contains all values that appear in the second array's prefix, return -1. Otherwise, return the computed minimum deletions.

Key Points to Mention

Use a hash set to efficiently check for common values.
The problem reduces to finding the longest subsequence of the second array's prefix that avoids a given set of values.
Preserving order means we can only delete elements, not rearrange, so the solution is to keep all elements not in the forbidden set.
Time complexity is O(k) for scanning and O(k) space for the set, which is optimal.
Edge cases: k=0 (no deletions needed), k > array length, or when the first array's prefix contains all values from the second array's prefix.
Return -1 if it's impossible to achieve k elements without common values.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.