Interview Question
Country: India
Interview Type: In-Person
@Rakesh, if your rephrasing of the question above is correct (which I think it is), then why not to solve it using Subset Sum algorithm. We just need to add an extra condition to check if the length of the calculated sub-array does not exceed the n/2 criterion.
1. Sort the whole list of numbers in descending order.
2. If n == 1, print the single element that's the minimum difference.
3. Otherwise if n >= 2, create two variable x, y which denote the sum of two lists whose difference we want to minimize.
4. Assign the first two elements in x and y - i.e. initialize x with one value and y with other.
5. for rest of all the elements : a[i] , add the value to 'x' if (x+a[i]) <= y or add it to 'y'.
one thing we should remember that if the number of values assignment associated with 'x' equal to ceil(n/2) - we should stop adding value to it (x) and continue adding the values with 'y'.
After all these steps abs(x-y) will give you the ultimate answer.
Counter example: { 3,3,2,2,2 }
With your algorithm you miss the optimal solution {3,3} and {2,2,2} because you put the two elements of value 3 in two different teams.
If I understood you correctly
i guess below approach should work :
1.sort in decending order
2. move the first/next element to the team A and next +1 to team B
3. move the next element to team B nad next + 1 to team A
4 . repear step 2 and 3 till the list exhausted .
this should give almost nearest answer .
say the given set is {25,24,15,9,2,1} team A {25,9 , 2 } team b {24,15,1}
but to optimise our result we can further process our teams
find the avg of all the skill level , total skill level /2 . ( lets call this avg )
get the smallest set ( in case of odd )
try to replace the each element by the elements in other set and find the diff between the skil set and avg if it lesser than the earlier diff swap teh elements else replce with next element
diff* -> absolute value ignoring the sign of the result .
if you iterate above step you can attain the optimum result .
for ( i =0 ; i< sizeof( smalest set ) ; i ++ )
{
for ( j= 0 ; j < sizeof(bigger set ) ; J ++ )
{
actual skill set diff = sum of all skilset - avgskilset
temp skill set diff = (sum of all skill of team a - skil set of a[i] + skilset of b[j] ) - avag
if ( temp skill set diff < actual skill set diff)
{
swap teh skill sets a[i] and b[j] ;
}
}
}
Please note you can also do it by just dividing the given set into two sets and just process by above algorithm . (if you sort and divide you will be doin the lesser swap while processing )
@Bruteforce22: Couple of points: 1. the method minimizeSkillGap has code duplicated if and else part to take care of even and odd number of elements. This part can be re-factored. There is a lot of code and you may have to spend some time, so better copy and paste into eclipse in case you do not want to waste time.
public static void minimizeSkillGap(int[] v) {
int minDiff = Integer.MAX_VALUE;
int tempDiff = 0;
int leftMask = 0;
int rightMask = 0;
int sum = 0, N = v.length;
int tempSum = 0;
for (int j : v) {
sum += j;
}
int firstHalf, secodnHalf;
if (N % 2 == 0) {
firstHalf = N / 2;
secodnHalf = N / 2;
ArrayList<HashMap<Integer, Integer>> hash = new ArrayList<HashMap<Integer, Integer>>();
for (int i = 0; i <= firstHalf; i++)
hash.add(new HashMap<Integer, Integer>());
int mask, numSubSets = 1 << firstHalf;
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0;
int subsetSum = 0;
for (int i = 0; i < firstHalf; i++) {
if ((mask & 1 << i) > 0) {
subsetSum += v[i];
subsetSize++;
}
}
hash.get(subsetSize).put(mask, subsetSum);
}
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0;
int subsetSum = 0;
int remSize = 0;
for (int i = 0; i < secodnHalf; i++) {
if ((mask & 1 << i) > 0) {
subsetSum += v[i + firstHalf];
subsetSize++;
}
}
remSize = secodnHalf - subsetSize;
// remSum = halfSum - subsetSum;
for (Integer key : hash.get(remSize).keySet()) {
tempSum = subsetSum + hash.get(remSize).get(key);
tempDiff = Math.abs(sum - 2 * tempSum);
if (tempDiff < minDiff) {
minDiff = tempDiff;
leftMask = key;
rightMask = mask;
}
}
}
System.out.println("Minimum skill diffrerence is " + minDiff);
printSkillGroup(v, leftMask, rightMask);
} else {
firstHalf = N / 2 + 1;
secodnHalf = N / 2;
ArrayList<HashMap<Integer, Integer>> hash = new ArrayList<HashMap<Integer, Integer>>();
for (int i = 0; i <= firstHalf; i++)
hash.add(new HashMap<Integer, Integer>());
int mask, numSubSets = 1 << firstHalf;
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0;
int subsetSum = 0;
for (int i = 0; i < firstHalf; i++) {
if ((mask & 1 << i) > 0) {
subsetSum += v[i];
subsetSize++;
}
}
hash.get(subsetSize).put(mask, subsetSum);
}
numSubSets = 1 << secodnHalf;
for (mask = 0; mask < numSubSets; mask++) {
int subsetSize = 0;
int subsetSum = 0;
int remSize = 0;
for (int i = 0; i < secodnHalf; i++) {
if ((mask & 1 << i) > 0) {
subsetSum += v[i + firstHalf];
subsetSize++;
}
}
remSize = secodnHalf - subsetSize;
for (Integer key : hash.get(remSize).keySet()) {
tempSum = subsetSum + hash.get(remSize).get(key);
tempDiff = Math.abs(sum - 2 * tempSum);
if (tempDiff < minDiff) {
minDiff = tempDiff;
leftMask = key;
rightMask = mask;
}
}
remSize = firstHalf - subsetSize;
subsetSum = 0;
for (Integer key : hash.get(remSize).keySet()) {
tempSum = subsetSum + hash.get(remSize).get(key);
tempDiff = Math.abs(sum - 2 * tempSum);
if (tempDiff < minDiff) {
minDiff = tempDiff;
leftMask = key;
rightMask = mask;
}
}
}
System.out.println("Minimum skill diffrerence is " + minDiff);
printSkillGroup(v, leftMask, rightMask);
}
}
static void printSkillGroup(int[] v, int leftMask, int rightMask) {
System.out.println("leftMask: " + leftMask + ", and rightMask: "
+ rightMask);
int i;
int halfLength = 0;
if(v.length % 2 ==0){
halfLength = v.length / 2;
}else{
halfLength = v.length / 2 + 1;
}
ArrayList<Integer> a = new ArrayList<Integer>();
ArrayList<Integer> b = new ArrayList<Integer>();
for (i = 0; i < halfLength; i++) {
if ((leftMask & 1 << i) > 0) {
a.add(v[i]);
} else {
b.add(v[i]);
}
if(i + halfLength == v.length)
continue;
if ((rightMask & 1 << i) > 0) {
a.add(v[i + halfLength]);
} else {
b.add(v[i + halfLength]);
}
}
System.out.print("Array A: ");
for (Integer value : a)
System.out.print(value + " ");
System.out.print("\nArray B: ");
for (Integer value : b)
System.out.print(value + " ");
System.out.println("");
}
Test
public static void main(String[] args) {
final int input[] = { 1, 20, 20, 20, 29, 30 };
final int skillLevel[] = {25,24,15,9,2,1,4};
minimizeSkillGap(skillLevel);
minimizeSkillGap(input);
}
Can I assume that your question is : Given an array of integers(skill level) of length n. Suppose sum of the elements of the array is "sum". Divide the elements into two groups of n/2 (if n is even, else n/2 and n/2 + 1) elements such that their group sum is equal to sum/2 if possible else as close to sum/2 as possible.
- Rakesh Roy October 16, 2013