Google Interview Question
Dev LeadsCountry: United States
Interview Type: In-Person
function magicFunction (char, font) {
return font.getDimensions(char)
}
var fonts = [/* font1, font2, font3, .... */]
module.exports = function (s, screenWidth, screenHeight) {
// Assume fonts are sorted largest to smallest...
for (var i = 0; i < fonts.length; ++i) {
var font = fonts[i]
var screenRemainingHeight = screenHeight
var screenRemainingWidth = screenWidth
var maxCharacterHeightLine = 0
var lineWidth = 0
for (var j = 0; j < s.length; ) {
var char = s[j]
var d = magicFunction(char, font)
if (d.height <= screenRemainingHeight) {
maxCharacterHeightLine = max(maxCharacterHeightLine, d.height)
lineWidth += d.width
if (lineWidth > screenRemainingWidth) {
// Start a new line
// don't increment j
lineWidth = 0
screenRemainingHeight -= maxCharacterHeightLine
} else {
// it fits on this line, get next character in `s`
++j
}
} else {
// Decrease the font-size
break
}
}
if (j === s.length) {
return font.size
}
}
return -1
}
@LinkSausage What do you think about bounding the font sizes you need to consider and then doing binary search?
In other, words find a font that will for sure fit and one that will for sure not fit. Then do binary search on the remaining fonts. You could maybe even improve the speed by using the average font size somehow.
@albin.severinson - the interviewer did mention it was a "bounding" problem. So your hunch is right. Although given the fact the input string length is unknown, I don't see how useful an greedy/opportunistic bounding approach is. Now think of it, if the question was asked "what's the quickest way to find out whether a random string can be rendered on display", that could be just a binary search solution as you suggested.
Assuming the random string forms some kind of natural language flow text with words and spaces and no formatting such as line breaks, paragraphs, headings, tables etc. and no word division (hyphenation) or maybe with the strategy would almost stay the same.
- Chris January 04, 2017Basic strategy:
1) estimate a font size by guessing
2) Layout based on the estimate, correct into either direction
1) Estimate
- there are unknowns like word wraps, average character width, but line height is given by the font size, e.g. 1.5 times max_height
- assume average word size (in characters) that is either typical or by analyzing the given text
- assume average charachter width either typical or by analyzing given text
- from the given screen width and each font characteristics you can now estimate the number of lines which in return gives yout the hight needed.
- calculate this characteristics for each font if n is reasonable small or binary search the font size and pick the biggest where the desired height fits within the bounds given
2) now layout with real text and adjust font until it overlaps or fit... when the string is really random, you might, after running some samples be able to bypass the last step or only correct font size downwards in case it overlaps in rare cases... how ever the estimations might need to be language sensitive.