Amazon Interview Question
SDE-3sCountry: United States
Interview Type: Phone Interview
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;
}
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;
List<Integer> numbers = new LinkedList<>();
subsets(0, target, numbers);
return results;
}
public void subsets(int index, int target, List<Integer> numbers){
if(target == 0){
results.add(numbers);
}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;
workItems = new LinkedList<>();
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){
workItems.add(workItem);
subsets(index + 1, money - workItem.money, utility + workItem.utility);
workItems.remove(workItems.size() - 1);
}
}else{
if(utility > maximum){
maximum = utility;
maximumList = new LinkedList<>();
for(WorkItem workItem : workItems)
maximumList.add(workItem);
}
}
}
}
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;
maximumList = new LinkedList<>();
for(WorkItem workItem : workItems.values())
maximumList.add(workItem);
}
}
}
}
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();
subset.add(arr[i]);
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);
}
}
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>();
tempSub.add(currentTotal);
if (currentTotal < totalNumber) {
for(int k = i+1; k < array.length;k++){
int t = k;
currentTotal = array[i];
tempSub = new ArrayList<Integer>();
tempSub.add(currentTotal);
while(currentTotal < totalNumber && t < array.length){
tempSub.add(array[t]);
currentTotal += array[t];
t++;
}
if (currentTotal == totalNumber) subArray.add(tempSub);
}
}
else if (currentTotal == totalNumber) subArray.add(tempSub);
}
return subArray;
}
}
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);
}
}
First can be solved by basic recursion.
- gsharma34065 October 15, 2016