## Amazon Interview Question for Software Engineer Interns

• -2

Country: United States

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

task is a bit unclear, what do you mean "If a number is used once, it must not be used again" ?
What if we have an array 6 5 4 3 2 1 and sum = 10.
What output should be?
First, it is 6 4.
But what about 6 3 1 ? We already used 6, so, can we use it in case of 6 3 1 ?
And then, what about 4 3 2 1 ? We already used 4 in first output, what should we do now?
And what about 5 3 2 ?
And so on.

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

Its just pairs of numbers. My bad!

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

thank you for clarification.
If the task is about to find only pairs then it is quite straightforward O(n) solution as follows (c#).

``````private static List<int[]> GetCombinationsOfTwo( int[] arr, int sum ) {
var res = new List<int[]>();
var dic = new Dictionary<int, int>();

for ( int i = 0; i < arr.Length; i++ ) {
if ( arr[ i ] > sum || dic.ContainsKey( arr[ i ] ) ) { continue; }
if ( dic.ContainsKey( sum - arr[ i ] ) ) {
dic[ sum - arr[ i ] ]++;
continue;
}
dic[ arr[ i ] ] = -1;
}

foreach ( var key in dic.Keys ) {
if ( dic[ key ] >= 0 ) {
res.Add( new [] { key, sum - key } );
}
}
return res;
}``````

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

@zr.roman: Correct me if I'm wrong, but your solution assumes that the input array is sorted. If it's not, the code will not work.

Here is what I came up with:

``````void find_combination(vector<int> arr, int sum)
{
vector<int> map(10);
//set default values to 0.
fill(map.begin(), map.end(), 0);

//1-insert items in map O(n)
for(int i=0;i<arr.size();i++)
{
map[ arr[i] ]=1;  //key is the element and value is a flag 1.
}

for(int i=0;i<arr.size();i++)
{
if(map[ sum - arr[i] ] !=0)
{
cout<<arr[i]<<"-"<<sum-arr[i]<<endl;
map[sum-arr[i]]=0; //so we don't use this again
map[arr[i]]=0; //so we don't use this again
}
}

}``````

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

no, that is not correct, my code does not contain any assumptions.
Array is expected to be arbitrary.

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

As I understand the problem is:

You're given an array has n elements and a number k. Output all the combination such that sum is equal k and each element is used at most one time.

Examples:
Input:
array = {6, 4, 4, 3, 1, 7}
k = 10

Output (any order):
6 4
6 3 1
3 7

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

if the input were {6,4,4,5,5,3,1,7}
would 5 5 be an accepted output?
I would think yes.
if the input were {6,4,4,5,3,1,7}
then I'd think 5 5 is not an accepted output

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

Yes. I think so.

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

Its just combinations of length 2

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

``````For pairs only, the following wll give o(n) time

int assoc[n]
for(i=0;i<n;i++)
if(assoc[sum - a[i]])
{
printf("%d %d ",a[i],sum - a[i];
assoc[sum - a[i]] = 0;
}
else
assoc[a[i]] = 1;``````

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

what if sum -a[I] > n? in that case, assoc[sum - a[I] ] would throw out of index error

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

I think your code might fail for 64644

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

Create a hashmap with non repeating element except for element sum/2 for which we maintain count
loop through the hasmap from beginning and find the other element by
sum - currentelement
whichever elements pairs to sum..set those values to zero.hence while looping if we encounter zero we skip that and move on to next element.

If we encounter element equal to sum/2 and counter greater than or equal to 2 ,we set the count to zero after considering the pair once.

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

If I give input as 7,6,3,4,5,5,2,8,5,5 the output will be
Pair:7,3
Pair:6,4
Pair:5,5
Pair:2,8
Number of Combinations:4

public class SumOfCombinations {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] numbers = in.nextLine().split(",");
int sum = in.nextInt();
int combinations = 0;
Map<Integer,Integer> mappings = new HashMap<>();
Set<Integer> unique = new HashSet<>();
for(int i=0;i<numbers.length;i++){
int key = Integer.parseInt(numbers[i]);
if(mappings.containsKey(key) && !unique.contains(key)){
int value = mappings.get(key);
if(value == sum-key){
++combinations;
System.out.println("Pair:"+value+","+key);
}
}else if(!mappings.containsKey(key)){
mappings.put(sum-key, key);
}
}
System.out.println("Number of Combinations:"+combinations);
}
}

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

