Given a two-column table where: the text content of both columns is known, the total table width is fixed, and the column divider can be placed at any position — find the optimal placement of the column divider that minimizes the total height (length) of the table.
Given a two-column table where: the text content of both columns is known, the total table width is fixed, and the column divider can be placed at any position — find the optimal placement of the column divider that minimizes the total height (length) of the table. The table height is determined by the taller of the two columns after text wrapping. Handle corner cases such as a single word whose length exceeds the available cell width.
What if a single word is longer than the cell width assigned to its column?
If multiple divider positions give the same minimum table height, how do you handle that?
How do you prove/justify the monotonicity or unimodal property needed for binary search to work here?
| Approach | Notes |
|---|---|
| Linear scan | Try every possible divider position and compute table height for each; O(W * (N1 + N2)) where W is total width and N1, N2 are text lengths. Simple to implement but slower than binary/ternary search. |
| Ternary search | Works cleanly on unimodal functions; slightly more intuitive than binary search when the monotonicity argument is not immediately obvious, but requires verifying the unimodal property. |
Common mistakes: Not finishing the code in time — one candidate reasoned through the full solution but ran out of time to implement it, which counted against them.; Missing or not explicitly handling the corner case where a single word is longer than the cell width, leaving the height function incorrect for those divider positions.
Interviewer hints: The interviewer guided like a peer rather than gatekeeping — described as 'peer-like' in steering the candidate toward the solution, suggesting they will nudge you if you're stuck.; The interviewer explicitly raised the 'multiple valid divider positions' follow-up as a direct question mid-discussion, not just as an afterthought.; Waymo coding rounds are described as strongly favoring binary search — if you can argue monotonicity, binary search is almost always the intended direction.
What passers do: Immediately framing the problem as a binary search on the divider position — recognizing monotonicity or unimodal shape of the height function — was the key insight interviewers were looking for.; Candidates who did well verbalized the solution approach (even without fully coding it) by reasoning about how shifting the divider trades height between the two columns, and identifying the optimal crossover point.