FastPrep
Problem · Hash Table

Most Frequent Call Stack Per Thread

Learn this problem
● MediumRobloxPHONE SCREEN
See Roblox hiring insights

Problem statement

You are given an array samples containing full call-stack observations from multiple threads. Each record has the format threadId|frame1>frame2>...>frameD, where frames are ordered from the root call to the active leaf call.

Compute the most frequent full call stack independently for every observed thread:

  • Each record contributes one occurrence of its exact full stack path to that record's thread.
  • Thread IDs, frame names, and full paths are case-sensitive.
  • If several paths in one thread have the same highest frequency, choose the lexicographically smallest full path string.
  • Statistics from different threads never affect one another.

Return one string per observed thread using the format threadId|winningPath|frequency. Order the result by threadId in ascending lexicographic order. If samples is empty, return an empty array.

Function

mostFrequentCallStackPerThread(samples: String[]) → String[]

Examples

Example 1

samples = ["worker-2|main>parse","worker-1|main>cache","worker-2|main>parse","worker-1|main>db","worker-1|main>cache","worker-2|main>render","worker-3|run"]return = ["worker-1|main>cache|2","worker-2|main>parse|2","worker-3|run|1"]

worker-1 samples main>cache twice and main>db once. worker-2 samples main>parse twice and main>render once. worker-3 has one sample. The three statistics are returned in thread-ID order.

Example 2

samples = ["t2|root>zeta","t1|root>beta","t2|root>alpha","t1|root>alpha"]return = ["t1|root>alpha|1","t2|root>alpha|1"]

Within each thread, both observed paths have frequency 1. The path root>alpha is lexicographically smaller, so it wins both independent ties.

Example 3

samples = ["alpha|run>work","beta|main","alpha|run>work>work","alpha|run>work>work","beta|main"]return = ["alpha|run>work>work|2","beta|main|2"]

Repeated frame names are part of the exact path. Thread alpha selects run>work>work with frequency 2, while thread beta selects main with frequency 2.

Example 4

samples = []return = []

No threads or stack samples are observed, so the result is empty.

Constraints

  • 0 <= samples.length <= 200000
  • Every record has exactly one | delimiter and follows threadId|frame1>frame2>...>frameD.
  • Each threadId is non-empty and contains only letters, digits, underscores, or hyphens.
  • Each frame name is non-empty and contains only letters, digits, or underscores.
  • 1 <= D <= 50 for every sample.
  • The total number of characters across all samples is at most 2 * 10^6.

More Roblox problems

drafts saved locally
public String[] mostFrequentCallStackPerThread(String[] samples) {
    // write your code here
}
samples["worker-2|main>parse","worker-1|main>cache","worker-2|main>parse","worker-1|main>db","worker-1|main>cache","worker-2|main>render","worker-3|run"]
expected["worker-1|main>cache|2", "worker-2|main>parse|2", "worker-3|run|1"]
checking account