This is an Interactive coding problem where you need to find the largest possible font size that allows a sentence to fit within a given screen's width and height. You are given a list of available font sizes (sorted) and an API FontInfo that provides the width of a character and the height of the font for a specific size.
Google asks this to test a candidate's ability to apply Binary Search in a practical, UI-related context. It's an optimization problem on a sorted range. The 'interactive' part (using an API) mimics real-world development where you often interact with black-box libraries to get metadata. It also tests if you can correctly implement the logic to check if a sentence fits (summing character widths vs. screen width).
This follows the Binary Search on Answer interview pattern. Since the font sizes are sorted and the 'fit' property is monotonic (if font size X fits, all sizes smaller than X also fit), you can binary search for the maximum size. For each mid-point font size, you check if the font height is within screen height and if the total width of all characters in the sentence is within screen width.
Sentence: "Hi", Width: 20, Height: 10, Fonts: [8, 10, 12, 14, 16]
One mistake is not checking the height constraint, focusing only on the width. Another is calculating the sentence width inefficiently (e.g., calling the API in a nested loop for every check). Some candidates also struggle with the binary search boundaries, potentially missing the largest valid font or returning an invalid one.
Binary Search isn't just for finding a number in a list; it's for any scenario where you have a sorted range of possible answers and a way to verify if a specific answer works. Always look for this 'monotonic' property when asked for a 'maximum' or 'minimum' possible value.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Number of Equal Numbers Blocks | Medium | Solve | |
| Search in a Sorted Array of Unknown Size | Medium | Solve | |
| Find the Index of the Large Integer | Medium | Solve | |
| Find in Mountain Array | Hard | Solve | |
| Plates Between Candles | Medium | Solve |
