FastPrepQuery Words Within K Positions
Problems/Query Words Within K Positions

Query Words Within K Positions

Palantir logoPalantir● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a Palantir technical phone screen, the candidate got a sentence, a two-word search phrase and a number k. The task was to list the word positions where the phrase starts, when its words show up close enough to each other, with k as the allowed distance. The report includes one worked example with its answer.

The report does not say how distance is counted, whether the words must keep the phrase order, how a longer phrase works, or what the limits are. Here, distance is the difference between word positions, the words must appear in phrase order, each next word must be at most k positions after the one before it (so a whole match can be longer than k), phrases of up to five words are allowed, each start is listed once in increasing order, and the limits and the other examples are ours.

Our version is about 85% the same as the reported question.

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 exactly q[i] for every i, and
  • each next position is at most k after the previous one: p[i + 1] - p[i] <= k for every i from 0 to m - 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, fox at position 4 is 4 - 2 = 2 positions later, which is at most k = 2.
  • From position 7, fox at position 8 is 1 position 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

  • text has 1 to 1000 words.
  • query has 1 to 5 words.
  • Every word in text and query has 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)
All Palantir interview questionsSee Palantir hiring insights
Saved
class Solution {
    public int[] findQueryStarts(String text, String query, int k) {
        // Write your code here.
    }
}
Checking account…