Find where a query's words appear in order, each within k positions
Company: Palantir
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a text, a query and an integer `k`. Find every place where the words of the query appear in the text in the same order, with each query word at most `k` word positions after the previous one. Return the index of the word where each such match begins.
The report gives one example and states the rule only loosely; the Rules below fix the details in a way that reproduces that example.
### Function Signature
```python
def find_query_matches(text: str, query: str, k: int) -> list[int]:
```
### Rules
- Split `text` and `query` on single spaces into words, and index the words of `text` from `0`.
- Let the query words be `q[0], q[1], ..., q[m-1]`. A match starting at index `p[0]` is a sequence of indices `p[0] < p[1] < ... < p[m-1]` such that the text word at `p[j]` equals `q[j]` exactly, and `p[j] - p[j-1] <= k` for every `j >= 1`. Words between the matched words are ignored.
- Return, in increasing order, every index `p[0]` at which at least one match starts. Each start index appears once, even if several matches start there. Return `[]` if there is no match.
- With a one-word query, every occurrence of that word is a match start.
### Constraints
- `1 <=` number of words in `text` `<= 10^5`
- `1 <=` number of words in `query` `<= 10`, and the query may repeat a word
- `1 <= k <= 10^5`
- Every word consists of 1 to 20 lowercase English letters; neither string has leading, trailing or repeated spaces.
### Examples
**Example 1**
```text
Input: text = "the small quick fast fox is running quick fox", query = "quick fox", k = 2
Output: [2, 7]
```
"quick" at index 2 and "fox" at index 4 are 2 positions apart, which is allowed. "quick" at 7 and "fox" at 8 are 1 apart.
**Example 2**
```text
Input: text = "red blue blue green gold", query = "red blue gold", k = 2
Output: [0]
```
The indices 0, 2 and 4 form a match: each step is 2 positions. Continuing from "blue" at 1 would need "gold" at index 2 or 3, which holds "blue" and "green", but one valid match is enough.
**Example 3**
```text
Input: text = "fox jumps quick fox", query = "fox quick", k = 1
Output: []
```
"fox" at 0 would need "quick" at index 1, which holds "jumps"; "fox" at 3 has no word after it. "quick" followed by "fox" does not count, because the order of the query matters.
Overview: Given a text, a multi-word query and a distance k, return every word index where the query's words begin a match: they appear in order, each at most k positions after the previous one. The problem tests turning a loosely stated rule into precise semantics, tokenization, and an efficient search over many candidate matches.
You are given a string `text`, a string `query` and an integer `k`. Find every place where the words of the query appear in the text in the same order, with each query word at most `k` word positions after the previous one, and return the index of the text word where each such match begins.
Rules:
- Split `text` and `query` on single spaces into words, and index the words of `text` from 0.
- Let the query words be q[0], q[1], ..., q[m-1]. A match starting at index p[0] is a sequence of indices p[0] < p[1] < ... < p[m-1] such that the text word at p[j] equals q[j] exactly (whole words), and p[j] - p[j-1] <= k for every j >= 1. Words between the matched words are ignored.
- Return, in increasing order, every index p[0] at which at least one match starts. Each start index appears once, even if several matches start there. Return an empty list if there is no match.
- With a one-word query, every occurrence of that word is a match start.
Example 1:
Input: text = "the small quick fast fox is running quick fox", query = "quick fox", k = 2
Output: [2, 7]
Explanation: "quick" at index 2 and "fox" at index 4 are 2 positions apart, which is allowed. "quick" at 7 and "fox" at 8 are 1 apart.
Example 2:
Input: text = "red blue blue green gold", query = "red blue gold", k = 2
Output: [0]
Explanation: The indices 0, 2 and 4 form a match: each step is 2 positions. Continuing from "blue" at 1 would need "gold" at index 2 or 3, which hold "blue" and "green", but one valid match is enough.
Constraints:
- 1 <= number of words in text <= 10^5
- 1 <= number of words in query <= 10, and the query may repeat a word
- 1 <= k <= 10^5
- Every word consists of 1 to 20 lowercase English letters; neither string has leading, trailing or repeated spaces.
No value exceeds 2^31 - 1: every input number and every returned index fits in a 32-bit signed integer (each returned index is below 10^5).
Constraints
- 1 <= number of words in text <= 10^5
- 1 <= number of words in query <= 10, and the query may repeat a word
- 1 <= k <= 10^5
- Every word consists of 1 to 20 lowercase English letters; neither string has leading, trailing or repeated spaces.
Examples
Input: ('the small quick fast fox is running quick fox', 'quick fox', 2)
Expected Output: [2, 7]
Explanation: Source Example 1 (text is 45 characters, 9 words): quick@2 -> fox@4 is a gap of exactly k = 2, quick@7 -> fox@8 is a gap of 1.
Input: ('red blue blue green gold', 'red blue gold', 2)
Expected Output: [0]
Explanation: Source Example 2, nearest-greedy regression: red@0 -> blue@1 dead-ends (gold@4 is 3 away), but red@0 -> blue@2 -> gold@4 works.
Hints
- In Example 2 the 'blue' right after 'red' leads nowhere while a farther 'blue' still completes the match, so committing to one particular occurrence of the next query word too early can miss a valid match.
- The distance limit applies between each pair of consecutive matched words, not between the first and the last matched word.
- Because the indices must be strictly increasing, one text word can never fill two query positions, even when the query repeats a word.