FastPrepCount Adjacent Symbol Pairs for BPE

Count Adjacent Symbol Pairs for BPE

Amazon logoAmazon● EasyINTERNONSITE INTERVIEW

Problem statement

You are given a training vocabulary for a byte-pair encoding (BPE) tokenizer: words[i] appears freqs[i] times in the corpus.

Each word is split into symbols: its letters in order, followed by the end-of-word marker "</w>". For example, "low" becomes l, o, w, </w>, with the neighboring pairs (l, o), (o, w) and (w, </w>).

The count of a pair is the total, over all words, of how many times the pair appears in the word times the word's frequency. If the same word appears more than once in words, each entry counts.

The problem statement continues
Pro

Examples

Example 1

words = ["low","lower","newest","widest"]freqs = [5,2,6,3]return = ["e s 9","s t 9","t </w> 9","w e 8","l o 7","o w 7","e w 6","n e 6","w </w> 5","d e 3","i d 3","w i 3","e r 2","r </w> 2"]

The classic BPE example. low (5) and lower (2) both contain (l, o) and (o, w), giving 7 each. newest (6) and widest (3) both end in e, s, t, </w>, so (e, s), (s, t) and (t, </w>) get 9 each.

The three pairs with 9 come first, ordered by their left symbols e < s < t. Then (w, e) has 2 + 6 = 8, from lower and newest.

FastPrep Pro
Reported in 1 Amazon interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week
See Amazon hiring insights
CodePython 3
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Amazon interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week