Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
If you sum all the numbers in the set, then you just have to find the numbers which total half of that sum (i.e if you have 1,2,3,4 sum is 10. 2 + 3 total 5, 1 + 4 totals 5).
Say you get that the sum of your set divided by two is S.
At this point, you just gotta use the 0/1 knapsack algorithm (can't repeat elements) to find a combination of numbers that sums up to that S.
This would be O(nS) complexity which is exponential (since usually any N numbers will sum up higher than 2N).
Should you find only one set of numbers or sets of all numbers? i mean for {1,2,3} the answer would be {-1-2},{-3}. Assuming we need to return all sets of negative numbers,
1. find permutations of the array.
2. for each element in permutation; negate 1st element and take the sum. if sum is 0, return the 1st element, else negate 1st and 2nd elements... and so on...
java POC:
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4 };
System.out.println(findnegateSet(a));
}
private static Set findnegateSet(int[] ary) {
List<int[]> lst = new LinkedList<int[]>();
permute(ary, lst, 0);
Set<Set<Integer>> set = new HashSet<Set<Integer>>();
for (int[] is : lst) {
Set<Integer> temp = sumZero(is);
if (temp != null) {
set.add(temp);
}
}
return set;
}
private static Set<Integer> sumZero(int[] ary) {
boolean brk = false;
for (int i = 0; i < ary.length; i++) {
ary[i] = -1 * ary[i];
if (sum(ary) == 0) {
brk = true;
break;
}
}
Set<Integer> negVal = new HashSet<Integer>();
if (brk) {
for (int i : ary) {
if (i < 0) {
negVal.add(i);
}
}
return negVal;
}
return null;
}
private static int sum(int[] ary) {
int sum = 0;
for (int i : ary) {
sum += i;
}
return sum;
}
public static void swap(int[] ary, int i, int j) {
int temp = ary[i];
ary[i] = ary[j];
ary[j] = temp;
}
public static void permute(int[] ary, List<int[]> temp, int j) {
if (j == ary.length - 1) {
temp.add(ary.clone());
return;
}
for (int i = j; i < ary.length; i++) {
swap(ary, i, j);
permute(ary, temp, j + 1);
swap(ary, i, j);
}
}
output:
[[-3, -2], [-4, -1]]
Complexity is exponential but I dont think there is a way to avoid it in this case. It boils down to subset problem which is an exponential problem.
def subset (myList,target):
if (sum(myList)==target):
return myList
if (len(myList)==1):
return []
answer = [myList[-1]]+subset (myList[:-1],target-myList[-1])
if (len(answer)!=1):
return answer
else:
if answer[0]!=target:
answer = subset(myList[:-1], target)
return answer
return answer
def findNegate(x):
sumOfElements = sum(x)
if sumOfElements%2!=0:
return []
target = sumOfElements/2
print (target)
x.sort()
negateList = []
summation=0
for i in x:
summation+=i
negateList.append(i)
if (summation>=target):
break
if (summation==target):
return negateList
answer = subset(negateList,target)
return answer
We have to find all sublists of the the list whose sum is half the sum of the list. (I use List instead of Set as the elements may not be all distinct.) There 2^N such sublists and it is exponential in N. Here is a solution in Scala:
object solver extends App {
type Partition = List[Int]
type Partitions = List[Partition]
def partition(list: List[Int]): Partitions = list match {
case head::tail => {
val p=partition(tail)
p.map(x => head::x):::p
}
case _ => List((List()))
}
val list = List.fromArray(args.map(x => x.toInt))
val sum=(list foldLeft 0)(_ + _)
val partitions=partition(list)
println(partitions.filter(x => (x foldLeft 0)(_ + _) * 2 == sum))
/* for val list= List(2, 3, 4, 5, 6), it gives
List(List(2, 3, 5), List(4, 6))
*/
}
public static void main(String[] args) {
int[] iarr = { 1, 4, 5, 8, 6};
ArrayList <Integer> al = new ArrayList<Integer>();
for( Integer i : iarr)
sum += i;
System.out.println(scan(sum/2, 0, 0, al, iarr));
}
public static ArrayList<Integer> scan(int half, int sum, int i, ArrayList<Integer> al, int arr[]){
if (half == sum)
return al;
if (half < sum )
return null;
for ( int j = i; j < arr.length; j++ ){
ArrayList<Integer> altmp = new ArrayList<Integer>();
for( Integer in : al)
altmp.add(in);
altmp.add(arr[j]);
ArrayList<Integer> t = scan( half, sum + arr[j], j+1, altmp, arr);
if ( t != null)
return t;
}
return null;
}
}
#include<stdio.h>
int main()
{
int i,j,a[100],temp;
static int n=0,sum=0,sum1=0,count=0,count1=0;
printf("\nEnter the number of terms:");
scanf("%d",&n);
printf("\nEnter the %d numbers:",n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
sum=sum+a[i];
}
printf("\n%d",sum);
if(sum==0)
{
printf("\nThe sum is zero already");
}
if(sum%2==0)
{
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<(n/2);i=i+2)
count=count+(a[i]+a[n-i-1]);
for(i=1;i<(n/2);i=i+2)
count1=count1+(a[i]+a[n-(i+1)]);
if(count==count1)
{
for(i=0;i<(n/2);i=i+2)
{
a[i]=-a[i];
a[n-i-1]=-a[n-i-1];
}
printf("\n");
for(i=0;i<n;i++)
{
printf(" %d ",a[i]);
}
for(i=0;i<n;i++)
{
sum1=sum1+a[i];
}
printf("\n%d",sum1);
printf("\nThe numbers to be negated are: ");
printf("\n{");
for(i=0;i<(n/2);i=i+2)
{printf("%d,",a[i]);
printf("%d,",a[n-i-1]);
}
printf("}");
}}
else
{
printf("\nThe is no such combination in the following set:");
printf("\n{");
for(i=0;i<n;i++)
printf(" %d,",a[i]);
printf("}");
}
return 0;
}
I think it is possible to use greedy aproach here
public class FindNegate {
public static void main(String[] args) {
int a[] = {1,2,3};
System.out.println(new FindNegate().findNegate(a));
int b[] = {1,2,3,4};
System.out.println(new FindNegate().findNegate(b));
}
public Collection<Integer> findNegate(int[] array) {
// greedy approach
Arrays.sort(array);
long sum = 0;
for (int val : array) {
sum += val;
}
if (sum % 2 == 1) {
return Collections.emptyList();
}
sum /= 2;
List<Integer> answer = new ArrayList<Integer>();
for (int i = array.length - 1; i >=0; i--) {
if (sum - array[i] >= 0) {
answer.add(array[i] * -1);
sum -= array[i];
}
if (sum == 0) {
return answer;
}
}
if (sum != 0) {
answer.clear();
}
return answer;
}
}
private static List<String> findAllComb(int arr[],int index,int sum)
{
if(index==(arr.length-1))
{
if(sum+arr[index]==0)
{
System.out.println("me");
return new ArrayList<String>();
}
else if(sum-arr[index]==0)
{
List<String> list=new ArrayList<String>();
Integer negate=-1*arr[index];
list.add(negate.toString());
return list;
}
else
return null;
}
else
{
int negatedSum=sum-arr[index];
int normalSum=sum+arr[index];
List<String> negatedSumList=findAllComb(arr,index+1,negatedSum);
List<String> normalList=findAllComb(arr,index+1,normalSum);
if(sum==-5 && index==2)
System.out.println("a");
if(negatedSumList !=null)
{
String negate=Integer.toString(-1*arr[index]);
List<String> newNegaedList= new ArrayList<String>();
if(negatedSumList.size()==0)
newNegaedList.add(negate);
else
{
for(String s: negatedSumList)
{
s=negate+"|"+s;
newNegaedList.add(s);
}
}
negatedSumList=newNegaedList;
}
if(negatedSumList!=null&& normalList!=null)
negatedSumList.addAll(normalList);
else if(normalList!=null)
return normalList;
return negatedSumList;
}
javascript:
var nums=[4,3,1,1,1,1,1];
var sum=0;
for(var i=0; i<nums.length; i++) {
sum+=nums[i];
}
if(sum%2!=0) throw "not possible: " + sum;
var targetSum = sum/2;
var sum=0;
var elems=[];
var reset = function(i) {
sum=nums[i];
elems=[sum];
}
var sort = function(x) {
//assume sorted
}
sort(nums);
for(var i=0; i<nums.length; i++) {
reset(i);
for(var j=i; j<nums.length; j++) { //j=1 to achieve combinations instead of permutations
if(i==j) continue;
if(sum==targetSum) {
console.debug(elems);
reset(i);
continue;
}
if(sum>targetSum) {
reset(i);
continue;
}
sum+=nums[j];
elems.push(nums[j]);
}
}
javascript without sorting:
var nums=[1,1,1,4,1,1,3];
var sum=0;
for(var i=0; i<nums.length; i++) {
sum+=nums[i];
}
if(sum%2!=0) throw "not possible: " + sum;
var targetSum = sum/2;
for(var i=0; i<nums.length; i++) {
var sum=nums[i];
var elems=[sum];
for(var j=0; j<nums.length; j++) {
if(i!=j) {
sum+=nums[j];
elems.push(nums[j]);
}
if(sum==targetSum) {
console.debug(elems);
break;
}
}
}
It seems to be subset-sum problem.
- Nitin Gupta December 08, 2013Find a subset with sum of elements half of total sum of array.