Amazon Interview Question Software Engineer Interns
Country: United States
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;
}
@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
}
}
}
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
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
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;
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.
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;
unique.add(key);
System.out.println("Pair:"+value+","+key);
}
}else if(!mappings.containsKey(key)){
mappings.put(sum-key, key);
}
}
System.out.println("Number of Combinations:"+combinations);
}
}
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);
}
}
}
}
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;
}
}
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++;
}
}
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++;
} }
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>();
list.add(i);
list.add(sum - i);
res.add(list);
if(map.get(sum - i) == 1){
map.remove(sum - i);
}else{
map.put(sum - i,map.get(sum - i) - 1);
}
}
// 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>();
list.add(i);
list.add(sum - i);
res.add(list);
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>();
list.add(i);
list.add(i);
res.add(list);
map.put(i,map.get(i) - 2);
}
}
}else if(map.get(sum - i) == null){
map.remove(i);
}
}
}
return list;
}
//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;
}
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);
}
}
}
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);
}
}
}
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]);
list.add(target-arr[i]);
list.add(arr[i]);
ht.put(target-arr[i], true);
}
else if(!ht.containsKey(arr[i]))
ht.put(arr[i],false);
if(!list.isEmpty())
result.add(new ArrayList<Integer>(list));
}
return result;
}
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]);
list.add(target-arr[i]);
list.add(arr[i]);
ht.put(target-arr[i], true);
}
else if(!ht.containsKey(arr[i]))
ht.put(arr[i],false);
if(!list.isEmpty())
result.add(new ArrayList<Integer>(list));
}
return result;
}
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]);
list.add(target-arr[i]);
list.add(arr[i]);
ht.put(target-arr[i], true);
}
else if(!ht.containsKey(arr[i]))
ht.put(arr[i],false);
if(!list.isEmpty())
result.add(new ArrayList<Integer>(list));
}
return result;
}
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);
}
}
}
}
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);
}
}
}
}
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);
}
}
}
}
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
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]));
}
pair.add(arr[i]);
}
}
}
}
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);
}
}
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);
newTrace.Add(desiredSum);
PrintList(newTrace);
}
else
{
// if there are other count in the first element of dictionary
List<int> newTrace = Copy(trace);
newTrace.Add(kvp.Key);
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);
dict.Add(kvp.Key, 1);
}
}
// try the rest of the dictionary, this number is ignored
dict.Remove(kvp.Key);
PrintListsSum(dict, desiredSum, trace);
dict.Add(kvp.Key, kvp.Value);
}
}
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
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
for (int i = 0; i < array.length; i++) {
if (!set.contains(array[i])) {
set.add(array[i]);
if (map.containsKey(array[i])) {
System.out.println("combination at : " + map.get(array[i]) + " and : " + i);
}
map.put(sum - array[i], i);
}
}
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.
task is a bit unclear, what do you mean "If a number is used once, it must not be used again" ?
- zr.roman January 31, 2016What 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.