You receive execution-trace records from a program. Each record marks either a function invocation or a function return. Process the records in order while keeping track of the currently active calls. Whenever execution enters a function, increment the count for the complete stack at that moment.
For instance, after an enter event, the active calls could be:
bootstrap -> dispatchInput -> processTap
The path counted for that event would be:
bootstrap->dispatchInput->processTap
This task may also be described as identifying the most frequent function call, call route, call chain, or stack trace. It is commonly presented in three stages:
A tie-break detail should be confirmed during an interview: some versions favor shallower paths, whereas the usual extension favors deeper ones. Here, rank candidates by count first, then by greater depth, and finally by which path attained that count earlier.
A single-thread trace uses records such as:
"-> bootstrap" # invoke bootstrap
"<- bootstrap" # return from bootstrap
The whitespace after an arrow is optional, so inputs such as "->bootstrap" and "<-bootstrap" must also be accepted.
In the multithreaded form, every record begins with its thread identifier:
"3 -> bootstrap"
"3 <- bootstrap"
"8 -> background_job"
Unless stated otherwise, traces are valid: a return always corresponds to the function atop that thread's stack, names contain only letters, digits, or underscores, and nesting depth is limited.
Given single-thread trace records, produce the call path with the largest number of entry occurrences. Count a path only when a function is entered.
Return an empty string when the input contains no records. For Part 1, if several paths have equal counts, choose the one that first reached that count during the left-to-right scan.
from typing import List
def most_frequent_call_path_deepest_tie(traces: List[str]) -> str:
pass
traces = [
"-> bootstrap",
"-> routeRequest",
"-> loadProfile",
"<- loadProfile",
"-> loadProfile",
"<- loadProfile",
"<- routeRequest",
"<- bootstrap",
]
most_frequent_call_path_deepest_tie(traces)
# "bootstrap->routeRequest->loadProfile"
traces = ["-> bootstrap",bootstrap->routeRequest->loadProfile
| 0 | 1 | |
|---|---|---|
| 0 | evt | funct… |
| 1 | + | boots… |
| 2 | + | route… |
| 3 | + | loadP… |
| 4 | - | loadP… |
| 5 | + | loadP… |
| 6 | - | loadP… |
| 7 | - | route… |
| 8 | - | boots… |
The single-thread trace has four enter (+) and four return (-) records.
The entry records contribute these paths:
| Enter record | Path added | Total so far |
|---|---|---|
-> bootstrap | bootstrap | 1 |
-> routeRequest | bootstrap->routeRequest | 1 |
first -> loadProfile | bootstrap->routeRequest->loadProfile | 1 |
second -> loadProfile | bootstrap->routeRequest->loadProfile | 2 |
The deepest route is observed twice, making it the result.
Apply the following comparison order:
from typing import List
def most_frequent_call_path_deepest_tie(traces: List[str]) -> str:
pass
traces = [
"-> bootstrap",
"-> routeRequest",
"-> parseQuery",
"<- parseQuery",
"-> renderPage",
"<- renderPage",
"-> renderPage",
"<- renderPage",
"-> parseQuery",
"<- parseQuery",
"<- routeRequest",
"<- bootstrap",
]
most_frequent_call_path_deepest_tie(traces)
# "bootstrap->routeRequest->renderPage"
The renderPage path and parseQuery path each occur twice at the same depth; renderPage reaches frequency two first.
Each leaf path appears two times:
bootstrap->routeRequest->renderPagebootstrap->routeRequest->parseQueryTheir frequencies and depths match, so the result is the path that reached frequency 2 earlier.
Each trace record now supplies a thread ID. Events from separate threads may be mixed together. Keep a distinct stack and distinct path-frequency map for every thread, and return the Part 2 result independently for each one.
from typing import Dict, List
def most_frequent_call_path_deepest_tie(traces: List[str]) -> Dict[str, str]:
pass
traces = [
"4 -> server",
"9 -> cleanup",
"4 -> authorize",
"4 <- authorize",
"9 -> purge_cache",
"9 <- purge_cache",
"9 <- cleanup",
"4 <- server",
]
most_frequent_call_path_deepest_tie(traces)
# {
# "4": "server->authorize",
# "9": "cleanup->purge_cache",
# }
For thread 4, both server and server->authorize occur once; the Part 2 rule chooses the deeper one. Thread 9 is evaluated the same way.
Related versions ask for the winning frequency, the maximum-depth stack, or the most common function name for each thread. The API sketches below are preparation-oriented examples rather than official interfaces.
assert most_frequent_call_path_deepest_tie([
"-> bootstrap",
"-> routeRequest",
"-> loadProfile",
"<- loadProfile",
"-> loadProfile",
"<- loadProfile",
"<- routeRequest",
"<- bootstrap",
]) == "bootstrap->routeRequest->loadProfile"
assert most_frequent_call_path_deepest_tie([]) == ""
# In Part 1, equal frequencies keep the route that reached that count first.
assert most_frequent_call_path_deepest_tie([
"-> Root",
"-> Left",
"<- Left",
"-> Right",
"<- Right",
"<- Root",
]) == "Root"
# In Part 2, a deeper route wins when its count equals a shallower route's count.
assert most_frequent_call_path_deepest_tie([
"-> Root",
"-> Child",
"<- Child",
"<- Root",
]) == "Root->Child"
traces = ["-> bootstrap",bootstrap->routeRequest->loadProfile
| 0 | 1 | |
|---|---|---|
| 0 | evt | funct… |
| 1 | + | boots… |
| 2 | + | route… |
| 3 | + | loadP… |
| 4 | - | loadP… |
| 5 | + | loadP… |
| 6 | - | loadP… |
| 7 | - | route… |
| 8 | - | boots… |
The single-thread trace has four enter (+) and four return (-) records.