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 eBay.

What role is this question designed for?

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

Format Words into Fixed-Width Lines

Q: Format Words into Fixed-Width Lines

This question evaluates proficiency in string manipulation, greedy line-packing algorithms, and attention to implementation details such as spacing distribution and edge-case handling.

Company: eBay

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an array of words and an integer `maxWidth`, arrange the words into lines so that each line has exactly `maxWidth` characters. Rules: 1. Put words into each line greedily: each line should contain as many words as possible without exceeding `maxWidth` when separated by at least one space. 2. For every line except the last line: - If the line contains more than one word, distribute spaces between words so the line length is exactly `maxWidth`. - Spaces should be distributed as evenly as possible. - If the spaces cannot be divided evenly, the leftmost gaps should receive more spaces than the rightmost gaps. - If the line contains only one word, left-align it and pad the remaining characters with spaces on the right. 3. For the last line, left-align the words using a single space between adjacent words, then pad the remaining characters with spaces on the right. Return the formatted lines as an array of strings. Example: ```text Input: words = ["This", "is", "an", "example", "of", "word", "formatting"] maxWidth = 16 Output: [ "This is an", "example of word", "formatting " ] ``` Constraints: - `1 <= words.length <= 300` - `1 <= words[i].length <= 20` - `words[i]` contains only English letters and symbols without spaces. - `1 <= maxWidth <= 100` - Every word has length at most `maxWidth`.

Quick Answer: This question evaluates proficiency in string manipulation, greedy line-packing algorithms, and attention to implementation details such as spacing distribution and edge-case handling.

Given a list of words and an integer maxWidth, format the words into lines so that each returned string has exactly maxWidth characters. Build each line greedily by placing as many words as possible without exceeding maxWidth when using at least one space between adjacent words. Formatting rules: 1. For every line except the last line: - If the line has more than one word, distribute spaces between words so the line length becomes exactly maxWidth. - Spaces must be as evenly distributed as possible. - If the spaces do not divide evenly, the leftmost gaps get one extra space before the rightmost gaps. - If the line has only one word, left-align it and pad the rest with spaces on the right. 2. For the last line: - Left-align the words with a single space between each pair of adjacent words. - Pad the remaining spaces on the right. Return the formatted lines as a list of strings.

Constraints

1 <= len(words) <= 300
1 <= len(words[i]) <= 20
words[i] contains no spaces
1 <= maxWidth <= 100
Every word length is at most maxWidth

Examples

Input: (["This", "is", "an", "example", "of", "word", "formatting"], 16)

Expected Output: ["This is an", "example of word", "formatting "]

Explanation: The first two lines are fully justified, and the last line is left-aligned and padded on the right.

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

Expected Output: ["What must be", "acknowledgment ", "shall be "]

Explanation: The second line contains only one word, so it is left-aligned with trailing spaces.

Input: (["Science", "is", "what", "we", "understand", "well"], 20)

Expected Output: ["Science is what we", "understand well "]

Explanation: The first line needs 5 spaces across 3 gaps, so the leftmost two gaps get 2 spaces and the last gap gets 1.

Input: (["Hello"], 10)

Expected Output: ["Hello "]

Explanation: A single last-line word is left-aligned and padded with spaces to width 10.

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

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

Explanation: With maxWidth = 1, each line can contain only one character, so each word forms its own line.

Hints

First decide which words belong to the current line using a greedy scan, then format that line.
For a non-last line with k gaps and s spaces to place, each gap gets s // k spaces, and the first s % k gaps get one extra space.

Quick Overview

This question evaluates proficiency in string manipulation, greedy line-packing algorithms, and attention to implementation details such as spacing distribution and edge-case handling.