Parse and Reconstruct Stack Trace

Q: Parse and Reconstruct Stack Trace

This question evaluates parsing and string-processing skills, hierarchical data structure design for call-tree reconstruction, exception trace analysis, and algorithmic complexity reasoning for robust log handling.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Anthropic.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Anthropic during technical interviews.

Question

Given a multi-line stack trace string from a single thread (e.g., each frame is in the form 'at Module::Function(file:line)'), design and implement a parser that:
(
1) extracts the ordered list of frames from most recent to oldest;
(
2) reconstructs the call hierarchy as a tree; and
(
3) identifies the deepest frame associated with the thrown exception. The parser must correctly handle nested causes (e.g., 'Caused by:' sections), abbreviated repeated frames (e.g., '... N more'), and missing or malformed lines. Describe your data structures, time/space complexity, and provide working code for parse and reconstruction.

PracHub · Accepted Answer

def solution(trace): def parse_frame(line): stripped = line.strip() if not stripped.startswith('at '): return None body = stripped[3:].strip() if not body.endswith(')'): return None open_paren = body.rfind('(') colon = body.rfind(':') if open_paren == -1 or colon == -1 or colon < open_paren or colon >= len(body) - 1: return None line_no = body[colon + 1:-1] if not line_no.isdigit() or not body[:open_paren]: return None return body if not trace: return [] frames = [] for line in trace.splitlines(): if line.strip().startswith('Caused by:'): break frame = parse_frame(line) if frame is not None: frames.append(frame) return frames def solution(trace): def parse_frame(line): stripped = line.strip() if not stripped.startswith('at '): return None body = stripped[3:].strip() if not body.endswith(')'): return None open_paren = body.rfind('(') colon = body.rfind(':') if open_paren == -1 or colon == -1 or colon < open_paren or colon >= len(body) - 1: return None line_no = body[colon + 1:-1] if not line_no.isdigit() or not body[:open_paren]: return None return body def parse_more(line): stripped = line.strip() if not stripped.startswith('... ') or not stripped.endswith(' more'): return None middle = stripped[4:-5].strip() if not middle.isdigit(): return None return int(middle) if not trace: return {} sections = [] current = {'frames': [], 'omitted': 0} for line in trace.splitlines(): if line.strip().startswith('Caused by:'): sections.append(current) current = {'frames': [], 'omitted': 0} continue frame = parse_frame(line) if frame is not None: current['frames'].append(frame) continue omitted = parse_more(line) if omitted is not None: current['omitted'] = omitted sections.append(current) full_sections = [] for i, section in enumerate(sections): frames = list(section['frames']) omitted = section['omitted'] if omitted > 0 and i > 0: parent = full_sections[i - 1] k = min(omitted, len(parent)) if k > 0: frames.extend(parent[-k:]) full_sections.append(frames) forest = {} for frames in full_sections: if not frames: continue node = forest for frame in reversed(frames): if frame not in node: node[frame] = {} node = node[frame] return forest def solution(trace): def parse_frame(line): stripped = line.strip() if not stripped.startswith('at '): return None body = stripped[3:].strip() if not body.endswith(')'): return None open_paren = body.rfind('(') colon = body.rfind(':') if open_paren == -1 or colon == -1 or colon < open_paren or colon >= len(body) - 1: return None line_no = body[colon + 1:-1] if not line_no.isdigit() or not body[:open_paren]: return None return body def parse_more(line): stripped = line.strip() if not stripped.startswith('... ') or not stripped.endswith(' more'): return None middle = stripped[4:-5].strip() if not middle.isdigit(): return None return int(middle) if not trace: return None sections = [] current = {'frames': [], 'omitted': 0} for line in trace.splitlines(): if line.strip().startswith('Caused by:'): sections.append(current) current = {'fram

Quick Overview

Solution

Hints

Part 2: Reconstruct a Merged Call Hierarchy Tree

Constraints

Examples

Solution

Hints

Part 3: Find the Deepest Frame of the Thrown Exception

Constraints

Examples

Solution

Hints

Quick Overview