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

What role is this question designed for?

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

Find first 5-7-5 haiku in sentence | Faire Coding Question

Quick Overview

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.

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.

Input: ('', {... syllable dict ...})

Expected Output: None

Explanation: Empty sentence yields no tokens, so no haiku exists.

Input: ('Hello, An old pond, a frog jumps in the water splashes! the morning coding done', {... syllable dict ...})

Expected Output: ['An old pond, a frog', 'jumps in the water splashes!', 'the morning coding']

Explanation: 'Hello,' is an unknown barrier so the haiku starts at 'An'. Lookups strip the punctuation ('pond,' -> 'pond', 'splashes!' -> 'splashes') but the returned lines keep the original tokens verbatim.

Input: ('An old QUUX pond a frog jumps in the water splashes the morning coding', {... syllable dict ...})

Expected Output: None

Explanation: 'QUUX' is unknown, acting as a barrier inside what would otherwise be a haiku run, so no contiguous 5-7-5 partition is possible.

Input: ("don't go slow we win i love to code all day and see it run fast now", {... syllable dict ...})

Expected Output: ["don't go slow we win", 'i love to code all day and', 'see it run fast now']

Explanation: The apostrophe word 'don't' is looked up directly (interior apostrophe preserved) and counts as 1 syllable; the first valid 5-7-5 run is returned.

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.

Quick Overview