← Capital One Interview Insights

Capital One·Machine Learning Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Capital One ML Engineer coding round, one question, string matching with some tricky edge cases around index collisions. Nothing flashy but it took me longer than I'd like to admit to get the complexity right.

Questions Asked (1)

Q1

Given a list of string fragments and a target string, count all ordered pairs (i, j) where i != j such that concatenating fragments[i] and fragments[j] equals the target string.

Algorithms & Data Structures
Author's notes

My first instinct was just brute force every pair, which works but is obviously too slow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints (e.g., fragment lengths, duplicates, empty strings) and then propose an efficient solution using a hash map to store fragment frequencies. Iterate through each fragment, compute the required complement to reach the target, and count valid pairs while handling the i != j condition and duplicate fragments.

Pro tip: Mention edge cases like empty strings, duplicate fragments, and fragments longer than the target, and discuss how to handle them without breaking the solution. Also, note that the order of concatenation matters, so (i, j) and (j, i) are distinct unless fragments are identical.

1. Clarify requirements and constraints

Ask about input size, character set, possibility of empty strings, and whether fragments can be used multiple times. Confirm that pairs are ordered and i != j.

2. Design an efficient algorithm

Use a hash map to count occurrences of each fragment. For each fragment, compute the complement needed to form the target and look it up in the map, adjusting counts for the i != j condition.

3. Handle edge cases and duplicates

Account for cases where the complement equals the current fragment (need to subtract 1 from count) and where fragments are duplicated. Also consider fragments longer than the target.

4. Analyze complexity and optimize

State that the solution runs in O(n * L) time where n is the number of fragments and L is the average fragment length, and O(n) space. Discuss potential optimizations if needed.

5. Test with examples

Walk through a small example to verify correctness, including cases with duplicates and the i != j condition.

Key Points to Mention

  • Use a hash map to store fragment frequencies for O(1) lookups.
  • Handle the i != j condition by subtracting 1 when the complement equals the current fragment.
  • Consider duplicate fragments and how they contribute to multiple pairs.
  • Account for empty strings and fragments longer than the target.
  • Time complexity: O(n * L) where L is the length of the target (or average fragment length).
  • Space complexity: O(n) for the hash map.

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