O(n) time - Code in Java

Here if same no is repeated n times then it will use number n times to find sum

``````private static void findSumPairsLinear(int[] a,int sum){
Map<Integer,Node> data=new HashMap<Integer,Node>();
for(int i=0;i<a.length;i++){
if(null==data.get(a[i])){
data.put(a[i], new ArrayProblems().new Node(1,i));
}else{
data.get(a[i]).setCount(data.get(a[i]).getCount()+1);
}
}

for(int i=0;i<a.length;i++){
if(data.get(sum-a[i])!=null){
Node pair1=data.get(sum-a[i]);
Node pair2=data.get(a[i]);
if(sum-a[i]==a[i] && pair1.getCount()<2){
continue;
}
System.out.println("Pair is -> "+a[i]+" "+a[pair1.getIndex()]);
if(pair1.getCount()==1){
data.remove(sum-a[i]);
}else{
pair1.setCount(pair1.getCount()-1);
}
if(pair2.getCount()==1){
data.remove(a[i]);
}else{
pair2.setCount(pair2.getCount()-1);
}
}
}
}``````

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

``````typedef vector<int> array
vector<array> findNumberForSum(vector<int> arr, int sum)
{
vector<array> result;
vector<int> x;
x.push_back(0);
result.push_back(x);
for(vector<int>::iterator it= arr.begin();it!=arr.end();it++)
{
int len = result.size();
for(int it2=0; it2<len;it2++)
{
if(result[it2][result[it2].size()-1]+*it <=sum)
{
vector<int> temp(result[it2]);//this array contains elements that add less than or
//equal to sum followed by sum of integers present in
// the array
temp.push_back( result[it2][result[it2].size()-1] + *it);//insert new sum
temp[temp.siz()-2] = *it;
}

}
}
for(int i-0;i<result.size();i++)
{
if(result[i][result[i].size()-1] != sum)
{
result.erase(result.begin()+i);
}
}
return result;
}``````

}

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

modify the above code
before the code "for(vector<array>::iterator it2= result.begin();it2!=result.end();it2++)"
calculate size of result into variable z.
make the loop run until z number of elements

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

public static void main(String[] args)
{

int[] a = {6,4,5,5};
int sum =10;
int length = a.length;
System.out.println(length);
HashMap<Integer, Integer> arrayitem = new HashMap<Integer, Integer>();
for(int i=0;i<length;i++) {
if(!arrayitem.containsValue(a[i])) {

arrayitem.put(i,a[i]);
}
}
HashMap<Integer, Integer> finalpairs = new HashMap<Integer, Integer>();
System.out.println(arrayitem);
int size = arrayitem.size();
System.out.println(size);
for(int i=0;i<size;i++) {
int value = sum-a[i];
if(arrayitem.containsValue(value) && !finalpairs.containsKey(value) && !finalpairs.containsValue(value)){
System.out.println(value + "and"+ a[i]);
finalpairs.put(value,a[i]); }
else
i++;

}
}

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

public static void main(String[] args)
{
int[] a = {6,4,5,5};
int sum =10;
int length = a.length;
System.out.println(length);
HashMap<Integer, Integer> arrayitem = new HashMap<Integer, Integer>();
for(int i=0;i<length;i++) {
if(!arrayitem.containsValue(a[i])) {

arrayitem.put(i,a[i]);
}}
HashMap<Integer, Integer> finalpairs = new HashMap<Integer, Integer>();
System.out.println(arrayitem);
int size = arrayitem.size();
System.out.println(size);
for(int i=0;i<size;i++) {
int value = sum-a[i];
if(arrayitem.containsValue(value) && !finalpairs.containsKey(value) && !finalpairs.containsValue(value)){
System.out.println(value + "and"+ a[i]);
finalpairs.put(value,a[i]); }
else
i++;
} }

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

HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
List<List<Integer>> res = new ArrayList<List<Integer>>();

