0

Text box formatter

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Text box formatter

Companies: Airbnb

Difficulty: Medium

Problem statement

Implement format_boxes(sentences: list[str]) -> list[str].

Each sentence is a non-empty string of printable ASCII characters and spaces. Draw every sentence in its own ASCII box and return the drawing as a list of lines.

Rules:

  • All boxes have the same inner width: the length of the longest sentence.
  • A border line is +, then width + 2 dashes, then +.
  • A text row is | , the sentence left-aligned, spaces up to width, then |.
  • Boxes are stacked top to bottom in input order. Neighbouring boxes share one border line, so n sentences produce 2n + 1 lines.
  • Copy each sentence exactly, including any inner spaces.

Example

sentences = ["Hi there", "A longer one", "Ok"]

+--------------+
| Hi there     |
+--------------+
| A longer one |
+--------------+
| Ok           |
+--------------+

Part 2. Add format_wrapped_boxes(sentences, max_width, mode). The inner width is now min(longest sentence, max_width). Wrap each sentence greedily onto as many rows of its box as needed, with one space between words; cut a word longer than the width into width-sized pieces. Align each row by mode: left, right, center, or justify (spread spaces evenly, extra spaces go to the leftmost gaps, and the last row of each sentence stays left-aligned).

sentences = ["the quick brown fox jumps", "hello"], max_width = 10, mode = "justify"

+------------+
| the  quick |
| brown  fox |
| jumps      |
+------------+
| hello      |
+------------+

Constraints: up to 10^4 sentences, each up to 10^3 characters; max_width >= 1.

Approach

Part 1 is a two-pass layout problem. Every box has the same inner width, and that width depends on every sentence. So you cannot print the first box until you have seen the last sentence. First pass: width = max(len(s)). Second pass: emit the boxes.

Fix the format before coding. Say the layout out loud and confirm it with the interviewer. This solution uses one space of padding on each side of the text:

  • a border line is +, then width + 2 dashes, then +;
  • a text row is | , the sentence, enough spaces to reach width, then |;
  • boxes are stacked and neighbours share one border line, so n sentences give 2n + 1 lines.

Every output line then has the same length, width + 4. That is the invariant to check in your tests. Most bugs here are off-by-one errors in padding, so put the border and the row in two tiny helpers and reuse them.

There is no brute force to beat. Part 1 is linear. The interview is about clean code, exact output, and how well the code takes the next part.

Part 2 adds a maximum width. Now a sentence longer than max_width must wrap onto several rows of the same box. This is where the LeetCode "Text Justification" ideas come in:

  1. The inner width becomes min(longest sentence, max_width). Short input keeps the Part 1 layout. Long input fills the full width.
  2. Wrap each sentence greedily: put as many words on a line as fit, with one space between words. Greedy is optimal for the number of lines, because pulling a word to the next line can never help a later line fit.
  3. A word longer than the width cannot fit anywhere. Cut it into width-sized pieces (agree this rule with the interviewer; the other choice is to raise an error).
  4. Align each line: left (pad right), right (pad left), center (split the slack, extra space on the right), or full justify.

Full justification. For a line with k words and s spaces to place, there are k - 1 gaps. Each gap gets s // (k - 1) spaces, and the first s % (k - 1) gaps get one more. A line with one word is left-aligned. The last line of each sentence is left-aligned, as in normal typesetting.

Keep layout and rendering apart. wrap decides which words go on which line. align_line turns one line into a string of exactly width characters. row and border draw the box. Each later follow-up changes only one of these.

Code

from typing import List


def border(width: int) -> str:
    return "+" + "-" * (width + 2) + "+"


def row(text: str, width: int) -> str:
    return "| " + text + " " * (width - len(text)) + " |"


def format_boxes(sentences: List[str]) -> List[str]:
    """Part 1: one box per sentence, stacked, sharing border lines."""
    width = max((len(s) for s in sentences), default=0)
    out = [border(width)]
    for s in sentences:
        out.append(row(s, width))
        out.append(border(width))
    return out


def wrap(sentence: str, width: int) -> List[List[str]]:
    """Greedy word wrap. Words longer than width are cut into pieces."""
    lines: List[List[str]] = []
    cur: List[str] = []
    cur_len = 0  # letters plus one space between words
    for word in sentence.split():
        pieces = [word[i:i + width] for i in range(0, len(word), width)]
        for piece in pieces:
            need = len(piece) if not cur else cur_len + 1 + len(piece)
            if need > width:
                lines.append(cur)
                cur, need = [], len(piece)
            cur.append(piece)
            cur_len = need
    if cur or not lines:
        lines.append(cur)
    return lines


def justify(words: List[str], width: int) -> str:
    """Spread spaces evenly; leftmost gaps take the extra ones."""
    if len(words) == 1:
        return words[0]
    gaps = len(words) - 1
    spaces = width - sum(len(w) for w in words)
    base, extra = divmod(spaces, gaps)
    parts = []
    for i, w in enumerate(words[:-1]):
        parts.append(w + " " * (base + (1 if i < extra else 0)))
    parts.append(words[-1])
    return "".join(parts)


