Count ordered pairs that concatenate to target
Company: Capital One
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given a list of integers `numbers` and an integer `target`, count the number of **ordered pairs** `(i, j)` with `i != j` such that concatenating `numbers[i]` followed by `numbers[j]` (in base-10) produces exactly `target`.
More precisely, treat each integer as its usual base-10 string without extra leading zeros (e.g., `12 -> "12"`). Count pairs where:
`str(numbers[i]) + str(numbers[j]) == str(target)`.
Return the total count.
## Example
- `numbers = [1, 212, 12, 12]`, `target = 1212`
Valid ordered pairs:
- `(0, 1)`: `"1" + "212" = "1212"`
- `(2, 3)`: `"12" + "12" = "1212"`
- `(3, 2)`: `"12" + "12" = "1212"`
Return `3`.
## Assumptions / Constraints
- Assume all integers are non-negative.
- `1 ≤ len(numbers) ≤ 2e5` (you should aim for better than `O(n^2)` if possible).
- Values fit in 32-bit signed integers.
Quick Answer: This question evaluates a candidate's ability to manipulate string and numeric representations, perform efficient counting, and leverage associative data structures to identify matching concatenations.
Given non-negative integers numbers and an integer target, count ordered index pairs (i, j), i != j, such that str(numbers[i]) + str(numbers[j]) == str(target).
Constraints
- 1 <= len(numbers) <= 2e5
- numbers are non-negative
Examples
Input: ([1, 212, 12, 12], 1212)
Expected Output: 3
Input: ([12, 12], 1212)
Expected Output: 2
Hints
- A valid pair corresponds to a split of str(target).
- When both sides of the split are equal, subtract self-pairs.