Interiew Question: Build a Table Of Contents

Like many stories, this one starts with me bombing a tech interview. Years ago I had a live coding challenge with some company I don't remember now, but I won't forget how anxious and embarrassed I felt as I found myself unable to solve the problem. The truth is that I often don't see the right solution to basic algorithm problems right away. It can really take time to marinate before I have my "aha" moment!

Sometimes, I obsess for some number of days after the interview and eventually solve the problem. This is actually not one of those cases 😂 but I ran into the problem again recently and figured it out. Slowly. We're talking about an entire day of my life. Maybe I'm not a great programmer but it seems unfair that so many tech interviewers expect us to solve things like this in just one hour.

Dear reader, please note that I did not have to solve this problem. It was already solved for me with a plugin. But when I recognized it as the same problem that I'd encountered in that awful interview so long ago, I wanted to solve it, mainly to prove that I could, but also with an aim of sharing it here, because I take great joy in being a spoiler for interviewers with unfair expectations. If you ever find yourself facing an interview question like this one, I hope this post leaves you better prepared.

The Challenge

In this problem, we're given an ordered list of headings that we must convert to a tree that can be used as a Table Of Contents (TOC) like the one that appears on the right side of this page when the screen is wide. For instance, say you have a list of heading tags in the order that they appear on a page.

const orderedHeadings = [
  "h1",
  "h2",
  "h2",
  "h3",
  "h4",
  "h2",
];

Given the above list, you want to transform it into a TOC (Table Of Contents) with a structure that looks more like this:

return [
  {
    tag: "h1",
    children: [
      {
        tag: "h2",
        children: [],
      },
      {
        tag: "h2",
        children: [
          {
            tag: "h3",
            children: [
              {
                tag: "h4",
                children: [],
              },
            ],
          },
        ],
      },
      {
        tag: "h2",
        children: [],
      },
    ],
  },
];

Maybe you're a much stronger programmer than I am and you already recognize a fairly simple solution to this. You might also recognize that, for content authored using mdx, there are already plugins for that. But of course, that would be cheating for this challenge. So, how do we solve this by hand?

Solution

My big developer brain often leads me to believe that there's a recursive, immutable solution for everything involving list transformations. And maybe there is, but I didn't find one in this case. I spent a whole lot of time trying, especially considering that I already had a TOC after integrating a mdx plugin. So when I got a loop-and-mutate solution working, I called it a day.

What I eventually figured out is that for any given heading in the list, it's easy to look through the rest of the list and figure out what its parent should be, or if it shouldn't have a parent at all. If you find a parent, then you can add the node to the parent's children. That's... basically it.

Examples

Consider headings appearing on a page in this order.

0 - h1
1 - h2
2 - h2
3 - h3
4 - h4
5 - h4
6 - h3
7 - h2

What is the parent node of item at index 7? It's an h2, so we only need to look backwards through the list until we find an h1, which happens to be the first item in the list.

What about the parent of the item at index 5? It's an h4, and a sibling to the h4 located at index 4. Both of these share the same h3 parent located at index 3.

The first item in the list has no parent. Of course we know that an h1 is a top level heading, but what if we didn't have any h1 tags in our list?

0 - h2
1 - h2
2 - h3

If we examine the item at index 1, we have to conclude that it's a top level heading, because when we search backwards through the list, we won't find an element with a lower heading number. This example has two top level nodes, and the h3 at index 2 is a child of the h2 at index 1.

Find the parent

Now that the problem is more clear, let's write code that will loop through and identify the parent. Instead of an array of strings like h1, and h2, we'll have objects with a level property and the text that the heading displays. We won't enforce proper heading semantics, e.g. our code won't care if an h5 comes after an h3. We'll leave that up to the author of the content.

interface ContentHeading {
  level: item.level;
  text: item.text;
}
 
