Roblox VO 面试真题解析：Calls｜调用栈统计

Your team is debugging a program’s performance. A tracing tool records all function calls and returns, producing a sequence of events. Your task is to analyze these raw traces and determine which call stack occurs most frequently.

Identifying the most frequent call stack will provide insights into where the main slowdown may be occurring.

Input:

• An array of strings, where each string represents a traced function call or return
• Function calls have the prefix -> (e.g. -> main)
• Function returns have the prefix <- (e.g. <- main)

Output:

• Return the call stack as a string with function names separated by -> that occurs most frequently
• If there’s a tie in frequency, return the call stack that achieves the top frequency first among those tied

Call Stack Definition:

• A call stack is the sequence of active function calls at any point in time
• For example, if main() calls handleEvents(), which calls handleClickEvent(), the call stack is main->handleEvents->handleClickEvent
• Returning from a function to a previous call stack does not create a new call stack for the purpose of counting occurrences

Example:

traces = [
  "-> main",
  "-> handleEvents",
  "-> handleClickEvent",
  "<- handleClickEvent",
  "-> handleClickEvent",
  "-> handleClickEvent",
  "<- handleClickEvent",
  "<- handleEvents",
  "<- main"
]

In the above example, the call stack main->handleEvents->handleClickEvent occurs twice, which is the most frequent.

这题要求根据函数调用与返回日志，统计每个“当前活跃调用栈”出现的次数，并返回出现最频繁的那个。解题时通常用一个栈维护当前路径：遇到 <code>-> function</code> 就入栈，遇到 <code><- function</code> 就出栈，然后把栈中从底到顶的函数名拼成 <code>a->b->c</code> 形式作为当前调用栈进行计数。关键点在于：只有真正形成的新调用栈才计入频次，函数返回回到之前的栈状态并不会算作新的一次。若存在并列，按照题目要求返回最先达到最高频次的调用栈。