How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at SoFi.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at SoFi during technical interviews.

Format words into wrapped/justified lines

Q: Format words into wrapped/justified lines

This question evaluates practical programming skills in string processing, greedy packing, and careful handling of spacing and edge cases, and falls under the Coding & Algorithms domain.

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of words (strings with no spaces) and an integer `maxWidth`. Implement text formatting in two variants: ## Variant A — Basic word wrap (no padding) Return lines by packing words **greedily** from left to right: - Each line contains as many words as possible. - Words in a line are separated by **a single space**. - **Do not** pad the end of the line with extra spaces. ## Variant B — Full justification (fixed width) Return lines of **exactly** `maxWidth` characters: - Pack words greedily as in Variant A. - For every line **except the last**: - Distribute spaces between words so that the line length is exactly `maxWidth`. - If the spaces do not divide evenly, the **leftmost gaps** get more spaces. - If a line has only **one** word, left-justify it and pad trailing spaces to reach `maxWidth`. - For the **last** line: - Left-justify: words separated by a single space, then pad trailing spaces to reach `maxWidth`. ### Input - `words: List[str]` - `maxWidth: int` ### Output - `List[str]` lines formatted according to the chosen variant. ### Constraints (typical) - `1 <= len(words) <= 10^4` - `1 <= len(words[i]) <= maxWidth` - `1 <= maxWidth <= 100`

Quick Answer: This question evaluates practical programming skills in string processing, greedy packing, and careful handling of spacing and edge cases, and falls under the Coding & Algorithms domain.

Part 1: Greedy Word Wrap Without Padding

Given a list of words where each word contains no spaces, and an integer `maxWidth`, split the words into lines using greedy word wrap. Build each line from left to right, placing as many words as possible without making the line longer than `maxWidth`. Words in the same line must be separated by exactly one space. Do not add any trailing spaces to the end of a line. Return the list of produced lines. If the input list is empty, return an empty list.

Constraints

0 <= len(words) <= 10^4
1 <= len(words[i]) <= maxWidth <= 100
Each word consists of non-space characters only

Examples

Input: (["The", "quick", "brown", "fox", "jumps", "over", "the", "lazy", "dog"], 10)

Expected Output: ["The quick", "brown fox", "jumps over", "the lazy", "dog"]

Explanation: Each line greedily takes as many words as possible without exceeding width 10.

Input: (["a", "bc", "d", "ef"], 4)

Expected Output: ["a bc", "d ef"]

Explanation: Both lines fit exactly into width 4 with one space between words.

Input: (["hello"], 10)

Expected Output: ["hello"]

Explanation: Single-word input returns one line, with no trailing padding.

Input: (["a", "b", "c"], 1)

Expected Output: ["a", "b", "c"]

Explanation: With width 1, every word must appear on its own line.

Input: ([], 5)

Expected Output: []

Explanation: Empty input should produce no lines.

Hints

Track the total number of letters already in the current line. If you add another word, the number of required spaces is equal to the number of words already in that line.
When the next word no longer fits, finalize the current line with `' '.join(current_words)` and start a new one.

Part 2: Full Text Justification

Given a list of words where each word contains no spaces, and an integer `maxWidth`, format the text so every returned line has exactly `maxWidth` characters. Pack words greedily from left to right. For every line except the last, distribute spaces between adjacent words so the line reaches width `maxWidth`; if the spaces do not divide evenly, assign the extra spaces to the leftmost gaps. If a non-last line contains only one word, left-justify it and pad spaces on the right. The last line is always left-justified: words are separated by a single space, then padded with trailing spaces to reach `maxWidth`. If the input list is empty, return an empty list.

Constraints

0 <= len(words) <= 10^4
1 <= len(words[i]) <= maxWidth <= 100
Each word consists of non-space characters only

Examples

Input: (["This", "is", "an", "example", "of", "text", "justification."], 16)

Expected Output: ["This\x20\x20\x20\x20is\x20\x20\x20\x20an", "example\x20\x20of\x20text", "justification.\x20\x20"]

Explanation: The expected literal uses `\x20` to make spaces visible. Non-last lines distribute spaces evenly, and the last line is left-justified.

Input: (["What", "must", "be", "acknowledgment", "shall", "be"], 16)

Expected Output: ["What\x20\x20\x20must\x20\x20\x20be", "acknowledgment\x20\x20", "shall\x20be\x20\x20\x20\x20\x20\x20\x20\x20"]

Explanation: The first line gets 3 spaces in each gap, the second is a single-word non-last line padded on the right, and the final line is left-justified.

Input: (["hello"], 8)

Expected Output: ["hello\x20\x20\x20"]

Explanation: A single last line is left-justified and padded to length 8.

Input: (["a", "b", "c"], 1)

Expected Output: ["a", "b", "c"]

Explanation: Each line already has exact width 1, so no extra spaces are needed.

Input: ([], 5)

Expected Output: []

Explanation: Empty input should return an empty list.

Hints

First, greedily decide which words belong to each line. Then format that line separately.
For a non-last line with multiple words, let `total_spaces = maxWidth - total_letters`. Use `divmod(total_spaces, gaps)` to know the minimum spaces per gap and how many leftmost gaps get one extra space.

Quick Overview

This question evaluates practical programming skills in string processing, greedy packing, and careful handling of spacing and edge cases, and falls under the Coding & Algorithms domain.