for(int i=0;i<array.length;i++){
if(map.get(array[i]) == null){
map.put(array[i],1);
}else{
map.put(array[i],map.get(array[i]) + 1);
}
}
for(Integer i : map.keySet()){
if(map.get(sum - i) != null){
List<Integer> list = new ArrayList<Integer>();
if(map.get(sum - i) == 1){
map.remove(sum - i);
}else{
map.put(sum - i,map.get(sum - i) - 1);
}
}

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

``````// Given an array nums[], return a list containing all non-duplicated numbers that add up to sum.
// Time complexity O(n).
public List<List<Integer>> 2sum(int[] nums,int sum){
HashMap<Integer,Integer> map = new HashMap<>();
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums.length == 0)
return res;

// Put all numbers into a hashmap where key equals nums[i],
// and value equals existing times of nums[i].
for(int i=0;i<nums.length;i++){
if(map.get(nums[i]) == null){
map.put(nums[i],1);
}else{
map.put(nums[i],map.get(nums[i])+1);
}
}

// Use for each loop and hashmap to look for (sum - i).
// Each time remove used numbers, and keep looping until all key-value mappings removed.
while(!map.isEmpty()){
for(Integer i : map.keySet()){
if(map.get(sum - i) != null){
if(i != sum - i){
List<Integer> list= new ArrayList<Integer>();
if(map.get(i) == 1){
map.remove(i);
}else{
map.put(i,map.get(i) - 1);
}
if(map.get(sum - i) == 1){
map.remove(sum - i);
}else{
map.put(sum - i,map.get(sum - i) - 1);
}
}else if(i == sum - i){
if(map.get(i) == 1){
map.remove(i);
}else if(map.get(i) > 1){
List<Integer> list= new ArrayList<Integer>();
map.put(i,map.get(i) - 2);
}
}
}else if(map.get(sum - i) == null){
map.remove(i);
}
}
}
return list;
}``````

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

public void sum(int[] nums,int target){
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0;i<nums.length;i++){
if(set.contains(nums[i])){
System.out.println("["+nums[i]+","+(target-nums[i])+"]");
}else{
}
}
return;
}

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

//C++
#include<iostream>
#include<map>
using namespace std;
void printPairs(int arr[], int arr_size, int sum)
{
int i, temp;
std::map<int,int> hMap;
std::map<int,int>::iterator it = hMap.begin();
std::map<int,int>::iterator foundPair;
for(i=0;i<arr_size;i++)
{
hMap.insert(std::pair<int,int>(arr[i],1));
}

for (it=hMap.begin(); it!=hMap.end(); ++it)
{
if(it->second)
{
foundPair = hMap.find(sum - it->first);
if((foundPair!=hMap.end()) )
{
foundPair->second =0;
cout<< sum - it->first<<" " <<it->first<<endl;
}
}
}
}

int main()
{
int A[] = {6,4,4,0};
int n = 10;
int arr_size = sizeof(A)/sizeof(A[0]);

printPairs(A, arr_size, n);

getchar();
return 0;
}

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

``````public static void findCombinationsOn(int[] intArray, int sum) {
Map<Integer, Integer> mappings = new HashMap<>();
for (int i = 0; i < intArray.length; i++) {
int key = intArray[i];
if(mappings.containsKey(key)){
int value = mappings.get(key);
System.out.println("Key : " + key+ "; Value : "+ value);
}else{
mappings.put(sum - key, key);
}
}``````

}

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

``````public static void findCombinationsOn(int[] intArray, int sum) {
Map<Integer, Integer> mappings = new HashMap<>();
for (int i = 0; i < intArray.length; i++) {
int key = intArray[i];
if(mappings.containsKey(key)){
int value = mappings.get(key);
System.out.println("Key : " + key+ "; Value : "+ value);
}else{
mappings.put(sum - key, key);
}
}
}``````

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

``````public List<List<Integer>> twoSumNew1(int[] arr,int target){

if(arr == null || arr.length<=1)
return Collections.EMPTY_LIST;
List<List<Integer>>  result = new ArrayList<List<Integer>>();
Hashtable<Integer,Boolean> ht = new Hashtable<Integer,Boolean>();
List<Integer> list = new ArrayList<Integer>();

for(int i=0;i<arr.length;i++){
list = new ArrayList<Integer>();
if(ht.containsKey(target-arr[i]) && !ht.get(target-arr[i])){
//System.out.println("Soln:"+ (target-arr[i])+","+arr[i]);
ht.put(target-arr[i], true);

}
else if(!ht.containsKey(arr[i]))
ht.put(arr[i],false);

if(!list.isEmpty())
}

return result;``````

}

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

