← Trexquant Interview Insights

Trexquant·Data Scientist·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Interviewed for a Data Scientist role at Trexquant and got a coding problem that felt more like a software engineering screen than anything data-related. The problem was algorithmic and the hint they gave basically told you the solution approach, which was a little odd.

Questions Asked (1)

Q1

Given two strings s and p where p is a subsequence of s, and an array of removable indices, find the maximum number of characters you can remove from s (in the given order) such that p remains a subsequence of the resulting string.

Algorithms & Data Structures
Author's notes

They gave away the approach in the hint, which was binary search on k.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the removals must be applied in the given order, so the problem reduces to finding the maximum prefix of the removable indices that can be removed while still allowing p to be a subsequence of the remaining characters. Use binary search on the number of removals, and for each candidate count, check if p is a subsequence of the string after removing the first k indices. This yields an O((n + m) log n) solution.

Pro tip: Clarify that the removals are applied sequentially, so removing the first k indices means those characters are gone; then binary search works because if p is a subsequence after k removals, it will also be a subsequence after fewer removals. Also, mention that you can optimize the check using a two-pointer scan or precomputed next-occurrence arrays.

1. Understand the problem and constraints

Restate the problem: given s, p (subsequence of s), and removable indices, find the maximum k such that after removing the first k indices from s, p is still a subsequence. Note that removals are in order, and indices are distinct.

2. Identify monotonicity and binary search

Observe that if p is a subsequence after removing k characters, it remains a subsequence after removing fewer than k characters. Thus, the property is monotonic, enabling binary search on k from 0 to len(removable).

3. Design the check function

For a given k, create a boolean array or set of removed indices (the first k from removable). Then check if p is a subsequence of the remaining characters in s using a two-pointer scan: iterate through s, skip removed indices, and match characters of p in order.

4. Analyze complexity and optimize

The check function takes O(n + m) time. Binary search adds a log factor, giving O((n + m) log n) overall. Mention that precomputing next occurrence arrays can reduce the check to O(m log n) but is not necessary.

5. Handle edge cases and conclude

Consider cases where p is empty, removable is empty, or p cannot be formed even without removals. Return the maximum k found. Discuss potential pitfalls like 0-indexed vs 1-indexed indices.

Key Points to Mention

  • Monotonicity of the property: if p is a subsequence after k removals, it is also after fewer removals.
  • Binary search on the number of removals to achieve O((n + m) log n) time.
  • Efficient subsequence check using two pointers, skipping removed indices.
  • Use of a boolean array or hash set to mark removed indices for O(1) lookup.
  • Edge cases: empty p, empty removable array, and indices out of bounds.
  • Alternative approach: dynamic programming or greedy without binary search, but binary search is optimal.

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