← 返回 roblox 的题目列表Most Frequent Full Call Path from Trace Logs
类型：online_judge
Problem: Most Frequent Full Call Path from Trace Logs
You are given a chronological list of logs traces describing function entries and exits in a single-threaded program.
Each log is one of:
Entry: "-> funcName"
Exit: "<- funcName"
The call stack starts empty. On every entry event, push the function onto the stack and form the full call path by joining the stack from bottom to top with ->.
Example stack [main, handleEvents, handleClickEvent] corresponds to:
main->handleEvents->handleClickEvent
Your tasks:
Only on each -> event, increment the count of the full call path at that moment.
Return the full call path with the highest frequency.
Tie-breaking
If multiple paths share the same maximum frequency:
Prefer the deeper path (with more function names / larger stack depth).
If depth is also tied, prefer the one that first reached that maximum frequency when scanning logs left-to-right.
If the input is empty, return an empty string "".
I/O
Input: array of strings traces
Output: the most frequent full call path string
Constraints
0 ≤ len(traces) ≤ 100,000
Each line starts with "-> " or "<- "
funcName contains only letters, digits, underscores
Logs are well-formed (every exit matches a previous entry)
No recursion (a function name won’t be re-entered before it returns)
Max call depth ≤ 1,000
Test Cases (5)
Case 1
Input
8
-> main
-> handleEvents
-> handleClickEvent
<- handleClickEvent
-> handleClickEvent
<- handleClickEvent
<- handleEvents
<- main
Output
main->handleEvents->handleClickEvent
Case 2 (tie on frequency, choose earliest to reach max)
Input
12
-> main
-> handleEvents
-> handleKeyEvent
<- handleKeyEvent
-> handleClickEvent
<- handleClickEvent
-> handleClickEvent
<- handleClickEvent
-> handleKeyEvent
<- handleKeyEvent
<- handleEvents
<- main
Output
main->handleEvents->handleClickEvent
Case 3 (empty)
Input
0
Output
Case 4 (tie on frequency, prefer deeper path)
Input
10
-> A
-> B
<- B
-> B
<- B
-> C
-> D
<- D
<- C
<- A
Output
A->B
Case 5
Input
14
-> m
-> a
-> x
<- x
-> y
<- y
<- a
-> b
-> x
<- x
<- b
-> a
<- a
<- m
Output
m->a
Example
Input
8
-> main
-> handleEvents
-> handleClickEvent
<- handleClickEvent
-> handleClickEvent
<- handleClickEvent
<- handleEvents
<- main
Output
main->handleEvents->handleClickEvent