Bloomberg | Phone | Number of ways to purchase oil

4776

I have applied for Bloomberg Software Engineer Grad position and asked me to schedule interview in a week.

There was one question and hackerrank coderpad (I was expecting a proper hackerrank assessment)

Question:

'm' amount of oil can be purchased from 'n' companies. Every company has 'k' capacity of oil to be sold, you can take zero or many times the quantity offered by each company. Give the maximum number of combinations possible.

For examples:
There are three companies: A, B, C

A - 10
B - 15
C - 50

Target: 60

Number of Combinations: 4 {[10,50], [15,45], [20,40],[10,20,30]

I was able solve the question by priting all combination but my count was not updating, I was debugging the code but he told he didn't know java at all so we can move on. I thought I would get through, but they rejected me.

I hope this expereince might be useful for you!

Approach, I took:

I have generated multiples of all quantities in a list till the target amount. Then generated all possible subsets and for every subset, I was calculating sum of all elements in the subset. Later, compared sum with target, I have incremented count.

public class Solution {
    static Integer count=new Integer(0); // Global
    public static void main(String args[] ) throws Exception {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        int [] given= {10,15,50};
        int target=60;
        List<Integer> quantities=new ArrayList<>();
        
        for(int i=0;i<given.length;i++) {
            int multiple=1;
            while(given[i]*multiple < target)  {
                if(!quantities.contains(given[i]*multiple))
                    quantities.add(given[i]*multiple);
                multiple++;
            }
        }
        //System.out.println(quantities);
        List<Integer> temp=new ArrayList<>();
        subset(quantities, temp, 0, target);
        System.out.println(count);


    }


public static void  subset(List<Integer> quantities, List<Integer> temp, int index, int target) {
    int sum=0;
    for(Integer i: temp) sum+=i;
    if(sum==target) {
        count++;
    }
    for(int i=index; i<quantities.size();i++) {
        temp.add(quantities.get(i));
        subset(quantities, temp, i+1, target);
        temp.remove(new Integer(quantities.get(i)));
    }
}

Edit:

Thanks xiaoxiang615!

Comments (7)