Document Outline from Headings: Stack Interview Problem

Walk the headings in order, keeping a stack of the headings currently open. For each heading, pop until the top has a lower level number, attach the new node as that top's child, or at the root if the stack is empty, then push it. Each heading is pushed and popped at most once, so it is O(n).

mediumPattern: StackFrom Devana's Microsoft question set

Problem

A word processor shows a navigation pane built from the document's headings. You get them as a flat list of (level, title) pairs in document order, where level 1 is the top. Build the nested outline: each heading becomes a node with its level, its title and its children.

Real documents are messy. An H1 can be followed directly by an H3, and a document can start at H2 and contain an H1 later. Neither case may lose content.

def build_outline(headings: list[tuple[int, str]]) -> list[dict]:

This is one of Devana's own questions, written in the style of Microsoft's interviews. It is not a question leaked from Microsoft, and Devana is not affiliated with Microsoft.

Constraints

A heading nests under the nearest preceding heading with a lower level number.
Skipped levels still nest: an H3 straight after an H1 is that H1's child.
A heading with no lower-level heading before it sits at the root.
Siblings keep document order.
Each node is {"level": int, "title": str, "children": list}.

Examples

Example 1

Input:  [(1, "A"), (2, "B"), (3, "C"), (2, "D")]
Output: A > [B > [C], D]

C nests under B. D closes B's section, so it becomes B's sibling under A.

Example 2

Input:  [(2, "A"), (1, "B"), (3, "C")]
Output: [A, B > [C]] at the root

Nothing comes before A, so it is a root. B has a lower level number than A, so it cannot nest under it and becomes a second root. C skips level 2 and still nests under B.

Hints

Open one at a time, and try the problem again after each.

Hint 1

When you read a heading, which earlier headings could possibly be its parent?

Hint 2

Once a level 2 heading appears, can any later heading nest under an earlier level 3 heading?

Hint 3

Keep the chain of open headings on a stack. Pop everything at the same level or deeper; what is left on top is the parent.

Approach: from brute force to optimal

Brute force: scan backward for a parent

For each heading, walk back through the earlier ones until one has a lower level. That parent search is O(n) per heading.

Complexity: O(n²) time, O(n) space

A stack of open headings

The only possible parents are the headings still open: the path from the root down to the most recent heading. A new heading at level L closes every open heading at level L or deeper, so pop those, attach the new node to whatever is on top, and push it.

Every heading is pushed once and popped at most once, so the total work is linear however the levels jump around.

Complexity: O(n) time; O(n) for the output and O(depth) for the stack

How to say it in the interview

Say the observation that makes it a stack problem: "a new heading closes every open section at its level or deeper, and its parent is whatever is left on top." Then walk the skipped-level example out loud, since that is where the follow-up questions start.

Solution

Python

def build_outline(headings):
    roots, open_path = [], []          # open_path: the chain of open headings
    for level, title in headings:
        node = {"level": level, "title": title, "children": []}
        # A heading closes every open section at its level or deeper.
        while open_path and open_path[-1]["level"] >= level:
            open_path.pop()
        (open_path[-1]["children"] if open_path else roots).append(node)
        open_path.append(node)
    return roots

JavaScript

function buildOutline(headings) {
  const roots = [];
  const openPath = []; // the chain of open headings
  for (const [level, title] of headings) {
    const node = { level, title, children: [] };
    // A heading closes every open section at its level or deeper.
    while (openPath.length > 0 && openPath[openPath.length - 1].level >= level) openPath.pop();
    (openPath.length > 0 ? openPath[openPath.length - 1].children : roots).push(node);
    openPath.push(node);
  }
  return roots;
}

Both versions are tested against the same cases, including every example on this page.

The nodes on the stack are the same objects as in the tree, so appending a child to the top of the stack updates the outline directly.
>= matters: a second H2 has to close the first H2, not nest under it.

Follow-up questions

How do you handle a document that starts at level 3?

The rules already do: it becomes a root. If the pane should look tidy, indent by depth in the tree rather than by heading level.

How would you renumber headings to make the outline well formed?

Assign each node level = depth + 1 in a traversal of the tree you built. Offer the change to the author rather than rewriting the document silently.

How do you keep the outline stable while the user edits?

An edit to one heading only affects the outline from that heading to the next heading at its level or above. Rebuild that span, and keep stable node ids so the pane does not lose its scroll position or which sections are expanded.

What about a very long document?

The stack is bounded by the number of heading levels, so memory is essentially the output, and the single pass makes thousands of headings trivial.

Common mistakes

Popping with > instead of >=, which nests a heading under its own sibling.
Dropping or promoting headings after a skipped level instead of nesting them.
Assuming the first heading is level 1.
Finding parents by level arithmetic, such as "the parent is level minus one", which breaks as soon as a level is skipped.

Practice it in a mock interview

Reading a solution and explaining one under questioning are different skills. The button below starts this problem as a voice mock interview with Josh, Devana's AI interviewer, with an editor that runs your code.

Practice this problem in a mock interview

Validate Nesting in a Rich-Text Comment: Push each opening tag with its position; a closing tag must match the top of the stack.
Resolve Inherited Folder Permissions: Walk the folder tree from the root and keep the nearest explicit rule; invalidate only the subtree that changed.
Stack: the pattern guide, with more practice questions.