Find first 5-7-5 haiku in sentence
Company: Faire
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given a sentence containing mixed case and punctuation, and a syllable dictionary mapping lowercase words to their syllable counts, implement:
```
find_haiku(sentence: str, syllable_dict: dict) -> list[str] | None
```
Return the first contiguous three-line haiku whose three lines have 5, 7, and 5 syllables respectively, or `None` if no such haiku exists.
1. The three lines must be formed by partitioning a **single contiguous subsequence of words** into three consecutive segments that sum to 5, 7, and 5 syllables (in that order).
2. Treat tokens **case-insensitively** for dictionary lookups, and **strip leading/trailing punctuation** when matching keys.
3. When returning the three lines, **preserve each original token's casing and punctuation** (return the words exactly as they appeared in the sentence).
4. Aim for **O(N)** time (e.g., prefix sums + hashing) and state the space complexity.
5. Discuss edge cases such as: unknown words (not in the dictionary), apostrophes (e.g., `"don't"`), trailing punctuation, and multiple/irregular spaces.
Explain your approach and its time and space complexity.
Quick Answer: Find first 5-7-5 haiku in sentence evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given a `sentence` containing mixed case, punctuation, and possibly irregular spacing, plus a `syllable_dict` mapping lowercase (punctuation-stripped) words to their syllable counts, find the **first** contiguous three-line haiku.
A haiku is a single contiguous run of words (no unknown words inside) partitioned into three consecutive segments whose syllable sums are **5, 7, and 5** respectively, in that order.
Rules:
1. Lines are formed by splitting one contiguous subsequence of words into three consecutive segments summing to 5, 7, 5.
2. Look words up case-insensitively after stripping leading/trailing punctuation (keep interior apostrophes, e.g. `don't`).
3. In the returned lines, preserve each original token exactly (casing + punctuation), space-joined.
4. A word not in the dictionary is treated as a barrier that cannot be part of any line.
Return a list of three strings `[line1, line2, line3]`, or `None` if no haiku exists.
Target O(N) time and state the space complexity.
Constraints
- 0 <= number of words; sentence may be empty or whitespace-only.
- Syllable counts are positive integers; an absent word is an unknown barrier.
- Token normalization: lowercase, strip leading/trailing non-alphanumeric characters, keep interior apostrophes.
- Return the FIRST haiku in left-to-right scan order when several exist.
- Preserve original token casing and punctuation in the returned lines.
Examples
Input: ('An old pond a frog jumps in the water splashes the morning coding', {... syllable dict ...})
Expected Output: ['An old pond a frog', 'jumps in the water splashes', 'the morning coding']
Explanation: Line sums: 1+1+1+1+1=5, then 1+1+1+2+2=7, then 1+2+2=5. A clean 5-7-5 starting at the first token.
Input: ('code', {... syllable dict ...})
Expected Output: None
Explanation: A single one-syllable word can never reach the first line's 5-syllable target.
Hints
- Split on whitespace to get tokens, but normalize a copy of each token (lowercase + strip outer punctuation) only for dictionary lookups; keep the originals for output.
- Treat any word missing from the dictionary as a barrier: a haiku can never span across it.
- Because the line targets (5, 7, 5) are fixed, you can greedily walk forward from each start, accumulating syllables and bailing out the moment a running sum overshoots its target.
- Scan starts left to right and return on the first start index that yields all three exact line sums; this guarantees the first haiku.