Amazon Interview Question
Dev Leads Dev LeadsCountry: India
Interview Type: Written Test
This would give all the possible outputs
set1="5,3,1,8, -8,-4"
def getSum(set2):
sum=0
for i in set2.split(','):
try:
sum+=int(i.strip())
except:
continue
return sum
def func1(set1,set2,i):
if i < len(set1.split(',')):
func1(set1,set2,i+1)
set2+="%s,"%set1.split(',')[i]
func1(set1,set2,i+1)
if getSum(set2)==0:
print set2
func1(set1,"",0)
outputs=>
8, -8,
3,1,-4,
3,1,8, -8,-4,
5,3, -8,
One of way to achieve this via brutal force is to generate the POWER set of the given set. Then check each of the POWER set if the sum of all the elements is equal to zero.
Please refer here for generating POWER set (recursive and non-recursive implementations):
cpluspluslearning-petert.blogspot.co.uk/2014/04/dynamic-programming-generate-power-set.html
The major problem here is the space complexity. Assume the given set has the size of N, then the POWER set has the size of 2^N (refer to cpluspluslearning-petert.blogspot.co.uk/2014/04/dynamic-programming-generate-power-set.html). The space complexity is O(2^N). According to Apurohit.in's description N could reach 100. This is a challenge to generate the POWER set and keep in memory. Need more investigation......
As my last comment points out that the way of generating the POWER set will not be feasible if the size, N, of the given set is too large because of the space complexity.
I have crafted a solution of O(N) space complexity that will constant update the indices of elements of subsets and its sum. It is a DP solution. Please refer to:
cpluspluslearning-petert.blogspot.co.uk/2015/01/dynamic-programming-list.html
Test:
1. The sub-sets is printed out to standard display
2. Test against the number of sub set with sum equal to zero
void TestPrintSubSetOfSummOfAllElementsEqualZero()
{
{
const SET testSet = { 5, 3, 1, 8, -8, -4 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 4);
}
{
const SET testSet = { 0, 0, 0 , 0 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 15);
}
{
const SET testSet = { -1, 1 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 1);
}
{
const SET testSet = { -1, 1, -3, 3 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 3);
}
{
const SET testSet = { -1, 1, -3, 3, -4, 4 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 9);
}
{
const SET testSet = { -1, 1, -2, 2, -3, 3, -4, 4 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 25);
}
{
const SET testSet = { -1, 1, -2, 2, -3, 3, -4, 4, -5, 5 };
assert(PrintSubSetOfSummOfAllElementsEqualZero(testSet) == 75);
}
}
Continue with my last comments. I was thinking of if there are any heuristic rules to help the searching.
My method is to sort the given set into 3 different portions: the negative sets, Sn, zero elements sets, So, and the positive element sets, Sp. We can ignore the zero elements set for now because they can either appear or not appear in the solution sub-set. Therefore any solution sub-set have to have negative and positive elements. The idea is to generate sub-sets from the Sp ( with a known NegativeSum) first and then to find a sub-set in Sp, whose sum is equal to the absolute value of NegativeSum.
The heuristic rules:
- Sn or Sp is empty, no need to search
- So is not empty
* Found solutions from Sn and Sp, then the number of solution sub-set expand time of
2^SizeOf(So)
* Not found, then the number of solution sub-sets are 2^SizeOf(So) -1. The solution
sub-sets are made of all zeros.
- If the sum of the current sub-set of Sp is more than the absolute value of NegativeSum,
then stop the search in the Sp because taking any extra element in from Sp will simply
cause the sum of the positive sub-set higher.
The details please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/02/dynamic-programming-list-all-sub-sets.html
Test
void TestPrintSubSetOfSummOfAllElementsEqualZero_Heuristic()
{
{
const SET testSet = { 1, 3, 5, 7};
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 0);
}
{
const SET testSet = { -1, -3, -5, -7 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 0);
}
{
const SET testSet = { -7, -8, -9, -10, 1, 2, 3 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 0);
}
{
const SET testSet = { 7, 8, 9, 10, -1, -2, -3 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 0);
}
{
const SET testSet = { 0, 0, 0, 0};
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 15);
}
{
const SET testSet = { 5, 3, 1, 8, -8, -4 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 4);
}
{
const SET testSet = { 0, 0, 0, 0 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 15);
}
{
const SET testSet = { -1, 1 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 1);
}
{
const SET testSet = { -1, 1, -3, 3 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 3);
}
{
const SET testSet = { -1, 1, -3, 3, -4, 4 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 9);
}
{
const SET testSet = { -1, 1, -2, 2, -3, 3, -4, 4 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 25);
}
{
const SET testSet = { -1, 1, -2, 2, -3, 3, -4, 4, -5, 5 };
assert(Set(testSet).PrintSubSetOfSummOfAllElementsEqualZero_Heuristic() == 75);
}
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
int[] arr = {5,3,1,8,-8,-4};
for(int i=0;i<arr.length;i++){
printAllZeroSets(arr,i,0,0);
}
}
public static void printAllZeroSets(int[] arr, int start, int currSum, int total){
if(start>arr.length-1){
return;
}
int thisValue = arr[start];
if(currSum + thisValue == total){
System.out.println(thisValue + "," + currSum);
return;
}
for(int i=start+1; i<arr.length; i++){
if(currSum + thisValue + arr[i] == total){
System.out.println(arr[i] + "," + thisValue + "," + currSum);
}
}
printAllZeroSets(arr, start+1, currSum+thisValue, total);
}
}
- Anonymous January 11, 2015