Implement Text Layout and Query Parsing
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
This interview note described two coding tasks.
1. **Format multiple articles into lines**
Write a function that takes:
- `articles`: a list of article strings
- `max_width`: a positive integer
Return a list of output lines that formats each article according to these rules:
- Break each article into multiple lines so that no line exceeds `max_width` characters.
- Words must remain whole; do not split a word across lines.
- No line may begin with punctuation. Assume punctuation tokens may appear separately, and a valid layout must keep punctuation from becoming the first token on a line.
- When multiple valid layouts exist, prefer a layout that avoids leaving a line with only one word if it can be improved without violating the width or punctuation rules.
- Insert a separator line `----` between consecutive articles.
You may assume words and punctuation tokens are separated by spaces in the input.
2. **Parse URL query parameters**
Write a function that takes a URL string and returns its query parameters as a key-value dictionary.
Rules:
- The query string begins after the first `?`.
- Parameters are separated by `&`.
- Each parameter is normally in the form `key=value`.
- If a key appears without `=value`, store that key with an empty string as its value.
- If the URL has no query string, return an empty dictionary.
- You may assume duplicate keys do not need special handling beyond the language's normal dictionary overwrite behavior unless otherwise specified.
Quick Answer: This question evaluates string-processing and parsing competencies, covering tokenization, constrained line-wrapping and layout decisions (including punctuation placement and avoidance of single-word lines) as well as extraction of URL query parameters into key-value mappings and handling of missing values.
Part 1: Format Multiple Articles Into Lines
You are given a list of article strings and a positive integer max_width. Each article is a sequence of space-separated tokens. A token can be a word or a punctuation token.
Format each article into output lines using these rules:
- Preserve token order.
- Each output line is made from one or more consecutive tokens joined by a single space.
- No line may exceed max_width characters.
- No line may begin with punctuation.
- Insert the separator line '----' between consecutive articles.
A punctuation token is any token made entirely of non-alphanumeric characters.
If multiple valid layouts exist for the same article, choose one that minimizes the number of lines containing exactly one word token. Punctuation tokens on that line do not increase the word count. If there is still a tie, choose the layout that makes each line as long as possible from left to right.
Return the final list of output lines.