text format solution

Question

A firm gave me a small take home assignment which asks you to implement text formatter. Given some text which only contains alphanumerics and spaces (only one space between words), we should align it either using one of LEFT, RIGHT or CENTER. Here's the main logic

This is the header file

#pragma once

#include <string>
#include "utils.hpp"

namespace formatter
{
    
enum Align {
    LEFT_ALIGN, 
    RIGHT_ALIGN, 
    CENTER_ALIGN
};

struct FormattedLine {
    size_t start_index;
    size_t end_index;
    size_t left_padding;
    size_t right_padding;
};

class Formatter {
public:
    std::string AlignText(const std::string& text, size_t column_width, const std::string& align_mode);
    Align GetAlignMode(const std::string& align_mode);
};

} // namespace formatter

And here's the main logic

#include <vector>
#include <iostream>

#include "formatter.hpp"

namespace formatter
{

Align Formatter::GetAlignMode(const std::string& align_mode) {
    if (align_mode == "LEFT_ALIGN") {
        return Align::LEFT_ALIGN;
    } else if (align_mode == "RIGHT_ALIGN") {
        return Align::RIGHT_ALIGN;
    } else if (align_mode == "CENTER_ALIGN") {
        return Align::CENTER_ALIGN;
    } else {
        throw std::invalid_argument("Align mode \"" + align_mode + "\" is not currently supported");
    }
}

std::string Formatter::AlignText(const std::string& text, size_t column_width, const std::string& align_mode) {
    if (!formatter_utils::IsValid(text)) {
        std::cerr << "Error: Invalid text input. No characters apart from lowercase ASCII or uppercase ASCII or spaces is allowed" << std::endl;
        return "";
    }
    if (!text.length()) {
        std::cerr << "Error: Empty input" << std::endl;
        return "";
    }
    
    std::vector<std::string> words = formatter_utils::SplitString(text);
    std::vector<FormattedLine> lines;

    auto const construct = [this, &lines, &column_width, &align_mode](size_t start_index, size_t end_index, size_t current_line_length) {
        switch (GetAlignMode(align_mode)) {
            case Align::LEFT_ALIGN:
            {
                lines.emplace_back(FormattedLine{start_index, end_index, 0, 0});
                break;
            };
            case Align::RIGHT_ALIGN:
            {
                auto padding_length = std::max(0ul, column_width - current_line_length + 1);
                lines.emplace_back(FormattedLine{start_index, end_index, padding_length, 0});
                break;
            };
            case Align::CENTER_ALIGN:
            {
                auto padding_length = std::max(0ul, column_width - current_line_length + 1);
                // For uneven padding length, Keep the text more left aligned than right aligned
                auto left_padding_length = padding_length / 2;
                auto right_padding_length = padding_length - left_padding_length;
                lines.emplace_back(FormattedLine{start_index, end_index, left_padding_length, right_padding_length});
            };
        }
    };

    size_t start_index = 0, current_line_length = 0;
    for (size_t end_index = 0; end_index < words.size(); end_index++) {
        const auto& word = words[end_index];
        // If the word is longer than column width, print error to STDERR
        if (word.length() > column_width) {
            std::cerr << "Error: current word \"" << word << "\" is longer than column width (" << column_width << ")" << std::endl;
            return "";  
        }
        if (current_line_length + word.length() > column_width) {
            construct(start_index, end_index, current_line_length);
            current_line_length = word.length() + 1;
            start_index = end_index;
        }
        else {
            current_line_length += word.length() + 1;
        }
    }
    if (current_line_length) {
        construct(start_index, words.size(), current_line_length);
    }

    std::string result;
    // This looks like O(N^2) but we are just iterating through all words using their respective indices
    for (const auto& [start_index, end_index, left_padding, right_padding] : lines) {
        result += std::string(left_padding, ' ');
        for (auto index = start_index; index < end_index; index++) {
            result += words[index];
            result += ' ';
        }
        result.pop_back();
        result += std::string(right_padding, ' ');
        result += "\n";
    }
    result.pop_back();

    return result;
}

} // namespace formatter

The time complexity for this solution is \$O(N)\$ where \$N\$ is the length of the text and Space would be \$O(N) + O(L)\$ where \$L\$ is the number of formatted lines. I thought the solution was optimal enough but apparently the firm thinks that this is an okay solution.

