Welcome to another coding interview challenge. Today we’re going to be implementing text justification. As always, you can implement your solution in any programming language you want. Write the answer in a github gist and post the link in the comments below.
Write an algorithm to justify text. Given a sequence of words and an integer line length k, return a list of strings which represents each line, fully justified.
More specifically, you should have as many words as possible in each line. There should be at least one space between each word. Pad extra spaces when necessary so that each line has exactly length k. Spaces should be distributed as equally as possible, with the extra spaces, if any, distributed starting from the left.
If you can only fit one word on a line, then you should pad the right-hand side with spaces.
Each word is guaranteed not to be longer than k.
For example, given the list of words [“the”, “quick”, “brown”, “fox”, “jumps”, “over”, “the”, “lazy”, “dog”] and k = 16, you should return the following:
["the quick brown", # 1 extra space on the left "fox jumps over", # 2 extra spaces distributed evenly "the lazy dog"] # 4 extra spaces distributed evenly