## Amazon Interview Question for SDE-3s

Country: United States
Interview Type: Phone Interview

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

First can be solved by basic recursion.

``````void printSubsetsUtil(int a[], int i, int n, vector<int> &v, int sum)
{

if(sum < 0 || i > n)
return;

if(sum == 0)
{
for(int j = 0; j < v.size(); j++)
cout << v[j] << " ";
cout << endl;
return;
}

printSubsetsUtil(a, i+1, n, v, sum);

v.push_back(a[i]);
printSubsetsUtil(a, i+1, n, v, sum-a[i]);
v.pop_back();

}

void printSubsets(int a[], int n, int sum)
{
vector<int> v;
printSubsetsUtil(a, 0, n, v, sum);
}
int main()
{
int a[] = {1, 2, 3, 4, 5};

int n = sizeof(a)/sizeof(a[0]);

printSubsets(a, n, 5);

return 0;
}``````

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

void printSubsetsUtil(int a[], int i, int n, vector<int> &v, int sum)
{

if(sum < 0 || i > n)
return;

if(sum == 0)
{
for(int j = 0; j < v.size(); j++)
cout << v[j] << " ";
cout << endl;
return;
}

printSubsetsUtil(a, i+1, n, v, sum);

v.push_back(a[i]);
printSubsetsUtil(a, i+1, n, v, sum-a[i]);
v.pop_back();

}

void printSubsets(int a[], int n, int sum)
{
vector<int> v;
printSubsetsUtil(a, 0, n, v, sum);
}
int main()
{
int a[] = {1, 2, 3, 4, 5};

int n = sizeof(a)/sizeof(a[0]);

printSubsets(a, n, 5);

return 0;
}

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

I made a solution for each problem in Java. Although I didn't test the code you can get the idea.

First problem:

``````public class Subsets{

private int size;
private int[] array;

private List<List<Integer>> results = new ArrayList<>();

public List<List<Integer>> subsets(int[] array, int target){
size = array.length;
this.array = array;

subsets(0, target, numbers);

return results;

}

public void subsets(int index, int target, List<Integer> numbers){
if(target == 0){
}else{
if(index < size){
subsets(index + 1, target - array[index], numbers;
subsets(index + 1, target, new LinkedList<>();

}
}

}

}``````

Second one:

``````public class Subsets{

private int size;
private WorkItem[] array;

private int maximum;
private List<WorkItem> maximumList;

private List<WorkItem> workItems;

public List<WorkItem> subsets(WorkItem[] array, int money){
size = array.length;
this.array = array;

subsets(0, money, 0);

return results;

}

public void subsets(int index, int money, int utility){
if(index < size){

subsets(index + 1, money, utility);

WorkItem workItem = array[index];
//We suppose that there are no negative costs
if(money >= workItem.money){
subsets(index + 1, money - workItem.money, utility + workItem.utility);
workItems.remove(workItems.size() - 1);
}

}else{
if(utility > maximum){
maximum = utility;
for(WorkItem workItem : workItems)
}

}

}

}``````

Third one (I assume that WorkItem has a field "with", which contains the name and the utility of the related item:

``````public class Subsets{

private int size;
private WorkItem[] array;

private int maximum;
private List<WorkItem> maximumList;

private HashMap<String, WorkItem> workItems;

public List<WorkItem> subsets(WorkItem[] array, int money){
size = array.length;
this.array = array;

workItems = new HashMap<>();
subsets(0, money);

return results;

}

public void subsets(int index, int money){
if(index < size){

subsets(index + 1, money);

WorkItem workItem = array[index];
//We suppose that there are no negative costs
if(money >= workItem.money){
workItems.put(workItem.name, workItem);

subsets(index + 1, money - workItem.money);

workItems.remove(workItem.name);
}

}else{
int utility = 0;
for(WorkItem workItem : workItems.values()){
if(workItem.with != null && workItems.containsKey(workItem.with.name))
utility += workItem.with.utility;
else
utility += workItem.utility;

}

if(utility > maximum){
maximum = utility;
for(WorkItem workItem : workItems.values())
}

}

}

}``````

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

``````import java.util.ArrayList;
import java.util.List;

public class SubsetSum{

public SubsetSum(int[] arr, int sum) {
if (sum <= 0 ) {
return;
}
subsetSumUtil(arr, 0, sum, new ArrayList<Integer>());
}

public static void subsetSumUtil(int[]arr, int index, int sum, List<Integer> subset) {
if (sum < 0) {
return;
}

if (sum == 0){
printList(subset);
}

for (int i = index; i < arr.length; ++i) {
int indexInserted = subset.size();
subsetSumUtil(arr, i+1, sum- arr[i], subset);
subset.remove(indexInserted);
}
}

public static void printList(List<Integer> list){
System.out.println(list.toString());
}

public static void main(String args[]){
int[] arr = {1,2,3,4,5};
int sum = 5;
SubsetSum s = new SubsetSum(arr, sum);

}

}``````

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

First one;

``````class SubSets{
int[] array;
SubSets(){
array = new int[]{1,2,3,4,5};
}

public ArrayList<ArrayList<Integer>> getSubs(int totalNumber){
ArrayList<ArrayList<Integer>> subArray = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> tempSub = new ArrayList<Integer>();
Integer currentTotal;
for(int i = 0;i < array.length-1;i++){
currentTotal = array[i];
tempSub = new ArrayList<Integer>();
if (currentTotal < totalNumber) {
for(int k = i+1; k < array.length;k++){
int t = k;
currentTotal = array[i];
tempSub = new ArrayList<Integer>();
while(currentTotal < totalNumber && t < array.length){
currentTotal += array[t];
t++;
}
}
}
else if (currentTotal == totalNumber) subArray.add(tempSub);
}

return subArray;
}
}``````

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

``````public class Budget {

int maxBudget, maxUtility;
int[] cost, utility;
String result;

public Budget(int maxBudget, int[] cost, int[] utility) {

this.maxBudget = maxBudget;
this.cost = cost;
this.utility = utility;
}

public static void main(String[] args) {

int[] cost = {50, 10, 20, 5, 9};
int[] utility = {50, 50, 50, 50, 50};
int maxBudget = 25;

Budget budget = new Budget(maxBudget, cost, utility);

budget.calc();

System.out.println("result: " + budget.result + " - maxUtility: " + budget.maxUtility);
}

private void calc() {

calc(0, 0, 0, "");
}

private void calc(int cCost, int cUtility, int i, String s) {

if (i >= cost.length)
return;

int tCost = cCost + cost[i];

int tUtility = cUtility + utility[i];

if (tCost <= maxBudget) {

String tS = s + "," + i;

calc(tCost, tUtility, i + 1, tS);

if (tUtility > maxUtility) {
maxUtility = tUtility;
result = tS;
}
}
calc(cCost, cUtility, i + 1, s);
}

}``````

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.