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.
Constraints
- 0 <= len(articles) <= 100
- 1 <= max_width <= 200
- Each article contains at most 300 tokens
- Each token length is at most max_width
- Tokens are separated by spaces
- You may assume every non-empty article has at least one valid formatting
Examples
Input: (['lorem ipsum dolor', 'sit amet'], 11)
Expected Output: ['lorem ipsum', 'dolor', '----', 'sit amet']
Explanation: For the first article, both 'lorem ipsum' / 'dolor' and 'lorem' / 'ipsum dolor' are valid. Both have one one-word line, so the tie-breaker keeps the first line as long as possible.
Input: (['a , b c d'], 5)
Expected Output: ['a , b', 'c d']
Explanation: If the first line were just 'a', the next line would start with ',' which is invalid.
Input: (['a b c d'], 3)
Expected Output: ['a b', 'c d']
Explanation: This layout has zero one-word lines. Valid alternatives like 'a' / 'b c' / 'd' are worse.
Input: ([], 10)
Expected Output: []
Explanation: No articles means no output lines.
Hints
- Treat each article independently. A line is always a consecutive slice of tokens.
- Dynamic programming from the end of the token list works well for minimizing the number of one-word lines.
Part 2: Parse URL Query Parameters
Write a function that takes a URL string and returns its query parameters as a dictionary.
Rules:
- The query string begins after the first '?'.
- Parameters are separated by '&'.
- A parameter is usually in the form key=value.
- If a key appears without '=value', store that key with an empty string.
- If the URL has no query string, return an empty dictionary.
- If the same key appears multiple times, normal dictionary overwrite behavior is enough.
- Do not perform URL decoding; keep keys and values exactly as written.
Constraints
- 0 <= len(url) <= 100000
- The query string, if present, starts after the first '?'
- Parameters are separated by '&'
- Duplicate keys overwrite earlier values
- No URL decoding is required
Examples
Input: 'https://example.com/search?q=python&page=2'
Expected Output: {'q': 'python', 'page': '2'}
Explanation: The query string is 'q=python&page=2'.
Input: 'https://site.com/path?debug&mode=fast'
Expected Output: {'debug': '', 'mode': 'fast'}
Explanation: The parameter 'debug' has no explicit value, so it maps to an empty string.
Input: 'https://a.com?x=1&x=2&y'
Expected Output: {'x': '2', 'y': ''}
Explanation: The second 'x' overwrites the first one, and 'y' gets an empty string.
Input: 'https://example.com/home'
Expected Output: {}
Explanation: There is no '?' in the URL, so there is no query string.
Input: 'https://example.com?'
Expected Output: {}
Explanation: The URL has a '?' but the query string is empty.
Hints
- First isolate the substring after the first '?'. If there is no '?', the answer is empty.
- For each parameter, split on the first '=' only. If '=' is missing, use an empty string as the value.