Here is a typical algorithmic problem I encounter when interviewed:
Write a program that receives a set of positive integers
(duplicates are possible) and decides if the set of integers can be divided into three subsets with the same sum of elements. For instance, {1,1,1} can be divided into three subsets with equal sum {1} {1} {1}, {3,2,5,4,1,3} can also be divided into three subsets with equal sum {1, 5}, {2, 4}, {3, 3}. {2,3,4,5} however canot be divided into three subsets with equal sum.
The problem can be easily solved using recursion but on an interview it is sometimes easier to come up with a non-recursive solution.
The algorithm:
total sum of elements is not divisible by 3 without reminder, the subsets do not exist.
true, otherwise continue to the next number.
theory:
group of objects (positive numbers in our case) we want to find all the
possible ways to divide the objects between 3 different buckets. Lets number
the buckets 0, 1, and 2, and lets assume for now that buckets are allowed to be
empty but each object must be in one of the buckets.
many ways are there to arrange 1 object into 3 buckets? The answer is 3 because
the object can be placed in either one of the buckets. And using our notation:
0 – object is in the first bucket, 1 – object is in the second bucket, 2 –
object is in the third bucket.
objects we have 9 arrangements:
both objects are in the first bucket
the first object is in the first bucket and the second object is in the second
bucket
the first object is in the first bucket and the second object is in the third
bucket
the first object is in the second bucket and the second object is in the first
bucket
both objects are in the second bucket
the first object is in the second bucket and the second object is in the third
bucket
the first object is in the third bucket and the second object is in the first
bucket
the first object is in the third bucket and the second object is in the second
bucket
both objects are in the third bucket
the similar logic for 3 objects we would have 27 arrangements:
n objects we would have 3^n arrangements. If we look at our example with 3
objects we might notice that we start counting from 0, and go up all the way to
2 and then suddenly go to 10 instead of 3. It actually looks like all the
digits above 2 are missing. And there is a good reason why they are missing. We
count in ternary numeral system or simply base 3.
find all the possible ways to divide a set of objects between 3 different buckets
we just have to count in base 3. And to while we count we can calculate the
total sum of all numbers in each bucket. For example for base 3 number
010011202 and a set of positive numbers 2,4,3,7,8,2,7,2,7 we would calculate
the sum for the first bucket 2+3+7+2, second bucket 4+8+2, and third bucket 7+7
and see that all sums are equal to 14.
course our solution is suboptimal because we only care about the sum of each
group and do care about the bucket order. 010011202 and 101100212 is the same
number for our purposes because nothing changes if we switch the buckets.
fact, to calculate what the number of unique combinations is equal to we would have to learn
Java implementation:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// List Example implement with ArrayList
List<Integer> numbers = new ArrayList<Integer>();
numbers.add(3);
numbers.add(4);
numbers.add(3);
numbers.add(10);
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4);
numbers.add(7);
numbers.add(7);
numbers.add(7);
int n = numbers.size();
int count = (int) Math.pow(3, n);
for (int i = 0; i < count; ++i)
{
String base3 = Integer.toString(i,3);
base3 = padLeft(base3, n);
//System.out.println(“base3:” + base3);
int [] group = {0, 0, 0};
int k = 0;
Iterator<Integer> it=numbers.iterator();
while(it.hasNext())
{
int groupId = Integer.parseInt(base3.substring(k,k+1));
Integer value=(Integer)it.next();
group[groupId] += value;
++k;
}
if (group[0] > 0 && group[0] == group[1] && group[0] == group[2])
{
System.out.println(“base3:” + base3);
}
}
}
public static String padLeft(String s, int n) {
return String.format(“%” + n + “s”, s).replace(‘ ‘, ’0′);
}
}
