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

Intermediate

Apr 2026

Summary

Capital One ML Engineer screen with a string pairing problem. Pretty focused session, just the one coding question from what I remember.

Questions Asked (1)

Given a list of strings and a target string, count how many ordered pairs (i, j) where i is not equal to j satisfy words[i] concatenated with words[j] equaling the target. Order matters, so both directions count if valid.

Algorithms & Data Structures

Author's notes

My first instinct was brute force, just nested loops, and it works but I knew they'd push back on efficiency.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a hash map to store the frequency of each word in the list. For each word, check if it is a prefix of the target; if so, compute the required suffix and add the frequency of that suffix from the map, subtracting 1 if the word equals the suffix to avoid using the same index twice. This yields O(n * L) time where L is the target length, which is efficient.

Pro tip: Clarify edge cases upfront, such as empty strings, duplicate words, and the i != j condition, and mention that you would handle them explicitly. Also, discuss time and space complexity trade-offs to demonstrate algorithmic maturity.

1. Understand the problem and edge cases

Restate the problem to ensure clarity: count ordered pairs (i, j) with i != j such that words[i] + words[j] == target. Identify edge cases like empty strings, duplicate words, and when no pairs exist.

2. Choose an efficient data structure

Use a hash map to store the frequency of each word. This allows O(1) lookups for the required suffix, making the solution efficient.

3. Iterate and count valid pairs

For each word, check if it is a prefix of the target. If so, compute the suffix needed and add the frequency of that suffix from the map, adjusting for the i != j condition when the word equals the suffix.

4. Handle duplicates and self-pairing

When the word equals the required suffix, subtract 1 from the frequency to avoid pairing the word with itself. This ensures i != j.

5. Analyze complexity and test

State the time complexity O(n * L) and space complexity O(n). Walk through a small example to verify correctness, including edge cases.

Key Points to Mention

Hash map for frequency counting to achieve O(1) lookups
Prefix check: only consider words that are prefixes of the target
Suffix computation: target.substring(word.length())
Handling i != j by subtracting 1 when word equals suffix
Time complexity O(n * L) and space complexity O(n)
Edge cases: empty strings, duplicate words, no valid pairs

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