## Amazon Interview Question for SDE-3s

• 1
of 1 vote

Country: India

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

subset sum problem is NP complete. There is a pseudo polinomial algorithm ala knapsack to solve it for small sums - which has limitted value in parctice.

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

Below is the code that works for any set of elements.
If we should somehow use the knowledge that the elements are 1,2,..,9, maybe, we should pre-compute all of possible results and store them in "n,k" => sets hashmap.

``````#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<vector<int>> SumSets(vector<int> const &a, int n, int16_t k,
unordered_map<uint64_t, vector<vector<int>>> &memo, int16_t idx = 0)
{
vector<vector<int>> out;
if (k < 0 ||
n < 0 ||
idx < 0)
{
return out;
}
if (k == 0 &&
n == 0)
{
out.resize(1);
return out;
}
if (idx > a.size()) {
return out;
}

uint64_t memo_key = (static_cast<uint64_t>(k) << 48) | (static_cast<uint64_t>(idx) << 32) | n;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}

out = SumSets(a, n - a[idx], k - 1, memo, idx + 1);
for (auto &s : out) {
s.push_back(a[idx]);
}
auto skip = SumSets(a, n, k, memo, idx + 1);
out.insert(out.end(), skip.begin(), skip.end());

memo[memo_key] = out;
return memo[memo_key];
}

int main()
{
unordered_map<uint64_t, vector<vector<int>>> memo;
auto out = SumSets({1, 2, 3, 4, 5, 6, 7, 8, 9}, 9, 3, memo);
for (auto &s : out) {
for (int n : s) {
cout << n << ", ";
}
cout << "\n";
}
}``````

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

import copy

def get_sets_of_sum(numbers, k, possible_set, result):
if k == 0:
if sorted(possible_set) not in result :
result.append( sorted(possible_set))
elif k < 0:
return
else:
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers = copy.copy(numbers)
new_numbers.remove(n)

get_sets_of_sum(new_numbers, k-n, new_set, result)

k = 10
possible_set = []
numbers = list(range(1,10))
result = []
get_sets_of_sum(numbers, k, possible_set, result)

for r in result:
print(r)

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

``````import copy

def get_sets_of_sum(numbers, k, possible_set, result):
if k == 0:
if sorted(possible_set) not in result :
result.append( sorted(possible_set))
elif k < 0:
return
else:
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers = copy.copy(numbers)
new_numbers.remove(n)

get_sets_of_sum(new_numbers, k-n, new_set, result)

k = 10
possible_set = []
numbers = list(range(1,10))
result = []
get_sets_of_sum(numbers, k, possible_set, result)

for r in result:
print(r)``````

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

``````import copy

def get_sets_of_sum(numbers, k, possible_set, result):
if k == 0:
if sorted(possible_set) not in result :
result.append( sorted(possible_set))
elif k < 0:
return
else:
for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers = copy.copy(numbers)
new_numbers.remove(n)

get_sets_of_sum(new_numbers, k-n, new_set, result)

k = 10
possible_set = []
numbers = list(range(1,10))
result = []
get_sets_of_sum(numbers, k, possible_set, result)

for r in result:
print(r)``````

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

// Practicas.cpp : Defines the entry point for the console application.
//

``````#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
int k = 3;
int n = 18;
int d[] = {1,2,3,4,5,6,7,8,9};
int *indx = new int[k];

for(int i=0; i<k; i++)
indx[i]=i;

int ci=k-1;
while(indx[0] < 9 - k)
{
while(indx[ci] < 9)
{
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}
indx[ci]++;
}
for(int i=k-1; i>0; i--)
{
if(indx[i] == 9)
{
indx[i - 1] ++;
for(int j=i; j< k;j++)
indx[j] = indx[j - 1] + 1;
}
}

}
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}

return 0;
}``````

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

// Practicas.cpp : Defines the entry point for the console application.
//

``````#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
int k = 3;
int n = 18;
int d[] = {1,2,3,4,5,6,7,8,9};
int *indx = new int[k];

for(int i=0; i<k; i++)
indx[i]=i;

int ci=k-1;
while(indx[0] < 9 - k)
{
while(indx[ci] < 9)
{
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}
indx[ci]++;
}
for(int i=k-1; i>0; i--)
{
if(indx[i] == 9)
{
indx[i - 1] ++;
for(int j=i; j< k;j++)
indx[j] = indx[j - 1] + 1;
}
}

}
int tmp=0;
for(int i=0; i<k; i++)
tmp+=d[indx[i]];
if(tmp==n)
{
for(int i=0; i<k; i++)
printf("%i ", d[indx[i]]);
printf("\n");
}

return 0;
}``````

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

``````public static List<List<Integer>> findKElementsSum(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
for (int i = 1: i < n - 2; i++ ) {
for (int J = i + 1: j < n - 1; j++ ) {
int r = n - (i + j);
if (r != i && r != j && r <= n && r > 0) {
}
}
}
return list;
}``````

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

``````private Set<Set<Integer>> findkElementsSum(int[] list, int n, int k) {
return combinations(list, k).stream().filter(sumIs(n)).collect(toSet());
}

private Set<Set<Integer>> combinations(int[] list, int k) {
for (int i = 0; i < k; i++) {
Set<Set<Integer>> result = new HashSet<>();
for (Set<Integer> lowerCombination : finalAnswer) {
for (int element : list) {
HashSet<Integer> biggerCombination = new HashSet<>(lowerCombination);
if (!biggerCombination.contains(element)) {
}
}
}
}
}

private Predicate<Set<Integer>> sumIs(int n) {
return integers -> sum(integers) == n;
}

private Integer sum(Set<Integer> integers) {
return integers.stream().reduce(0, (a, b) -> a + b);
}``````

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

private Set<Set<Integer>> findkElementsSum(int[] list, int n, int k) {
return combinations(list, k).stream().filter(sumIs(n)).collect(toSet());
}

private Set<Set<Integer>> combinations(int[] list, int k) {
for (int i = 0; i < k; i++) {
Set<Set<Integer>> result = new HashSet<>();
for (Set<Integer> lowerCombination : finalAnswer) {
for (int element : list) {
HashSet<Integer> biggerCombination = new HashSet<>(lowerCombination);
if (!biggerCombination.contains(element)) {
}
}
}
}
}

private Predicate<Set<Integer>> sumIs(int n) {
return integers -> sum(integers) == n;
}

private Integer sum(Set<Integer> integers) {
return integers.stream().reduce(0, (a, b) -> a + b);
}

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

import copy

def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)

new_numbers = copy.copy(numbers)

for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers.remove(n)

get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)

k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)

for r in result:
print(r)

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

``````import copy

def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)

new_numbers = copy.copy(numbers)

for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers.remove(n)

get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)

k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)

for r in result:
print(r)``````

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

``````import copy

def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)

new_numbers = copy.copy(numbers)

for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers.remove(n)

get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)

k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)

for r in result:
print(r)``````

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

``````import copy

def get_sets_of_sum(numbers, k, sum, possible_set, result):
if k == 1 and sum in numbers:
possible_set.append(sum)
result.append(possible_set)

new_numbers = copy.copy(numbers)

for n in numbers:
new_set = copy.copy(possible_set)
new_set.append(n)

new_numbers.remove(n)

get_sets_of_sum(new_numbers, k - 1, sum - n, new_set, result)

k = 3
sum = 9
possible_set = []
numbers = [i for i in range(1, 10)]
result = []
get_sets_of_sum(numbers, k, sum, possible_set, result)

for r in result:
print(r)``````

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.