FastPrepFrequency-Weighted Next-Word Sampling
Problems/Frequency-Weighted Next-Word Sampling

Frequency-Weighted Next-Word Sampling

Google logoGoogle● MediumINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was a PhD intern interview. The firsthand Google internship report builds next-word counts from training sequences. It first discusses the most frequent next word, then asks for random output weighted by frequency and how to handle many next words. We keep the weighted model, but the caller supplies zero-based tickets, so every sample is always the same and can be checked.

Train a next-word model from several token sequences. Within each sequence, every adjacent pair contributes one observation from its first token to its second; sequence boundaries never create observations.

For query queries[i], let its observed successors be sorted lexicographically. Their frequencies form consecutive weighted ranges in that order. If the query has total successor observations, tickets[i] is an integer from 0 through total - 1; return the successor whose range contains that ticket. Thus a successor observed f times owns exactly f tickets.

If a query has no observed successor, its ticket is 0 and the answer is the empty string. Return one sampled word per query.

Function

sampleNextWords(training: String[][], queries: String[], tickets: int[]) → String[]

Examples

Example 1

training = [["a","b","c"],["a","s","d"],["a","b","d"]]queries = ["a","b","x"]tickets = [2,1,0]return = ["s","d",""]

After a, lexicographic successor ranges are b:[0,2) and s:[2,3). After b, c owns ticket 0 and d owns ticket 1. The unseen query x returns an empty string.

Example 2

training = [["go","left"],["go","right"],["go","right"]]queries = ["go","go","go"]tickets = [0,1,2]return = ["left","right","right"]

Lexicographic order gives left the first ticket and right the next two tickets, matching their frequencies one and two.

Constraints

  • 1 <= training.length, queries.length <= 100000
  • Each training sequence contains between 1 and 100000 tokens.
  • The total number of training tokens and query tokens is at most 300000.
  • Every token contains 1 to 40 printable ASCII characters.
  • queries.length == tickets.length.
  • For a query with successor count total > 0, 0 <= tickets[i] < total; otherwise tickets[i] == 0.

More Google Phone Screen questions

  • Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
  • Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
  • Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
  • File Storage ServiceCresta · PHONE SCREENCresta interview questions
  • Snapshot Map with Sparse Version HistorySnorkel AI · PHONE SCREEN
  • Return Every Matching DecryptionDuolingo · PHONE SCREENDuolingo interview questions
  • Design a Food Rating SystemApple · PHONE SCREENApple interview questions
  • Time-Based Key-Value StoreOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions
  • Time-Based Key-Value StoreCockroach Labs · PHONE SCREEN · ONSITE INTERVIEW
  • Time Map with Sum and AverageConfluent · PHONE SCREENConfluent interview questions
  • Structured Log Stream with QueriesOpenAI · PHONE SCREENOpenAI interview questions
  • Hierarchical In-Memory File SystemClay · PHONE SCREEN

Interview reports that mention this question

  • Google SWE and PhD Intern Coding: 14 Experiences (Part 3 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public String[] sampleNextWords(String[][] training, String[] queries, int[] tickets) {
        // Write your code here.
    }
}
Checking account…