Pinterest·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Pinterest MLE interview with a string manipulation problem that looked straightforward but had enough edge cases to trip you up if you weren't careful about complexity.

Questions Asked (1)

Given two strings a and b, find the minimum number of copies of a you need to construct b. You can append a full copy of a to a buffer or delete any single character from the buffer. The final buffer must equal b exactly. Discuss time and space complexity and handle edge cases like b being empty or a not being a supersequence of b.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The deletion cost is what makes this non-trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the minimum number of copies of string a such that b is a subsequence of the concatenated copies, then account for deletions. Use dynamic programming or greedy matching to compute the minimum copies, and discuss time/space complexity and edge cases.

Pro tip: Clarify that deletions are free and only copies count, so the problem reduces to finding the smallest k where b is a subsequence of a repeated k times. This simplifies the solution and shows you understand the core constraint.

1. Understand the problem and constraints

Restate the problem: we can append full copies of a and delete any characters; we need the minimum number of copies to obtain b. Note that deletions are unlimited and free, so the challenge is to match b as a subsequence of repeated a.

2. Check edge cases and feasibility

Handle b empty (answer 0), a empty (impossible unless b empty), and check if every character in b appears in a; if not, return -1. Also consider if b is already a subsequence of a (answer 1).

3. Design algorithm to compute minimum copies

Use a greedy two-pointer approach: iterate through b, and for each character, find its next occurrence in a (wrapping around and incrementing copy count when needed). Alternatively, use DP to compute the minimum copies, but greedy is optimal here.

4. Analyze time and space complexity

The greedy approach runs in O(|b| * log |a|) with preprocessed positions, or O(|b| * |a|) naive; space O(|a|) for positions. Discuss trade-offs and potential optimizations.

5. Test with examples and discuss trade-offs

Walk through examples like a='abc', b='abcabc' (2 copies), a='abc', b='ac' (1 copy), and a='abc', b='abd' (impossible). Mention that the greedy approach is optimal and compare with DP if needed.

Key Points to Mention

The problem reduces to finding the minimum k such that b is a subsequence of a repeated k times.
Deletions are free and unlimited, so we only need to match characters in order.
Greedy two-pointer with precomputed next occurrence is optimal and efficient.
Time complexity: O(|b| * log |a|) with binary search on positions, or O(|b| * |a|) naive; space O(|a|).
Edge cases: empty b (0 copies), empty a (impossible unless b empty), characters in b not in a (return -1).
The greedy approach is optimal because each copy can contribute at most one full pass through a, and we minimize copies by taking the earliest possible matches.

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