InterviewDB
Question
Comment Tree: Build and Traverse a Nested Comment Thread Like Reddit's
phone
Question Details
Problem
Given a flat list of comment objects (each with an id and optional parent_id), reconstruct the nested tree structure and implement depth-first traversal for rendering.
python
from dataclasses import dataclass, field
from typing import Optional
@dataclass
class Comment:
id: int
author: str
body: str
parent_id: Optional[int]
children: list['Comment'] = field(default_factory=list)
def build_tree(comments: list[Comment]) -> list[Comment]:
**Returns** list of root-level comments with children populated
pass
def render_thread(roots: list[Comment], indent: int = 0) -> str:
pass
Example:
comments = [
Comment(1, "alice", "First!", None),
Comment(2, "bob", "Reply to first", 1),
Comment(3, "carol", "Reply to bob", 2),
]
build_tree(comments) -> [Comment(1, children=[Comment(2, children=[Comment(3)])])]
Follow-ups
- What data structure makes
build_treerun in O(n) rather than O(n^2)? - How would you handle orphaned comments (parent_id points to a non-existent comment)?
- How would you sort children by score (upvotes - downvotes) at each level?
- How would you implement lazy loading so deep sub-threads are only fetched on expand?
Full Details
Problem
Given a flat list of comment objects (each with an id and optional parent_id), reconstruct the nested tree structure and implement depth-first traversal for rendering.
python
from dataclasses import dataclass, field
from typing import Optional
@dataclass
class Comment:
id: int
author: str
body: str
parent_id: Optional[int]
children: list['Comment'] = field(default_factory=list)
def build_tree(comments: list[Comment]) -> list[Comment]:
**Returns** list of root-level comments with children populated
pass
def render_thread(roots: list[Comment], indent: int = 0) -> str:
pass
Example:
comments = [
Comment(1, "alice", "First!", None),
Comment(2, "bob", "Reply to first", 1),
Comment(3, "carol", "Reply to bob", 2),
]
build_tree(comments) -> [Comment(1, children=[Comment(2, children=[Comment(3)])])]
Follow-ups
- What data structure makes
build_treerun in O(n) rather than O(n^2)? - How would you handle orphaned comments (parent_id points to a non-existent comment)?
- How would you sort children by score (upvotes - downvotes) at each level?
- How would you implement lazy loading so deep sub-threads are only fetched on expand?
Free preview. Unlock all Nextdoor questions →
About This Question
This is a reported interview question from a nextdoor interview during the phone round.