``````public List<List<Integer>> twoSumNew1(int[] arr,int target){

if(arr == null || arr.length<=1)
return Collections.EMPTY_LIST;
List<List<Integer>>  result = new ArrayList<List<Integer>>();
Hashtable<Integer,Boolean> ht = new Hashtable<Integer,Boolean>();
List<Integer> list = new ArrayList<Integer>();

for(int i=0;i<arr.length;i++){
list = new ArrayList<Integer>();
if(ht.containsKey(target-arr[i]) && !ht.get(target-arr[i])){
//System.out.println("Soln:"+ (target-arr[i])+","+arr[i]);
ht.put(target-arr[i], true);

}
else if(!ht.containsKey(arr[i]))
ht.put(arr[i],false);

if(!list.isEmpty())
}

return result;``````

}

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

``````public List<List<Integer>> twoSumNew1(int[] arr,int target){

if(arr == null || arr.length<=1)
return Collections.EMPTY_LIST;
List<List<Integer>>  result = new ArrayList<List<Integer>>();
Hashtable<Integer,Boolean> ht = new Hashtable<Integer,Boolean>();
List<Integer> list = new ArrayList<Integer>();

for(int i=0;i<arr.length;i++){
list = new ArrayList<Integer>();
if(ht.containsKey(target-arr[i]) && !ht.get(target-arr[i])){
//System.out.println("Soln:"+ (target-arr[i])+","+arr[i]);
ht.put(target-arr[i], true);

}
else if(!ht.containsKey(arr[i]))
ht.put(arr[i],false);

if(!list.isEmpty())
}

return result;

}``````

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

import java.util.HashSet;

public class UniqueElementsSumstoNumber {
public static void main(String[] args) {
HashSet set = new HashSet();
int[] arr = {6,4,4,4};
int sum = 10;

for (int a : arr) { set.add(a); }
for (int a : arr) {
if (set.contains(sum - a)) {
System.out.println("[" + a + "," + (sum-a) + "]");
set.remove(a);
set.remove(sum-a);
}
}
}
}

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

``````import java.util.HashSet;

public class UniqueElementsSumstoNumber {
public static void main(String[] args) {
HashSet set = new HashSet();
int[] arr = {6,4,4,4};
int sum = 10;

for (int a : arr) {	set.add(a);	}
for (int a : arr) {
if (set.contains(sum - a)) {
System.out.println("[" + a + "," + (sum-a) + "]");
set.remove(a);
set.remove(sum-a);
}
}
}
}``````

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

import java.util.HashSet;

public class UniqueElementsSumstoNumber {
public static void main(String[] args) {
HashSet set = new HashSet();
int[] arr = {6,4,4,4};
int sum = 10;

for (int a : arr) { set.add(a); }
for (int a : arr) {
if (set.contains(sum - a)) {
System.out.println("[" + a + "," + (sum-a) + "]");
set.remove(a);
set.remove(sum-a);
}
}
}
}

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

Here is a recursive solution of it:

``````def subset_sum(numbers, target, partial = []):

s = sum(partial)

if s == target:
print( partial, '= ', s)

if s >= target:
return

for i in range(len(numbers)):

n = numbers[i]
remainings = numbers[i+1:]
subset_sum(remainings, target, partial + [n])

x = [6,4,4,6,5,1,9,2,3]
xSet = set(x)
print(x)
print(xSet)
subset_sum(list(xSet), 10)
subset_sum(list(xSet), 15)``````

output:
[6, 4, 4, 6, 5, 1, 9, 2, 3]
{1, 2, 3, 4, 5, 6, 9}
[1, 2, 3, 4] = 10
[1, 3, 6] = 10
[1, 4, 5] = 10
[1, 9] = 10
[2, 3, 5] = 10
[4, 6] = 10

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

Since searching in a HashSet is O(1) time

``````import java.util.HashSet;

public class SumEqualsK {
public static void main(String[] args) {
Integer [] arr = {6,4,4,3,1,7};
int k = 10;
HashSet<Integer> pair = new HashSet<Integer>();
for(int i = 0 ; i < arr.length ; i++){
if(!pair.contains(arr[i])){
if(pair.contains(k - arr[i])){
System.out.println(arr[i]+" "+(k-arr[i]));
}
}
}
}
}``````

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

I dont think it is possible to find a solution in O(n). If it was a pair then yes using a HashMap would help. But if it is more than 2 numbers adding to the sum, its a DP problem and cannot be solved using O(n)

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

``````package geek.array;

import java.util.Arrays;