I was wondering what could I have done in order to optimise this. One thing I can think of is that iterate through given text without breaking them into words which get rids of additional space but time complexity would still be same. Wondering if community can provide more feedback on this

Note: Ignore the errors being printed out to STDERR. That's a requirement otherwise, I would never do that

Answer 1

In addition to greybeard's answer:

Optimize calls to emplace_back()

I see lots of statements like this:

lines.emplace_back(FormattedLine{start_index, end_index, 0, 0});

However, that is not efficient use of emplace_back(); you are first creating a temporary FormattedLine object, and then when emplacing it is using the copy or move constructor, just like push_back() would do. You can write it like this however:

lines.emplace_back(start_index, end_index, 0, 0);

Now the normal constructor is called, and no moves or copies have to be made.

Use '\n' instead of std::endl

Prefer using '\n' instead of std::endl; the latter is equivalent to the former, except that it also forces the output to be flushed, which is usually unnecessary and might hurt performance.

Don't split the input up front

Space [complexity] would be \$O(N) + O(L)\$ where \$L\$ is the number of formatted lines.

The only reason for this is because you split the strings into words and store the words into a vector. Basically, that is copying the entire input up front. But do you really need that? You just need to keep track of where in text words begin and end. But even then you don't need to find the start and end of every word up front, you only need to keep track of it for the line you are currently working on. In other words, it should be possible to do this with \$O(1)\$ space complexity.

An elegant way would be to have some way to iterate over the words in a string, so you could write something like:

std::string line;

for (auto& word: split(text)) {
    if (!word_fits_on_line(word, line)) {
        align_and_print(line);
        line.clear();
    }

    append_word(word, line);
}

if (!line.empty()) // final line
    align_and_print(line);

So split() should return some object that has begin() and end() member functions that return iterators, and those iterators should return words (preferably using std::string_view to avoid unnecessary copies).

However, as greybeard already mentioned, you don't need to look at individual words, you just need to find a group of words that fits into a single line, and then align and print that whole group in one go. Consider the following code, which follows the same structure as the iterator approach above:

std::string::size_type start = 0, prev_end = 0, end;

while ((end = line.find(' ', start)) != std::string::npos) {
    if (end - start > column_width) {
        align_and_print(line.substr(start, prev_end));
        start = prev_end + 1;
    }

    prev_end = end;
}

if (prev_end != start)
    align_and_print(line.substr(start));

Note that the above example doesn't handle words longer than column_width, but that could be added easily.

Answer 2

(I'm completely out of touch with C++, modern C++ in particular.
I don't feel at odds with a potentially big std::string result built with += while entirely possibly everyone should be.)

Especially with a take-home assignment from a firm, I'd welcome more explicit documentation; minimum: AlignText() in Formatter in the header.

I don't like else controlling a statement with no way of getting reached otherwise.

Align mode doesn't change: convert from string once.

Formatter::AlignText() is on the long side. There is the faction every loop deserves its own procedure - well, I'm with every processing step shall be documented.
In the loop iterating lines to create result, you use left_padding and right_padding to uniformly handle padding. Doing same in construct reduces the repetition there:

auto const 
construct = [this, &lines, &column_width, &align_mode]
            (size_t start, size_t end, size_t line_length) {
        auto left_padding = 0,
             right_padding = 0;
        if (LEFT_ALIGN != align_mode) {
            auto padding_length = std::max(0ul, column_width - line_length + 1);
            switch (align_mode) {
            case Align::RIGHT_ALIGN:
                left_padding = padding_length;
                break;
            case Align::CENTER_ALIGN:
                left_padding = padding_length / 2;
                right_padding = padding_length - left_padding;
                break;
            }
        }
        lines.emplace_back(FormattedLine{start, end, left_padding, right_padding});
    };

(See G.Sliepen's answer: the invocation of emplace_back() should avoid a copy
lines.emplace_back(start, end, left_padding, right_padding);.)

---

You tagged algorithm - I find myself thinking about the problem quite differently:

The start of a line is at some position into text - 0, initially.
Either the rest of text fits column_width and should be handled as the last line, or I'd start looking for a space from position + column_width (inclusive/ + 1) down to position. If none, whail; else pad immediately and repeat from position following that space.

No advantage to handling words inside those limits.
No advantage to first enlisting padding for every line, and as a follow-on step perform the padding. Consequently, no use for FormattedLine.