Reverse a domain name string

Question

For an interview question, I was asked to do the following:

Given a dot separated domain name, reverse the domain elements.

Here are a few input/output examples:

codereview.stackexchange.com -> com.stackexchange.codereview
foo.bar -> bar.foo
a.. -> ..a

This was my proposed solution. I really feel like there's probably a better way to do this (in place?).

#include <iostream>
#include <string>

std::string
reverse(const std::string &str)
{
    std::string rstr = str;
    std::reverse(rstr.begin(), rstr.end());
    int size = rstr.size();
    int start = 0;
    int end = 0;
    while (end != size + 1) {
        if (rstr[end] == '.' || end == size) {
            std::reverse(rstr.begin() + start, rstr.begin() + end);
            start = end + 1;
        }
        ++end;
    }
    return rstr;
}

int 
main()
{
    std::string examples[] = {
        "hello.world",
        "com.domain.something",
        "..a"
    };

    int size = sizeof(examples) / sizeof(examples[0]);
    for (int i = 0; i < size; ++i) {
        std::cout << examples[i] << " -> " << reverse(examples[i]) << std::endl;
    }

    return 0;
}

Answer 1

This looks quite fine to me. Granted, you make several passes over the entire string, but that doesn't matter much, as the time complexity remains \$O(n)\$, space complexity constant, and this is easy to read and understand.

You could reduce the number of passes by using extra storage, in which you could prepend the reversed segments. But due to the extra storage, such algorithm would not be better, it would be different. Whether one solution is better than the other depends on external constraints not stated in the problem. Talking about this is important at an interview, more important than whatever solution you gave.

In terms of the implementation, the only thing I would change is convert the main while loop to a for loop. The reason is that the start and end variables are only used inside the loop body, and the for loop would help confining them into that scope, which is a good thing, reducing the live time of those variables, and preventing accidental uses outside the loop.

Answer 2

Main Suggestion

I think it will be useful to have couple of overloaded functions, one for working with const std::strings and one for regular std::strings.

With a const std::string, pay the cost of making a copy, reversing the copy, and returning the copy.

With a std::string, you can avoid all the above costs. You make all modifications to the string in place.

std::string& reverse(std::string& str)
{
   // Don't pay the cost of making copies for regular strings.
   std::reverse(str.begin(), str.end());
   int size = str.size();
   int start = 0;
   int end = 0;
   while (end != size + 1) {
      if (str[end] == '.' || end == size) {
         std::reverse(str.begin() + start, str.begin() + end);
         start = end + 1;
      }
      ++end;
   }

   return str;
}

std::string reverse(std::string const& str)
{
   std::string copy = str;
   return reverse(copy);
}

Now, you can reverse regular std::strings as well as temporary std::strings, i.e. const std::strings, while paying the cost of making copies only for const std::strings.

int main()
{
    std::string examples[] = {
        "hello.world",
        "com.domain.something",
        "..a"
    };

    int size = sizeof(examples) / sizeof(examples[0]);
    for (int i = 0; i < size; ++i) {
        std::cout << examples[i] << " -> " << reverse(examples[i]) << std::endl;
    }

    std::cout << "abc.com" << " -> " << reverse("abc.com") << std::endl;
    return 0;
}

Use right type names

Don't use int where other type names are more appropriate. You can use auto to avoid such issues. I would recommend replacing

int size = str.size();
int start = 0;
int end = 0;

with

auto size = str.size();
decltype(size) start = 0;
decltype(size) end = 0;

Using std::reverse vs hand crafted function to reverse a string

You can reverse a string or part of the string using std::reverse like you have in your code:

std::reverse(str.begin(), str.end());

and

std::reverse(str.begin() + start, str.begin() + end);

You can also reverse a string or part of the string using a hand crafted function:

void reverse_string(std::string& str, size_t start, size_t end)
{
   for ( --end; start <= end; ++start, --end )
   {
      char c = str[start];
      str[start] = str[end];
      str[end] = c;
   }
}

and use it as:

reverse_string(str, 0, str.size());

and

reverse_string(str, start, end);

I noticed that the hand crafter version performs 50% faster than std::reverse.

Sample program:

#include <iostream>
#include <string>
#include <algorithm>
#include <ctime>
#include <cstdlib>

void timeFunction(void (*fun)(int, std::string&), int N, std::string& str)
{
   clock_t start = std::clock();
   fun(N, str);
   clock_t end = std::clock();
   double secs = 1.0*(end-start)/CLOCKS_PER_SEC;
   std::cout << "Time taken: " << secs << std::endl;
}

void test_reverse_string_1(int N, std::string& str)
{
   for (int n = 0; n < N; ++n )
   {
      std::reverse(str.begin(), str.end());
   }
}

void reverse_string(std::string& str, size_t start, size_t end)
{
   for ( --end; start <= end; ++start, --end )
   {
      char c = str[start];
      str[start] = str[end];
      str[end] = c;
   }
}

void test_reverse_string_2(int N, std::string& str)
{
   for (int n = 0; n < N; ++n )
   {
      reverse_string(str, 0, str.size());
   }
}

int main(int argc, char** argv)
{
   int N = atoi(argv[1]);
   std::string str = argv[2];
   timeFunction(test_reverse_string_1, N, str);
   timeFunction(test_reverse_string_2, N, str);
   return 0;
}

