Implement string/matrix simulations and counting pairs
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given several independent implementation-focused tasks. For each task, write a function that returns the required value.
## Task 1 — Count matching 3-character windows (case-insensitive)
Given a string `s`, consider every contiguous substring of length 3: `s[i..i+2]` for `0 ≤ i ≤ len(s)-3`.
Count how many such windows satisfy:
- `lower(s[i]) == lower(s[i+2])` (case-insensitive comparison)
**Output:** an integer count.
**Notes:**
- If `len(s) < 3`, the answer is `0`.
---
## Task 2 — Grid “match-3” explosion with gravity
You are given an `m x n` integer matrix `grid` where each integer represents a “color”.
A cell `(r, c)` has up to 4 orthogonal neighbors: up, down, left, right.
### Explosion rule
A cell `(r, c)` is considered a **trigger** if **at least 2** of its orthogonal neighbors have the **same value** as `grid[r][c]`.
When a cell triggers, the cell itself and all orthogonal neighbors that match its value are marked to be removed.
All removals for the step happen **simultaneously**.
### Gravity rule
After removals, the removed positions become empty. Then, for each column independently:
- All remaining values in the column “fall” downward (preserving their relative order).
- Empty cells are filled at the top with `0`.
### Iteration
Repeat **Explosion → Gravity** until no more cells trigger.
**Output:** the final matrix after the process stabilizes.
**Clarifications:**
- `0` is treated as an empty cell after gravity; it does **not** participate in explosions.
---
## Task 3 — Count ordered pairs that form a target string
Given a list of strings `words` of length `n` and a target string `target`, count the number of **ordered** index pairs `(i, j)` such that:
- `0 ≤ i, j < n`
- `i != j`
- `words[i] + words[j] == target`
**Output:** an integer count.
**Important:** Ordered pairs are distinct, so `(i, j)` and `(j, i)` are counted separately when both satisfy the condition.
Quick Answer: This multi-part question evaluates implementation skills in string processing (case-insensitive substring matching), grid simulation with iterative match-and-collapse rules and gravity, and combinatorial counting of ordered string-pair concatenations.
Count Matching 3-Character Windows
Given a string s, count length-3 windows where the first and third characters match case-insensitively.
Examples
Input: ('abAxxX',)
Expected Output: 2
Input: ('ab',)
Expected Output: 0
Input: ('AaA',)
Expected Output: 1
Hints
- Compare s[i] and s[i+2] after lowercasing.
Match-3 Explosion with Gravity
Repeatedly remove every non-zero cell that has at least two orthogonal neighbors with the same value, also removing those matching neighbors. Apply gravity in each column after simultaneous removals. Return the stabilized grid.
Constraints
- 0 is empty and never explodes
- Removals in a step are simultaneous
Examples
Input: ([[1, 1, 1], [2, 3, 1], [2, 2, 2]],)
Expected Output: [[0, 0, 0], [0, 0, 0], [0, 3, 0]]
Input: ([[1, 2], [3, 4]],)
Expected Output: [[1, 2], [3, 4]]
Input: ([[0, 1, 0], [1, 1, 1], [0, 1, 0]],)
Expected Output: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Hints
- Collect cells to remove before mutating the grid.
- Gravity preserves vertical order of remaining values.
Count Ordered Word Concatenation Pairs
Count ordered pairs of distinct indices (i, j) such that words[i] + words[j] == target.
Constraints
- Ordered pairs count separately
- i and j must be different
Examples
Input: (['a', 'b', 'ab', 'a'], 'ab')
Expected Output: 2
Input: (['x', 'x'], 'xx')
Expected Output: 2
Input: (['', 'a', ''], 'a')
Expected Output: 4
Hints
- Use target splits and word frequencies.