FastPrepMarkov Transition Counts and Probabilities

Markov Transition Counts and Probabilities

Retool logoRetool● MediumFULLTIMEONSITE INTERVIEW
Learn

Problem statement

Given an observed token sequence, count every adjacent transition from a current token to its next token.

Return one row for each observed transition in the exact form current->next:count/total, where total is the number of outgoing transitions observed from current. The fraction is intentionally not reduced. Sort rows first by current, then by next.

Function

markovTransitionStats(tokens: String[]) → String[]

Examples

Example 1

tokens = ["a","b","a","c","a","b"]return = ["a->b:2/3","a->c:1/3","b->a:1/1","c->a:1/1"]

The three outgoing transitions from a go to b twice and c once.

Example 2

tokens = ["x","x","x"]return = ["x->x:2/2"]

Both adjacent pairs are self-transitions.

Example 3

tokens = ["z","a"]return = ["z->a:1/1"]

One pair creates one certain transition.

Constraints

  • 2 <= tokens.length <= 200000.
  • Each token has 1 to 30 lowercase English letters.

More Retool problems

See Retool hiring insights
public String[] markovTransitionStats(String[] tokens) {
    // write your code here
}
tokens["a","b","a","c","a","b"]
expected["a->b:2/3", "a->c:1/3", "b->a:1/1", "c->a:1/1"]
Checking account…