CareerCup

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.

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

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
}

Hi @ChrisK
could you please explain your code in layman language, so that i'll be able understand.

@srterpe The interviewer was asking whether there is a faster way to narrow down the font size range to try. He said if there are 1000+ font sizes is there a better way.

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

The question is problematic because it shows a lack of understanding of both how text works and how fonts work.

It should at a minimum constrain the characters which are allowed to appear int the string, and also specify the direction the text will be rendered.

This has dynamic programming written all over it