Amazon Interview Question for SDE-2s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
2
of 2 vote

public static void combinationForSum(int[] array, int index, List<Integer> result, int givenSum, int curSum) {
				
		if (curSum == givenSum) {
			System.out.println(Arrays.toString(result.toArray()));
			return;
		}
		
		if (curSum > givenSum)
			return;
		
		for (int i = index; i < array.length; i++) {
			curSum += array[i];
			result.add(array[i]);
			combinationForSum(array, i+1, result, givenSum, curSum);
			result.remove(result.size() - 1);
			curSum -= array[i];
		}
	}
	
	public static void main(String[] args) {
		int[] array = {-3,-9,8,4,5,7,10};
		combinationForSum(array, 0, new ArrayList<Integer>(), 15, 0);
	}

- WhoCares July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am doing this question as exercise: I think there could be more than on solution for any array eg: 7+8=15, 5+10=15 etc
do we need this assumption?

- bealebacchus July 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void combinationForSum(int[] array, int index, List<Integer> result, int givenSum, int curSum) {
				
		if (curSum == givenSum) {
			System.out.println(Arrays.toString(result.toArray()));
			return;
		}
		
		if (curSum > givenSum)
			return;
		
		for (int i = index; i < array.length; i++) {
			curSum += array[i];
			result.add(array[i]);
			combinationForSum(array, i+1, result, givenSum, curSum);
			result.remove(result.size() - 1);
			curSum -= array[i];
		}
	}
	
	public static void main(String[] args) {
		int[] array = {-3,-9,8,4,5,7,10};
		combinationForSum(array, 0, new ArrayList<Integer>(), 15, 0);
	}

- WhoCaresIdo July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Alg :
Sort the array,
Starts from N.
Count N and first element to N-1, if sum is matches then return that elements and still start count N and current element towards N-1 until the count is greater than given element.
If count is greater than given element then come for N-1 and do the same.

- sivanraj July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<int[]> CheckSum2(int[] arr, int res)
        {
            List<int[]> lst = new List<int[]>();

            if (arr == null)
                throw new ArgumentNullException();
            if (arr.Length == 0)
            {
                // lst.Add(new int[] { });
                return lst; ;
            }
            int[] inp = arr.Select(x => x).OrderBy(x => x).ToArray();//sorted
            if (inp.Length == 0)
            {
                //  lst.Add(new int[] { });
                return lst; ;
            }

            for (int i = 0; i < inp.Length; i++)
            {
                int num1 = inp[i];
                //if (num1 > res)
                //    break;
                if (num1 == res)
                {
                    lst.Add(new int[] { num1 });
                    continue;
                }
                int[] x = inp.Skip(i + 1).ToArray();

                var rest = CheckSum2(x, res - num1);
                foreach (int[] restNum in rest)
                {
                    var a = new int[restNum.Length + 1];
                    a[0] = num1;
                    for (int j = 1; j < a.Length; j++)
                    {
                        a[j] = restNum[j - 1];
                    }
                    lst.Add(a);
                }

            }

            return lst;
        }

The above code is in C#. I havn't worked out the space/time complexity.
It returns a list of arrays with each array containing the elements that add up the give sum.
So for an array {-1,0,1} if we want to find a sum of 0, then it will return {-1,0,1},{-1,1},{0}

- Devinder Singh July 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<int[]> CheckSum2(int[] arr, int res)
        {
            List<int[]> lst = new List<int[]>();

            if (arr == null)
                throw new ArgumentNullException();
            if (arr.Length == 0)
            {
                // lst.Add(new int[] { });
                return lst; ;
            }
            int[] inp = arr.Select(x => x).OrderBy(x => x).ToArray();//sorted
            if (inp.Length == 0)
            {
                //  lst.Add(new int[] { });
                return lst; ;
            }

            for (int i = 0; i < inp.Length; i++)
            {
                int num1 = inp[i];
                //if (num1 > res)
                //    break;
                if (num1 == res)
                {
                    lst.Add(new int[] { num1 });
                    continue;
                }
                int[] x = inp.Skip(i + 1).ToArray();

                var rest = CheckSum2(x, res - num1);
                foreach (int[] restNum in rest)
                {
                    var a = new int[restNum.Length + 1];
                    a[0] = num1;
                    for (int j = 1; j < a.Length; j++)
                    {
                        a[j] = restNum[j - 1];
                    }
                    lst.Add(a);
                }

            }

            return lst;

}
C# code.
This code will return a list of arrays with each array containing the list of number that adds to the given sum.
E.g. for a given array of {-1,0,1} if the given sum is 0, it will return {-1,0,1},{-1,1},{0}.
I haven't worked out the space/time complexity

- newdevin July 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

if (inp.Length == 0)
            {
                //  lst.Add(new int[] { });
                return lst; ;
            }

The above is redundant

- newdevin July 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class ArraySum {
	
	public static void main(String[] args) {
		int[] arr = {2, 5, 10, 7, 9, 3, 12, 8};
		int K = 17;

		List<Integer> sum = new ArrayList<>();
		List<String> idx = new ArrayList<>();
		
		int size;
		for (int i = 0; i < arr.length; i++) {
			size = sum.size();
			if (arr[i] <= K) {
				sum.add(arr[i]);
				idx.add(i + "");
			}
			for (int j = 0; j < size; j++) {
				if (sum.get(j) + arr[i] <= K) {
					sum.add(sum.get(j) + arr[i]);
					idx.add(idx.get(j) + ", " + i);
				}
			}
		}
		
		for (int i = 0; i < sum.size(); i++) {
			if (sum.get(i) == K) {
				System.out.println(idx.get(i));
			}
		}
	}
	
}

- madi.sagimbekov October 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Tried and tested...i would consider this as O(N)...not considering the adding of items into the Hashtable, as it would be O(N+N) => O(2N) => O(N) :P

import java.util.*;
class pairs
{
public static void main(String args[])
{
 int[] arr = new int[]{5,2,8,6,9,1,4,3};
 int sum = 9;
 Hashtable vals = new Hashtable();
 
 for(int i=0; i<arr.length;i++)
  vals.put(arr[i],arr[i]);

for(int i=0; i<arr.length;i++)
{ 
 if(vals.contains(sum-arr[i]))
 {
  
  System.out.println(arr[i]+" "+(sum-arr[i]));
  vals.remove(arr[i]);
  }
}
}
}

- liju.leelives July 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This solution to find only if two elements in the array sum to the given value

- oelsayed July 08, 2015 | Flag


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