Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 5 vote

It seems to be subset-sum problem.

Find a subset with sum of elements half of total sum of array.

- Nitin Gupta December 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

- Daniel. December 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello Daniel
Can you please explain how to use DP for calculating elements for sum S.

- Mohit March 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]]

- Prithvi December 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No offense but that seems like a horrible way to do it. The time complexity is way too high and the permutation can be avoided I think.

- Anonymous December 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous December 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))
  */
}

- sltang December 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

first find the sum S of array, now find a list whose sum is S/2;
that can be done is O(nlongn), by first sort the array ,1,2,... ,N
now if we include N in our list,the remaining list should be, S/2-N,
and so on recursively. so overall complexity is 0(nlogn)

- shailendra.vermaji December 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- Anonymous December 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- louis.arokiaraj December 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }
}

- krylloff December 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- anwser January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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]);
    }
}

- Anonymous January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
    }
}

- Anonymous January 11, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More