How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Capital One.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Capital One during technical interviews.

Count ordered fragment pairs forming a password

Quick Overview

This question evaluates proficiency with string manipulation, handling duplicate fragments, and combinatorial reasoning about ordered index pairs that concatenate to a target, reflecting algorithmic problem-solving and correctness under index distinctness constraints.

Company: Capital One

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given: - A target string `password`. - A list of `N` string fragments `fragments[0..N-1]` (fragments may repeat). Count the number of **ordered pairs of distinct indices** `(i, j)` such that: `fragments[i] + fragments[j] == password` Notes: - “Ordered” means `(i, j)` and `(j, i)` are counted separately when both satisfy the condition. - Indices must be distinct (`i != j`). **Input:** `password`, `fragments`. **Output:** an integer count (potentially large; specify/assume 64-bit). State any constraints you assume and handle duplicates correctly.

Quick Answer: This question evaluates proficiency with string manipulation, handling duplicate fragments, and combinatorial reasoning about ordered index pairs that concatenate to a target, reflecting algorithmic problem-solving and correctness under index distinctness constraints.

You are given a target string `password` and a list of `N` string `fragments` (fragments may repeat). Count the number of ordered pairs of distinct indices `(i, j)` with `i != j` such that `fragments[i] + fragments[j] == password`. `(i, j)` and `(j, i)` are counted separately when both satisfy the condition. The count can be large, so use a 64-bit integer. Approach: for every split position `k` of `password` into `prefix = password[:k]` and `suffix = password[k:]` (including the empty-prefix and empty-suffix splits, so `k` ranges from `0` to `len(password)`), let `a` = number of fragments equal to `prefix` and `b` = number of fragments equal to `suffix`. If `prefix != suffix`, every prefix-fragment can pair with every suffix-fragment: add `a * b`. If `prefix == suffix`, a fragment cannot pair with itself, so add `a * (a - 1)` (ordered, excluding `i == j`). Counting fragment frequencies once with a hash map makes this O(N + L^2) where L = len(password).

Constraints

1 <= len(password)
0 <= N (fragments may be empty; fragments may repeat)
The answer can exceed 32-bit range; use a 64-bit integer.
Empty-string fragments are allowed and count when '' + password == password or password + '' == password.

Examples

Input: ("abc", ["a", "bc", "ab", "c"])

Expected Output: 2

Explanation: Valid ordered pairs: ("a","bc") at indices (0,1) and ("ab","c") at indices (2,3). Each split contributes one pair, total 2.

Input: ("aa", ["a", "a"])

Expected Output: 2

Explanation: Split "a"+"a". prefix==suffix=="a" with count 2, so a*(a-1)=2*1=2: ordered pairs (0,1) and (1,0).

Input: ("aa", ["a"])

Expected Output: 0

Explanation: Only one fragment equals "a". Since i must differ from j and there is no second "a", no pair forms; a*(a-1)=1*0=0.

Input: ("abcd", ["ab", "cd", "abc", "d", "a", "bcd"])

Expected Output: 3

Explanation: Splits that match: "a"+"bcd", "ab"+"cd", and "abc"+"d" — three distinct ordered pairs.

Input: ("xyxy", ["xy", "xy", "xy"])

Expected Output: 6

Explanation: Only split "xy"+"xy" works; prefix==suffix=="xy" with count 3, giving 3*2=6 ordered distinct-index pairs.

Input: ("hello", ["hel", "world", "lo"])

Expected Output: 1

Explanation: Only "hel"+"lo"=="hello" matches (count 1 each, different strings): one ordered pair.

Input: ("ab", [])

Expected Output: 0

Explanation: Empty fragment list: no pairs possible.

Input: ("a", ["a", "", "a"])

Expected Output: 4

Explanation: Edge case with an empty-string fragment. Split ""+"a": prefix "" (count 1) times suffix "a" (count 2)=2. Split "a"+"": 2*1=2. Total 4 ordered pairs.

Hints

Brute force over all i != j is O(N^2). Instead, note that a valid pair must split `password` at exactly one position into a prefix and a suffix.
Count how many fragments equal each string with a hash map, then for each of the L+1 split positions multiply (count of prefix) by (count of suffix).
When prefix == suffix the two halves are the same string, and a single fragment cannot pair with itself: use a*(a-1) instead of a*a to respect i != j.

Quick Overview