public class CombinationForSum {

private void findSumOfArray(String str, int sum){
int n = str.length();
int[] A = new int[10];
for(int i=0;i<n;i++){
A[Integer.parseInt(""+str.charAt(i))]=1;
}
int totalOne = 0;
for(int i = 0;i<10;i++){
if(A[i]==1){
totalOne++;
}
}
int[] B = new int[totalOne];
int idx = 0;
for(int i =0;i<A.length;i++){
if(A[i]==1)
B[idx++]=i;
}

Arrays.sort(B);
int i=0;
int j=B.length-1;
while(i<=j){
if(B[i]+B[j]==sum){
System.out.println(B[i]+" and "+B[j]);
i++;
j--;
}
if(B[i]+B[j]>sum){
j--;
}else{
i++;
}
}
}
public static void main(String[] args) {
CombinationForSum combinationForSum = new CombinationForSum();
combinationForSum.findSumOfArray("6444", 10);
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi all,
I have no idea how you can print all the solutions in O(n) time. My solution is a worst case O(n^2) which is what you'd all expect.

We keep a trace of all the items that were ran through. Therefore, there are a lot of list creations, which end up being disposed of unused. Another way of doing this would be to populate a tree in which the nodes know their parents so we can trace it back to the root and print everything. I'll implement that version later.

To not have the same solution be printed twice, I first populate a dictionary with all the items in the array. Then, we pop the dictionary
1- if this item equal to the number we're looking for? if yes, print the trace
2- else, we subtract this element from the desiredSum and remove a count of this item from the dictionary, and pass these in the function recursively, with a new trace updated to have this item added.
3- in parallel, we look in the rest of the dictionary (pop this entry of the dictionary out) for a way to get this sum, recursively again.

``````public static void PrintListsSum(int [] A, int desiredSum)
{
Dictionary<int, int> dict = FillDict(A);
PrintListsSum(dict, desiredSum, new List<int>());
}

public static void PrintListsSum(Dictionary<int, int> dict, int desiredSum, List<int> trace)
{
if (desiredSum < 1 || dict.Count() == 0)
return;
else
{// first in dictionary is the right, print it
KeyValuePair<int, int> kvp = dict.First();
if (kvp.Key == desiredSum)
{
List<int> newTrace = Copy(trace);
PrintList(newTrace);
}
else
{
// if there are other count in the first element of dictionary
List<int> newTrace = Copy(trace);

if (kvp.Value > 1)
{
dict[kvp.Key]--;
PrintListsSum(dict, desiredSum - kvp.Key, newTrace);
dict[kvp.Key]++;// reverse the popping of the element
}
else
{// only one item left, remove the item from the dictionary
dict.Remove(kvp.Key);
PrintListsSum(dict, desiredSum - kvp.Key, newTrace);
}
}

// try the rest of the dictionary, this number is ignored
dict.Remove(kvp.Key);
PrintListsSum(dict, desiredSum, trace);
}
}

public static void PrintList(List<int> A)
{
for (int i = 0; i < A.Count(); i++)
{
Console.Write("{0} ", A[i]);
}

Console.WriteLine();
}``````

If I input

``PrintListsSum(new int[]{ 11, 4, 4, 2, 2, 1, 1,3,4,6,8,7,3,2,3,1,1,2,3,6,5,15,10,11,18}, 15);``

I get
11 4
11 2 2
11 2 1 1
11 1 1 1 1
11 1 3
4 4 4 2 1
4 4 4 1 1 1
4 4 4 3
4 4 2 2 2 1
4 4 2 2 1 1 1
4 4 2 2 3
4 4 2 1 1 3
...
5 10
15

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

``````Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();

for (int i = 0; i < array.length; i++) {

if (!set.contains(array[i])) {

if (map.containsKey(array[i])) {
System.out.println("combination at : " + map.get(array[i]) + " and : " + i);
}

map.put(sum - array[i], i);
}

}``````

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

this is just pairs, not all combinations

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

this is just pairs, not all combinations

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

This solution doesn't look correct. It doesn't include all possible solutions.

For instance, here's an input:

6, 6, 4, 3, 1.

The output was:
combination at : 0 and : 2,

but it doesn't include the print out for combination for the values at index 1, 3, 4. In fact, it doesn't look like it even accounts for combinations of length greater than 2.

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

this solution does not look correct.

It only finds combinations of length 2.

For instance, given this input:
{6,6, 4, 3, 1}

It will only find the combination at indices 0 and 2, but not 1, 3, 4.

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.