textJustification.js

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully justified on both the left and the right. Words should be packed in a greedy approach; that is, pack as many words as possible in each line. Add extra spaces when necessary so that each line has exactly Lcharacters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text and lines with one word only, the words should be left justified with no extra space inserted between them. — On CodeFights

I started this one in Ruby last week and gave up, I couldn’t get the ‘hidden tests’ to pass. I didn’t see anything obviously wrong and I didn’t take the time to write more tests.

I went back to this a couple days ago, to implement in JavaScript this time, and I didn’t get any further… This is a completely different type of interview question . As an interviewer, I’d use this to gauge soft skills (communication, team work) and probably talk to the candidate about their strategy for testing/debugging. It has a couple of special cases (single-word lines and the last line get special treatment) that distract from the more interesting task of distributing leftover spaces evenly.

What I did enjoy about this problem was that it motivated me to setup a simple Node.js project (here’s a handy recipe) and get some tests running. I ended up installing a few packages with npm: mocha, chai, and commander. And, I even tried out the built-in node debugger but there’s got to be something better out there… Looking at the docs made me realize that my node version was really out-dated and then I ran across nvm and switched to that (I always used rbenv or rvm).

function textJustification(words, l) {
//1. Split into lines, add between words to count
//2. Add spaces between words
// - Split extra spaces evenly between words
// - When spaces divide unevenly, split the extra and distribute again.
// - For lines with one word only, words are left justified, spaces on the right.
// - For the last line of text, words are left justified, spaces on the right.
var lines = [];
var i = 0;
lines[i] = [];
for(var n in words) {
if(lines[i].join(' ').length === 0 && words[n].length <= l) {
lines[i].push(words[n]);
}
else if((lines[i].join(' ').length + words[n].length + 1) <= l) {
lines[i].push(words[n]);
}
else {
lines[++i] = [];
lines[i].push(words[n]);
}
}
for(var x in lines) {
var line = lines[x].join(" ");
var spaces = l - line.length;
  // last line
if( x == lines.length - 1) {
lines[x] = appendSpaces(line, spaces);
}
// just 1 word on the line
else if(lines[x].length == 1) {
var word = lines[x].join("");
spaces = l - word.length;
lines[x] = appendSpaces(word, spaces);
}
else {
var w = lines[x];
var gaps = w.length - 1;
spaces = l - w.join("").length;
var extraSpaces = spaces % gaps;
var spacesPerGap = Math.floor(spaces / gaps);
   line = "";
for(var j = 0; j < w.length; j++) {
var addOneSpace = false;
if(extraSpaces > 0) {
addOneSpace = true;
extraSpaces--;
}
var filler = spacesPerGap + (addOneSpace ? 1 : 0);
if (j == w.length - 1) {
line += w[j];
}
else {
line += appendSpaces(w[j], filler);
}
}
  lines[x] = line;
}
}
 return lines;
}
function appendSpaces(str, n) {
for(var x = 0; x < n; x++ ) {
str += " ";
}
return str;
}

I added the whole little app to github.