Store credit code jam

I have found out that a common source of interview questions is Google Code Jam. You can practicing for this contest seeing what they did in the past editions, and there you can find interesting problems. The other day I have played with the first one proposed, part of the Qualification Round Africa 2010.

The core of the job is writing a function that gets in input an integer, representing an amount that we want to spend, and an array of integers, representing the cost of any single item that we could buy.

We know for sure that exists one and only one pair of values in the array respecting the condition:

total = first + second

Total is given, our task is returning the indexes in the array for first and second.

I avoid discussing the code around the function, that is pretty boring. It deals about reading from the input file provided by Code Jam and creating the relative output file in the expected format. Being C++ the language that I used, it was a matter of opening an ifstream, calling getline() on it a few times, converting strings to int (atoi sufficed), and extracting integers from a string (istringstream came handy). Then I created a ofstream, and put to it the results.

I should handle couples of values, so I am going to use std::pair, that I typedef'ed it Choice, to make it a bit more expressive. The function itself takes in input the total and the available values, and gets back the pair of indexes:

typedef std::pair<int, int> Choice;

Choice getChoice(int total, const std::vector<int>& input);

Before let my program work with the actual input data, I have written a few test cases, that I used to drive my code development. Here is just one of them:

TEST(TestCredit, Case1)
{
    const int TOTAL = 100;
    const int VALUES[] = {5, 75, 25};
    std::vector<int> values(VALUES, VALUES + sizeof(VALUES) / sizeof(int));

    Choice choice = getChoice(TOTAL, values);

    EXPECT_EQ(2, choice.first);
    EXPECT_EQ(3, choice.second);
}

And here is how I implemented the function:

Choice getChoice(int total, const std::vector<int>& input)
{
    typedef std::vector<int>::size_type ST;
    for(ST i = 0; i < input.size() - 1; ++i) // 1
    {
        if(input[i] >= total) // 2
            continue;

        for(ST j = i + 1; j < input.size(); ++j) // 3
        {
            if(input[i] + input[j] == total)
                return Choice(i+1, j+1);
        }
    }

    return Choice(); // 4
}

1. Admittedly, this implementation is quite brutal. Still, we didn't get tough requirements on time complexity, and we need to produce some working code quickly. So, I reckoned this plain Oh-n-square algorithm should be enough.
2. We need two values, so the first one should be smaller than the total. If this is not true, we skip to the next iteration.
3. Let's check all the values after the current one. If we found the happy couple, return it.
4. We should never get it, accordingly to the requirements. So I return the "bad" pair (0, 0). I could have thrown an exception, to make things more clear.

My test cases OK'd it, so I ran my application against the data provided by Code Jam (Oh-n-square performance was not a problem at all), submitted the results, and got the confirmation that all works alright.

In the comment to the post, Arthur passes a link to a github page with his two solutions to this problem. As Arthur says, one is quite similar to the one I have already presented, the other one it looks to me overly complicated, and probably an example of premature optimization (root of all evil!). I found more interesting the simple one, that makes uses of STL and C++11 features. On its dark side, it abuses of the C++ meaning for the auto keyword, and it loops by while, in a way that seems to me less natural than by for.

Using the Arthur suggestions, I'll rewrite the getChoice() in this way:

Choice getChoice(const int total, const std::vector<int>& values)
{
  typedef std::vector<int>::const_iterator IT;
  for(IT it = values.begin(); it != values.end() - 1; ++it) // 1
  {
    int first = *it;
    if(first >= total)
        continue;

    IT it2 = std::find_if(it + 1, values.end(), [first, total] (const int second) { // 2
      return first + second == total;
    });
    if(it2 != values.end()) // 3
      return { it - values.begin() + 1, it2 - values.begin() + 1 };
  }

  return { 0, 0 }; // 4
}

1. Instead of a plain old for loop, a loop on an iterator interval is more expressive.
2. The internal loop could be rendered with a call to the STL find_if() algorithm couple with a lambda. This line could be read: return the iterator to the element in the vector in the interval starting from the next to the current element, ending to the natural end of the range, that satisfies the requested relation (first plus second equals total).
3. If find_if() fails, it returns the end() iterator to the container.
4. Using the new C++11 notation to create a Choice (that is, a std::pair) could actually result more natural.