TopCoder Username

Another common source of interview questions is TopCoder, a site that hosts a huge variety of developer competitions. They have a standard format for tests, presented in their How to dissect a TopCoder problem statement page.

As example, they provides a few questions they have used in the past. First of them is the UserName problem. In a handful of words, we have to write a function that ensures the chosen username is available or, if not, propose a viable alternative.

I simplified a bit the required interface, tailoring it for C++. Now, my requirements are that we should write a function respecting this prototype:

std::string check(const std::string& input, const std::vector<std::string>& existing);

Where input is the username submitted by the user and existing is the list of already taken usernames. The function has to return a valid username, preferably the one chosen by the user. If the requested username is already taken, we will return it with a concatenated number - the smallest, the better.

As usual, before start coding, I have written a few testcases. Here is just one of them:

TEST(Username, Case0)
{
  std::string input("MyUsername");
  std::vector<std::string> existing = { "Taken", "Someone", "Hello", "Nickname", "User" }; // 1 

  ASSERT_EQ(input, check(input, existing)); // 2
}

1. I have written this code on a recent GCC compiler, so I took advantage of C++11 initialization for STL vectors.
2. The passed username is not among the list of already existing ones, so I expect to get it back as result of function call.

And here is my solution:

std::string check(const std::string& input, const std::vector<std::string>& existing)
{
  std::set<std::string> orderedNames(existing.begin(), existing.end()); // 1
  if(orderedNames.find(input) == orderedNames.end()) // 2
    return input;

  for(int i = 1; ; ++i) // 3
  {
    std::string candidate = input + boost::lexical_cast<std::string>(i); // 4
    if(orderedNames.find(candidate) == orderedNames.end())
      return candidate;
  }

  // we should never reach here
  throw new std::exception();
}

1. Seeing the requirements, the expected code complexity is not an issue, still I reckoned it was wise to be prepared for a huge vector of existing usernames. In that case, it is worthy to create a set so that we have them ordered, and looking for an element has a cheap O(log n) cost.
2. If the input is not among the existing items, return it.
3. We check until we find a good alternative candidate - so, I used an open ended for loop.
4. Username candidates are build concatenating the user input with a integer, starting from 1. Among the many possible ways of converting an int to a string, I've chosen the boost lexical cast.