This is a Google interview question for software engineer from careercup. Here is the original description,
Divide it into two Equal(it is important) partitions (in size both contains N/2 elements) such that difference between sum of both partitions is minimum.
If number of elements are odd difference in partition size can be at most 1.
If number of elements are odd difference in partition size can be at most 1.
2. Analysis and Solution
It is a combination problem. A problem like given N cards and pick up any half of cards and find out the one combination with the sum closest to the half of sum of all. In this problem we have to differentiate if N is odd or even. If N = 2m, then the number of combination is m!/N!. Anf if N = 2*m+1, then the number of combination is m!/N! too.
Another way of thinking of this problem is regarding it as an optimization problem.
- Objective function: Min(lambda1*X1+lamda2*X2 + ... + lamdaN*XN - HalfOfSum)
- Where lamda(i) either equal to 0 or 1
and Sigma(lamda(i)) = m
These two are identical in essence. Here I am going to propose how to solve it via functional programming in C++.
- n < m,
* F(n) = F(n-1) + lamda(n)*Xn, where lamda(n) = 1
- n = m
* check the sum of F(n) with half of the value of sum of all. Take the min.
* Exhaust other options of Xn. (in this case n is still equal to m and repeat this case)
* Flip previous lamda(n-1) = 0 and exhaust Xn-1. n != m anymore and repeat the whole.
In order to limit the case of Xn, Xn-1 ...., we will sort the array first. If we found the F(n) (n = m) and its sum is over the the min value we recorded so far, then skipped the rest Xn. Because it is sorted any smaller value is replaced with larger one and this does not affect the optimization process.
Another one if we find a solution, for instance a F(n) (n = m) and its value is equal to exactly half of the value of sum of all, then we can stop because one of global solution is found. In my implementation there is a special case that all the numbers are integer. Therefore if the difference is less than 1 we can confirm that a global solution is found.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <algorithm>
#include <numeric>
#include <stack>
#include <vector>
using DataArray = std::vector<unsigned int>;
using ResultStack = std::stack<size_t>;
enum class Action
{
STOP,
CONTINUE,
FOUND
};
Action DivideTwoPartsWithEqualSum(const DataArray& input,
const size_t last_index,
const double sum_of_part,
const size_t size_of_part,
const size_t size_of_all,
ResultStack& result,
size_t& result_size,
double& sumOfResult,
ResultStack& curBestResult,
double& sumOfCurBestResult)
{
if (result_size == size_of_part) {
if (fabs(sumOfResult - sum_of_part) < fabs(sumOfCurBestResult - sum_of_part)) {
// track the min solution
curBestResult = result;
sumOfCurBestResult = sumOfResult;
}
if (fabs(sumOfCurBestResult - sum_of_part) < 1.0) {
// found the best solution;
return Action::FOUND;
}
else if (sumOfResult > sum_of_part) {
// stop here because the rest of combination can't be smaller
return Action::STOP;
}
return Action::CONTINUE;
}
Action act = Action::CONTINUE;
const size_t startIndex = result.top() + 1;
const size_t endIndex = size_of_all - (size_of_part - result_size) + 1;
for (size_t index = startIndex; index < endIndex; ++index) {
// select lamda(i) and push in
result.push(index);
++result_size;
sumOfResult += input[index];
act = DivideTwoPartsWithEqualSum(input, last_index, sum_of_part,
size_of_part, size_of_all,
result, result_size, sumOfResult,
curBestResult, sumOfCurBestResult);
if (act == Action::FOUND) {
break;
}
// flip lamda(i) and pop out
result.pop();
--result_size;
sumOfResult -= input[index];
if (act == Action::STOP) {
act = Action::CONTINUE;
}
}
return act;
}
double DivideToTwoPartsWithEqualSum(const DataArray& input,
DataArray& result)
{
if (input.empty()) {
return -1.0;
}
const size_t len = input.size();
const size_t size_of_part = len >> 1;
const double sum_of_all = std::accumulate(input.begin(), input.end(), 0.0);
const double sum_of_part = sum_of_all/2;
const size_t last_index = (len & 1) > 0 ? (size_of_part + 2) : (size_of_part + 1);
DataArray inputCopy(input);
ResultStack tempResult;
size_t size_of_stack;
double sum_of_stack;
ResultStack bestResult;
double sumOfBestResult;
std::sort(inputCopy.begin(), inputCopy.end()); // sort
for (size_t index = 0; index < last_index; ++index) {
tempResult.push(index);
size_of_stack = 1;
sum_of_stack = inputCopy[index];
if (DivideTwoPartsWithEqualSum(inputCopy, last_index,
sum_of_part, size_of_part, len,
tempResult, size_of_stack,
sum_of_stack, bestResult,
sumOfBestResult) == Action::FOUND) {
break;
}
tempResult.pop();
}
result.clear();
result.reserve(size_of_part);
while (!bestResult.empty())
{
result.push_back(inputCopy[bestResult.top()]);
bestResult.pop();
}
return sumOfBestResult;
}
// ********************************************************************************
// Test
// ********************************************************************************
void TestCases
{
DataArray result;
// solution: 1, 8, 9
assert(DivideToTwoPartsWithEqualSum(DataArray{ 1, 2, 3, 6, 8, 9, 7 }, result) == 18.0);
// solution: 5, 7, 62
assert(DivideToTwoPartsWithEqualSum(DataArray{ 5, 7, 50, 8, 9, 62 }, result) == 74);
// solution: 10, 20
assert(DivideToTwoPartsWithEqualSum(DataArray{ 1, 10, 11, 18, 20 }, result) == 30);
// solution: 1, 10, 13
assert(DivideToTwoPartsWithEqualSum(DataArray{ 1, 7, 8, 9, 10, 13 }, result) == 24);
}
No comments:
Post a Comment