export function structure(list: Array<ContentHeading>) {
  // Loop backwards through the list
  for (let i = list.length - 1; i > -1; i--) {
    const item = list[i];
    let j = i - 1;
    let prev = list.at(j);
    let parent = null;
 
    // Start looking through the previous items. Keep going until
    // you find an item with a lower level than the current item.
    if (prev && item.level > prev.level) {
      parent = prev;
    } else {
      while (prev && item.level <= prev.level) {
        prev = list.at(--j);
      }
 
      if (prev) {
        parent = prev;
      }
    }
  }
}

This code will find the parent for each item, but won't do anything with that information. Let's finish this up by adding children to parents and returning top level nodes.

Restructuring the list

interface StructuredHeading extends ContentHeading {
  children: Array<StructuredHeading>;
}
 
export function structure(
  unstructuredList: Array<ContentHeading>
): Array<StructuredHeading> {
  const items = [];
  const list: Array<StructuredHeading> =
    unstructuredList.map((item) => ({
      level: item.level,
      text: item.text,
      children: [],
    }));
 
  for (let i = list.length - 1; i > -1; i--) {
    const item = list[i];
    let j = i - 1;
    let prev = list.at(j);
    let parent = null;
 
    if (prev && item.level > prev.level) {
      parent = prev;
    } else {
      while (prev && item.level <= prev.level) {
        prev = list.at(--j);
      }
 
      if (prev) {
        parent = prev;
      }
    }
 
    if (parent) {
      parent.children.unshift(item);
    } else {
      items.unshift(item);
    }
  }
 
  return items;
}

And that's really it! We've restructured the list just how we want it, so the next logical step is to display it.

Render the list

Now that we have a tree structure, recursive logic feels a bit more obvious, especially if we're using a component model to build our UI. Here's an example using Qwik 👇

export function RenderStructuredList(props: {
  list: Array<StructuredHeading>;
}) {
  if (props.list.length === 0) {
    return null;
  }
 
  return (
    <ol>
      {props.list.map((item, index) => {
        return (
          <li key={index}>
            {item.text}
            <RenderStructuredList list={item.children} />
          </li>
        );
      })}
    </ol>
  );
}

That's really all it takes: a nested loop and a recursive component. You can see this all together in the main layout file for this website. It seems simple in hindsight, and I think that good solutions to these problems usually are simple in the sense that they lack complexity. But that doesn't necessarily mean they are easy to find!

There's a plugin for that!

To be sure, the simplest way by far to add a TOC to my blog posts was to use the rehype-toc plugin. If you haven't used rehype plugins, I strongly recommend trying it. Any transformation that you might imagine making to your mdx output is either covered by an existing plugin or possible by writing your own. This website uses one such custom plugin to add a copy-to-clipboard button to the code snippets in the blog posts.

The TOC plugin exposes options that allow you to customize the output however you like. I had this plugin integrated early on in the development of my blog, but as I was reading through Qwik docs I learned about the useContent hook, which returns the ordered list of headings. It was then that I recognized the same problem that I'd been challenged with at an interview years prior. One advantage of using the data provided by Qwik is the flexibility to put the TOC anywhere I want on the page, and more direct control over what actually gets rendered.

Conclusion

I like writing about interview questions that I've found challenging. I think it helps prepare me for future interviews, and I hope it helps prepare readers similarly. With any luck, you'll come across a question like this in the future and remember how to solve it. Here are some key takeaways for me:

• Don't be afraid to just mutate stuff in a loop. You don't need to seek a recursive solution just because you suspect there is one. Find the most straightforward way to solve the problem, and maybe you'll find a way to generalize it into an elegant recursive expression later on (or maybe not, and that's ok).
• Start with the first thing you can deduce and build from there. In this case, realizing that you can identify any item's parent by moving backward through the list is key to solving the problem.
• Even if you've done this professionally for 14 years and did pretty darn well back in school, you might not see correct solutions to simple algorithm problems right away. Try not fo feel bad about it.
• The rehype ecosystem is awesome and you should leverage it as much as possible. Don't be like me, please. Spare yourself. But also, no regrets.
• Loops are great, btw.