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

Comment hidden because of low score. Click to expand.
0

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?

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

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.

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)
{
return lst; ;
}
int[] inp = arr.Select(x => x).OrderBy(x => x).ToArray();//sorted
if (inp.Length == 0)
{
return lst; ;
}

for (int i = 0; i < inp.Length; i++)
{
int num1 = inp[i];
//if (num1 > res)
//    break;
if (num1 == res)
{
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];
}
}

}

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}

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)
{
return lst; ;
}
int[] inp = arr.Select(x => x).OrderBy(x => x).ToArray();//sorted
if (inp.Length == 0)
{
return lst; ;
}

for (int i = 0; i < inp.Length; i++)
{
int num1 = inp[i];
//if (num1 > res)
//    break;
if (num1 == res)
{
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];
}
}

}

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

Comment hidden because of low score. Click to expand.
0

``````if (inp.Length == 0)
{
return lst; ;
}``````

The above is redundant

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) {
}
for (int j = 0; j < size; j++) {
if (sum.get(j) + arr[i] <= K) {
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));
}
}
}

}``````

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

Comment hidden because of low score. Click to expand.
0

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

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.

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