Katkat
Back

Count substrings and generate TOC

J.P. MorganSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates string processing, pattern recognition, and parsing competencies—covering counting and grouping in binary substrings and structured line parsing and numbering for a table of contents—within the Coding & Algorithms domain.

Solve the following two coding problems.

  1. Count valid binary substrings

Given a string s consisting only of '0' and '1', count how many substrings satisfy both conditions:

  • The substring contains the same number of 0s and 1s.
  • All 0s in the substring are contiguous, and all 1s in the substring are contiguous.

In other words, a valid substring must consist of exactly two consecutive groups, such as "0011", "1100", "01", or "10".

Return the total number of valid substrings.

  1. Generate a table of contents

You are given an array of strings lines, where each element represents one line in a document. Build a table of contents using the following rules:

  • A line starting with "##" is a section and belongs to the most recent chapter.
  • Otherwise, a line starting with "#" is a chapter.
  • All other lines should be ignored.

Number chapters and sections in the order they appear:

  • A chapter should be output as "<chapter_number>. <title>"
  • A section should be output as "<chapter_number>.<section_number>. <title>"

When a new chapter appears, its section numbering starts again from 1.

Return the generated table of contents as an array of strings.