def align_line(words: List[str], width: int, mode: str, last: bool) -> str:
    text = " ".join(words)
    if mode == "left" or (mode == "justify" and last):
        return text
    if mode == "right":
        return " " * (width - len(text)) + text
    if mode == "center":
        return " " * ((width - len(text)) // 2) + text
    if mode == "justify":
        return justify(words, width)
    raise ValueError(f"unknown alignment: {mode}")


def format_wrapped_boxes(
    sentences: List[str], max_width: int, mode: str = "left"
) -> List[str]:
    """Part 2+: wrap each sentence to max_width, then align inside the box.

    Inner width = min(longest sentence, max_width), so short input keeps
    the Part 1 layout and long input fills the full max_width.
    """
    if max_width < 1:
        raise ValueError("max_width must be positive")
    width = min(max((len(s) for s in sentences), default=1), max_width)
    width = max(width, 1)  # wrap() needs a positive width
    out = [border(width)]
    for lines in (wrap(s, width) for s in sentences):
        for i, words in enumerate(lines):
            text = align_line(words, width, mode, last=i == len(lines) - 1)
            out.append(row(text, width))
        out.append(border(width))
    return out

Complexity

Let n be the number of sentences and L the total number of characters.

  • Part 1: O(L) time to find the width and copy the text. The output has 2n + 1 lines of width + 4 characters, so output space is O(n · width). Extra working space is O(1).
  • Part 2: wrapping looks at each word once and each character a constant number of times, so O(L) time. Cutting long words and aligning lines is linear in the line lengths. Output is O(R · width), where R is the total number of rows. Extra space is O(longest sentence) for the current sentence's lines.

Test cases

  • ["Hi there", "A longer one", "Ok"] gives width 12:
    +--------------+, | Hi there |, +--------------+, | A longer one |, +--------------+, | Ok |, +--------------+.
  • One sentence ["x"] gives ["+---+", "| x |", "+---+"].
  • All sentences the same length: no padding on any row.
  • Sentences with inner spaces such as "a b" are copied as they are in Part 1; the length counts the spaces.
  • Empty list: a single border "+--+" (or an empty list; agree with the interviewer).
  • Part 2, ["the quick brown fox jumps", "hello"], max_width = 10, justify:
    | the quick |, | brown fox |, | jumps | in the first box and | hello | in the second. The last line of each sentence stays left-aligned.
  • Part 2, a word longer than the width: ["abcdefghij"], max_width = 4 gives rows | abcd |, | efgh |, | ij |.
  • Part 2, right alignment: ["ab cd"], max_width = 20 gives width 5 and the row | ab cd |.
  • Part 2, center: ["ab", "abcd"] gives | ab | for the short sentence.
  • Part 2 with max_width at least the longest sentence and left alignment gives the same output as Part 1.
  • Property: every line of every output has length width + 4.

Follow-ups

  1. Maximum width with word wrap. Covered by format_wrapped_boxes. The key choices are greedy wrapping, what to do with a word longer than the width, and whether the box shrinks to the longest wrapped line or uses min(longest, max_width).
  2. Alignment modes (left, right, center, justify). Covered by align_line. Ask how centering breaks ties (extra space left or right) and whether the last line of a justified paragraph is left-aligned. Only the per-line function changes.
  3. Separate boxes instead of shared borders, or boxes side by side. Separate boxes: emit border, rows, border per sentence. Side by side: build each box as a list of rows, pad shorter boxes with blank rows to the tallest, then join row i of every box. This is easy only if rendering a box returns a list of rows instead of printing.
  4. Table with several columns. Each row is a list of cells. Compute a width per column (max over that column), draw borders as + plus dashes per column, and wrap each cell to its column width. A row's height is the tallest cell; pad the others. This is the same code with the width moved from one number to a list.
  5. Streaming or very large input. Part 1 needs the width before the first line, so it needs two passes: read the file once for the max length, then again to print. If the width is given up front (Part 2), you can print each box as soon as its sentence arrives, with O(longest sentence) memory. Unicode text needs display width (for example East Asian wide characters count as 2), not len.

Interviewer expectations

Mid-level (L4)

  • States the exact border and row format before writing code, and gets the padding right on the first or second try.
  • Computes the width in a first pass and produces lines of equal length.
  • Tests one sentence, equal lengths, and the empty list.

Senior (L5)

  • Splits the code into helpers (border, row, wrap, align) so Part 2 is an extension, not a rewrite.
  • Implements greedy wrap and full justification with the even-gap rule, and handles a word longer than the width and the last line.
  • Uses the "every line has length width + 4" invariant as a test, and asks about ambiguous rules (empty input, tie-breaking when centering).

Staff (L6+)

  • Separates layout from rendering so side-by-side boxes, multi-column tables, and new alignments change one function each.
  • Discusses two-pass versus streaming, memory for large input, and display width for non-ASCII text.
  • Knows greedy wrap minimises line count but not raggedness, and can explain the dynamic-programming (Knuth-Plass style) alternative that minimises the sum of squared slack, with its O(n²) cost.

Sign in to comment, vote or remix.