Command to build (under Linux, using g++ 4.8.4) :

g++ -Wall -std=c++11     socc.cc   -o socc

Execution and ouput:

>> ./socc 1000000 "The quick brown fox jumped over the lazy dog."

Time taken: 0.484501
Time taken: 0.297132

>> ./socc 4000000 "The quick brown fox jumped over the lazy dog."

Time taken: 1.92211
Time taken: 1.02913

Standard Disclaimer

Your mileage may vary depending on your compiler and run time environment.

Answer 3

Reference vs Value

std::string
reverse(const std::string &str)
{
    std::string rstr = str;

If you wish for you algorithm to make a copy and you are not using the original string, pass by value. Your function also is not a plain reverse, so give it an appropriate name.

Prefer C++-style declarations (const std::string& str)

References/pointers relate more to the type than the expressions/grammar.

Ensure all dependencies are included

    std::reverse(rstr.begin(), rstr.end());

Missing <algorithm>.

Prefer for over while when using loop variables

    int start = 0;
    int end = 0;
    while (end != size + 1) {
        // ...
        ++end;
    }

The logic for the loop is up front.

Prefer initializing loop variables in the for initialization when not used out of the loop

Avoid magic constants

        if (rstr[end] == '.' || end == size) {

Magic/Literal constants can sometimes be overlooked. Use symbolic constants, as they provide semantic context when reading.

Answer 4

You could also try to avoid explicit loops, and playing around with indices yourself. Instead, we can let the standard library do most of the work for us. Indeed, let us use a stringstream to parse the input string (the delimiter is a dot). After the string has been split into parts, we reverse its elements, and write the contents to a new string.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

int main()
{
    const std::string s = "codereview.stackexchange.com";
    std::istringstream iss(s);

    std::vector<std::string> parts;
    for (std::string token; std::getline(iss, token, '.'); )
        parts.emplace_back(token);

    std::ostringstream oss;
    std::reverse(parts.begin(), parts.end());
    std::copy(parts.begin(), parts.end() - 1, std::ostream_iterator<std::string>(oss, "."));
    oss << parts.back();

    std::cout << oss.str() << "\n";
}

It worth noticing that the above is not exactly correct, outputting on ".a" on "a.." (instead of the expected "..a"). This can also be handled, but I'll omit it to convey the idea.

Answer 5

As you might understand from my original comments on your post, I don't agree with janos, that your solution is easy to read and understand. Here is the main issues I have with your solution:

• I find it confusing to reverse the entire string, and then to undo the first reverse for each domains one by one. Timewise this results in two traversals of the original string: One for the initial reversal, and one by the while loop reversing it back again
• You kind of hide the std::reverse with your choice of name for the function, and then when using it within the function you have to look twice to make sure you are not writing a recursive function. Nameing your main function, reverse_domains, would aleviate this, and also give a clearer indication on what your function actually does
• You also name the length variable for size, which is the same as the name of the function used to calculate it, size(). This complicates the logic a little bit, because you have to distinguish between doing the call of the function, or the use of the length variable
• Similarily using str and rstr is unneccessary confusing. It would look better to use result instead of rstr in my opinion.

On the bright side, your code is nicely indented, and you are pretty consistent with bracing style, and other stylistic elements. And it does what it is supposed to do!

Alternate algorithm

In the comments I suggested to use split and join, which has been commented upon by another answer afterwards. In the answer by janos, it's suggested to keep as is, but here is a faster alternative where you only traverse the text once, whilst building the result string.

Code follows:

std::string reverse_domains(const std::string& source)
{
    std::string result;
    size_t source_length = source.size();
    size_t end = source_length;

    // Loop from end of string to reverse the domains
    for (int i = source_length; i >= 0; i--) {

        // If not domain divider, continue 
        if (source[i] != '.') {
            continue;
        }

        // Append the domain substring
        result.append(source, i+1, end - i);
        result += '.'; // Append divider
        end = i-1; // Set end point of next domain
    }

    // Copy the last bit of source string, if needed
    if ((end = result.size()) != source_length) {
        result.append(source, 0, source_length - end);
    }
    return result;
}

In this code I've also added a few comments to explain what is going on, which was missing in your original code. And I used a little longer, but more descriptive variable names. Note that this method has the same space complexity as yours, as it creates a string to be returned, but the time complexity has been halfed as it only traverses the string once.

Performance comparison

I did a simple comparison test at repl.it (see complete code), running the reversal of a given list of domains (including your samples) 10 000 times, and taking the time. Your version clocked in at around 0.024 seconds, whilst mine clocked in at around 0.013 seconds. That is almost half the time of your code, or a 50 % improvement.

Addendum on memory cost

It has been argued by LokiAstari that my solution is not the fastest one, which is a claim I haven't made, and that the cost of memory allocation is more important than traversal costs. When comparing mine versus the OP solution, the memory cost is almost identical as both solutions uses a const std::string & as input, and not a mutable string. And timings clearly indicate which solution is the faster.

If you change to a mutable string, and does an in-place edit, faster solutions does exist, where one is presented here. This does use the double reversing method and in-place editing, but is even less readable and understandable than the OP version, from my point of view. This solution claims to be 3 times faster than my solution (half-heartedly transformed into an in-place edition).