Select Maximum Call Stacks Across Threads

Problem Statement

In a multi-threaded game engine, a profiling agent periodically samples call stacks from active worker threads to detect execution bottlenecks. Each sample records a thread_id and a list of frame strings representing the call stack from root to leaf (e.g., ["main", "tick", "physics"]).

Implement a StackProfiler class with the following methods:

• record_sample(thread_id: str, stack: list[str]) -> None: Records a sampled call stack for a given thread.
• get_top_overall() -> tuple[list[str], int] | None: Returns the most frequently sampled call stack across all threads and its sample count. Returns None if no samples have been recorded.
• get_top_per_thread() -> dict[str, tuple[list[str], int]]: Returns a mapping of each recorded thread_id to its most frequent call stack and sample count.

Tie-Breaking Rules

If two or more stacks have the same frequency, select the stack that is lexicographically smallest when comparing frames from root to leaf. For example, ["a", "b"] comes before ["a", "c"], and ["a"] comes before ["a", "b"].

Constraints

• 1 <= N <= 100,000 total calls to record_sample.
• 1 <= thread_id.length <= 32.
• 0 <= len(stack) <= 50. An empty list [] represents an idle thread stack and is a valid distinct stack.
• Frame names consist of ASCII alphanumeric characters and underscores, length 1 <= len(frame) <= 64.

Example

profiler = StackProfiler()
profiler.record_sample("worker-1", ["main", "physics"])
profiler.record_sample("worker-2", ["main", "render"])
profiler.record_sample("worker-1", ["main", "physics"])
profiler.record_sample("worker-2", ["main", "physics"])

# Overall counts:
# ["main", "physics"]: 3
# ["main", "render"]: 1
profiler.get_top_overall()
# Output: (["main", "physics"], 3)

# Per-thread:
# worker-1: ["main", "physics"] -> 2
# worker-2: ["main", "physics"] -> 1, ["main", "render"] -> 1 (tie broken lexicographically)
profiler.get_top_per_thread()
# Output:
# {
#   "worker-1": (["main", "physics"], 2),
#   "worker-2": (["main", "physics"], 1)
# }

Edge Cases

• Empty Call Stacks: Threads with empty stack lists [] must be tracked and treated like any other stack.
• Ties in Frequency: Equal counts must be broken deterministically using lexicographical comparison.
• No Samples: get_top_overall() must return None, and get_top_per_thread() must return an empty dictionary.