Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
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);
}
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.
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}
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
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));
}
}
}
}
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]);
}
}
}
}
- WhoCares July 07, 2015