← Trexquant Interview Insights

Trexquant·Data Scientist·Online Assessment (OA)·Intermediate

Intermediate
May 2026

Summary

Got an OA from Trexquant for a Data Scientist role and it was pretty much a straight-up coding problem. Not a lot of context given, just a problem statement and a hint.

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 result.

Algorithms & Data Structures
Author's notes

The hint basically gave it away: 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 answer is the largest prefix of the removable array that can be removed while p remains a subsequence of s. Use binary search on the number of removals, and for each candidate prefix, check if p is a subsequence of the remaining string in O(n) time. This yields an O((n + m) log m) solution, which is optimal for typical constraints.

Pro tip: Mention that a linear two-pointer check for subsequence is sufficient for each binary search step, and that the monotonic property (if removing k characters works, removing fewer also works) justifies binary search. Also note that if p is not a subsequence of s initially, the answer is 0.

1. Clarify the problem and constraints

Confirm that removals must be applied in the given order, and that we want the maximum number of removals from the prefix of the removable array. Ask about input sizes to choose the right algorithm.

2. Identify the monotonic property

Observe that if removing the first k characters (in order) keeps p as a subsequence, then removing any smaller number also works. This monotonicity enables binary search on k.

3. Design the subsequence check

For a given k, mark the first k indices in the removable array as removed, then use a two-pointer scan over s and p to verify if p is still a subsequence of the remaining characters.

4. Binary search for the maximum k

Set low = 0, high = length of removable array. While low < high, compute mid, check if removing mid characters works, and adjust bounds accordingly. Return the largest valid k.

5. Analyze complexity and edge cases

State that each check is O(n), and binary search adds a log m factor, giving O((n + m) log m) time and O(n) space for marking removed indices. Handle cases where p is not a subsequence initially or removable array is empty.

Key Points to Mention

  • Monotonicity of the removal process: if k removals work, any smaller number also works.
  • Binary search on the number of removals to achieve O((n + m) log m) time complexity.
  • Two-pointer technique for checking if p is a subsequence of the remaining string in O(n) time.
  • Use of a boolean array or set to efficiently mark removed indices for each check.
  • Edge cases: p not a subsequence of s initially (answer 0), empty removable array, or all characters removable.
  • Space-time trade-off: O(n) extra space for marking removed indices, which can be optimized by reusing the array.

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