Query Words Within K Positions
Updated
Problem statement
You are given a string text of words separated by single spaces, a string query of one or more words separated by single spaces, and an integer k. The words of text are numbered by position, starting from 0.
Let the query words be q[0], q[1], ..., q[m - 1]. A match is a list of positions p[0] < p[1] < ... < p[m - 1] where:
- the word at position
p[i]is exactlyq[i]for everyi, and - each next position is at most
kafter the previous one:p[i + 1] - p[i] <= kfor everyifrom0tom - 2.
So the query words must appear in query order, and the limit applies to each step. A whole match may span more than k positions.
Return, in increasing order, every position p[0] where at least one match starts. List each start once, even if several matches begin there. Return an empty array if there is no match.
Function
findQueryStarts(text: String, query: String, k: int) → int[]Examples
Example 1
text = "the small quick fast fox is running quick fox"query = "quick fox"k = 2return = [2,7]The words are numbered from 0. quick is at positions 2 and 7, and fox is at positions 4 and 8.
- From position
2,foxat position4is4 - 2 = 2positions later, which is at mostk = 2. - From position
7,foxat position8is1position later.
Both starts work, so the answer is [2,7].
Example 2
text = "fox quick fox jumps quick dog dog fox"query = "quick fox"k = 2return = [1]quick is at positions 1 and 4. From position 1, fox at position 2 is 1 position later, so 1 is a start.
From position 4, the next fox is at position 7, which is 3 positions later and more than k = 2. The fox at positions 0 and 2 comes before it, and query words must appear in query order. So the answer is [1].
Example 3
text = "red blue blue gray green"query = "red blue green"k = 2return = [0]The only red is at position 0. If blue is taken at position 1, the next word must be green at position 2 or 3, but those are blue and gray.
Taking blue at position 2 instead works: it is 2 positions after red, and green at position 4 is 2 positions after it. Each step is at most k = 2, even though the whole match spans 4 positions. The answer is [0].
Constraints
texthas 1 to 1000 words.queryhas 1 to 5 words.- Every word in
textandqueryhas 1 to 10 lowercase English letters. - Words are separated by single spaces, with no leading or trailing spaces.
1 <= k <= 1000
More Palantir interview questions
- Balanced Session ManagerPHONE SCREEN · Seen Oct 2026
- Employees With Shared InterestsPHONE SCREEN · Seen Jul 2025
- Merge a 2048 RowPHONE SCREEN · Seen Jan 2025
- Encrypt Letters by First-Occurrence SubstitutionPHONE SCREEN · Seen Aug 2022
- Encrypt Text by Columnar TranspositionPHONE SCREEN · Seen Aug 2022
- Basic Item DiscountsOA · Seen Nov 2026
- Optimize Discount Selection Under a Point BudgetOA · Seen Nov 2026
- Stacked Item and Category DiscountsOA · Seen Nov 2026
- Map and Accumulate Learning QueriesONSITE INTERVIEW · Seen Oct 2026
- Relational Learning QueriesONSITE INTERVIEW · Seen Apr 2025
Similar questions at other companies
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Most Relevant Text SpanHebbia · PHONE SCREEN
- Word BreakBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Longest Common Contiguous User ActionsWayfair · PHONE SCREENWayfair interview questions
- Longest Common URL History RunDatadog · PHONE SCREENDatadog interview questions
- Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
- Recursively Expanded Shell Command CountsZipRecruiter · OAZipRecruiter interview questions
- Merge Weekday and Time IntervalsNextdoor · PHONE SCREENNextdoor interview questions
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
Palantir interview experiences
- Palantir FDSE Experienced-Hire Interviews: 5 Experiences
- Palantir FDSE New Grad OA Questions: 6 Experiences (Part 2 of 2)
- Palantir FDSE New Grad Interviews: 5 Experiences (Part 1 of 2)
- Palantir FDSE Intern OA and Interviews: 3 Experiences
- Palantir FDSE Karat and Learning: 7 Experiences (Part 2 of 2)
- Palantir FDSE OA and Interviews: 16 Experiences (Part 1 of 2)