Indexed Proximity Search
Stripe● HardINTERNPHONE SCREENProblem statement
You are given a text represented by the ordered token array words, a batch of tokenized queries queries, and a nonnegative integer k. Return one list of valid starting positions for each query, in query order.
For a nonempty query with m tokens, a match is a sequence of text positions p0 < p1 < ... < p(m-1) such that:
words[pt]equals the query token at indext, using exact, case-sensitive comparison.- Every consecutive gap satisfies
1 <= p(t+1) - pt <= k. The bound applies to consecutive matched tokens; the total span may exceedk.
Return every valid p0 once, in increasing order. Positions are zero-based token indices, not character offsets. A start is valid if at least one complete match exists; different matches from the same start do not create duplicate answers.
A single-token query returns every occurrence of that token, including when k = 0. An empty query or a query with no complete match returns an empty list. Repeated query tokens must use distinct increasing text positions. All tokens have already been separated; do not split, lowercase, or otherwise normalize them.
Preprocess the unchanged text once and reuse the index across the batch. Query processing should examine occurrence lists for the query tokens instead of rescanning unrelated text tokens. The consecutive-gap, repeated-token, exact-token, and empty-query rules define this practice exercise.
Function
proximityStarts(words: String[], queries: String[][], k: int) → int[][]Examples
Example 1
words = ["The","quick","brown","fox","is","quick","filler","filler","filler","filler","filler","filler","filler","filler","filler","filler","filler","filler","filler","filler","quick","fox"]queries = [["quick","fox"]]k = 2return = [[1,20]]At start 1, fox occurs at 3, a gap of 2. At start 20, fox occurs at 21, a gap of 1. The quick at 5 is too far from the next fox. The filler tokens make explicit the positions omitted by the ellipsis in the reported example.
Example 2
words = ["a","b","x","b","x","c"]queries = [["a","b","c"],["a","c"],["b"]]k = 3return = [[0],[],[1,3]]For the first query, positions 0, 3, and 5 form a match: the consecutive gaps are 3 and 2. Its total span is 5, which is allowed. Choosing b at 1 would fail because the next c is 4 positions away. The second query has no match; the single-word query returns both b positions.
Example 3
words = ["a","a","a"]queries = [["a","a"],["a","a","a"],[]]k = 1return = [[0,1],[0],[]]Repeated query words must use distinct increasing positions. Two adjacent a tokens start at 0 or 1, while three start only at 0. An empty query returns an empty list.
Constraints
0 <= words.length <= 10^4.0 <= queries.length <= 100. Each query contains from 0 through 20 tokens, and the total number of query tokens is at most 500.0 <= k <= words.length.- Every token is a nonempty string containing at most 30 ASCII letters. Token comparison is case-sensitive; repeated tokens are allowed.
- The combined length of all tokens in
wordsandqueriesis at most2 * 10^5characters. - Valid inputs have at most
10^4returned starting positions in total across the whole batch. Return all matching positions; do not truncate any result. - These bounds and the token-array input representation define the practice input domain.