← 返回 roblox 的题目列表Most Frequent Function Call Path in Interleaved Multi-Threaded Logs
类型：online_judge
Most Frequent Function Call Path in Interleaved Multi-Threaded Logs
You are given function-call logs emitted by multiple threads. Log entries from different threads may be interleaved, but the call sequence within each individual thread is valid.
Each log entry has one of these formats:
START threadId functionName
END threadId functionName
For each thread, when a START event occurs, that thread's active stack from its root function to the newly started function is a call path. For example, if thread t1 has stack main -> parse -> tokenize, its path is main->parse->tokenize.
Return the most frequent call path across all threads, joining function names with ->.
If multiple paths have the same maximum frequency, return the lexicographically smallest path.
Input Format
The first line contains an integer N, the number of log entries.
The next N lines each contain START threadId functionName or END threadId functionName.
Output Format
Print the most frequent call path.
Constraints
1 <= N <= 200,000
threadId and function names contain no spaces.
The log sequence for every individual thread is valid and does not underflow its stack.
Entries from different threads may be arbitrarily interleaved.
Example
Input:
10
START t1 main
START t2 worker
START t1 parse
END t1 parse
START t2 task
END t2 task
START t1 parse
END t1 parse
END t1 main
END t2 worker
Output:
main->parse
The path main->parse occurs twice in thread t1.
Example
Input
10
START t1 main
START t2 worker
START t1 parse
END t1 parse
START t2 task
END t2 task
START t1 parse
END t1 parse
END t1 main
END t2 worker
Output
main->parse