CareerCup

Assume (x1,y1) , (x2,y2), (x3,y3) are the ranges of the three coke machines.
You have a range (m,n).

As stated before, m < X < Y < n for some (X,Y) to be obtained by a linear combination of the three machines.

Which means K1*x1 + K2*x2 + K3*x3 (= X) > m and K1*y1 + K2*y2 + K3 * y3 (=Y) < n

Take the second equation , we need to find all (K1,K2,K3) < n Start from n-1 (assume everything is an integer here. If not then we can scale the numbers till they become integers).
For every (k1,k2,k3) which satisfies the second equation see if it also satisfies the first equation. If yes , the problem can be solved . If no, decrement Sigma Ki*Xi to n-2 and repeat the algorithm.

It is a brute force approach almost. But it solves definitely.

You have three coke machine volume intervals:
(arrange them by increasing max, so max1<max2<max3)
min1,max1
min2,max2
min3,max3

The desired interval is m,n
if a linear combination of the soda machines min,max is completely contained in m,n:
m<min<max<n then a solution is possible, otherwise it is not guaranteed.

Now all you have to do is check if such a linear combination exists, and
start with the machine with the lowest max:
min1,max1 -> is this contained in m,n ?
if not add next machine and so on...

class Interval {
    double min;
    double max;
    
    Interval(double min, double max) {
        this.min = min;
        this.max = max;
    }
}

static boolean isPossible(double n, double m, double min1, double max1, double min2, double max2, double min3, double max3) {
        
        ArrayList<Interval> queue = new ArrayList<Interval>();
        queue.add(new Interval(.0, .0));
        
        while (true) {
            Interval cur = queue.remove(0);
            if (cur.min <= m && m <= cur.max) {
                return true;
            } else if (cur.min > n) {
                return false;
            }
            
            Interval i1 = new Interval(cur.min+min1, cur.max+max1);
            Interval i2 = new Interval(cur.min+min2, cur.max+max2);
            Interval i3 = new Interval(cur.min+min3, cur.max+max3);
            queue.add(i1);
            queue.add(i2);
            queue.add(i3);
        }
    }

what do you mean by minimum soda volume ? can we have an example please ...

would be good if you add an example

It looks like another version of knapsack problem, where bag capacity could be size of cup...n and now we have to fill some coke +soda(m) from each machine......i am not sure if this is what they are expecting.....question doesnt look complete , as they did not mention any constraint....well i am just guessing it to be similar to knapsack ...:)

public boolean getCoke(int min1,int  max1,int  min2,int max2,int min3,int max3,int m,int n) {

int glasses1=0, glasses2=0, glasses3=0;

for(glasses1=0;glasses1 <= (m/min1)+1; glasses1++){

	for(glasses2=0;glasses2 <= (m/min2)+1; glasses2++){
	if(glasses1*min1+glasses2*min2 >=m && glasses1*max1+glasses2*max2 <=n)
		return true;
	
if(glasses1*max1+glasses2*max2 >n )
break;
glasses3=(m-(glasses1*min1+glaasses2*min2))/min3+1; 

if(glasses1*min1+glasses2*min2+glasses3*min3 >=m && glasses1*max1+glasses2*max2+glasses3*max3 <=n)
		return true;
}
}
return false;

}

we can take all 3 values and the target value in fraction.

X1/Y1, X2/Y2, X3/Y3 and X/Y

What we are targeting is creating a value between X/Y to 1 . If none of X1/Y1 is > X/Y then we cant solve this problem. Else we can.

E.g. target is 6,12
options are 2,5 1,3 8,9
using a combination of 2,5 (2/5 < 6/12) and 1,3 (1/3 < 6/12) we can always exceed the max 12 to get to a min 6. Whereas using 8,9 (8/9>6/12) or any combination of values with > 6/12 ratio, we can achieve 6,12.

For 
		A		B		C
		(2,5)	(8,12)	(3,6)
			
	Allowed range		
		1	2	3	4	5	6	7	8	9	10	11	12	13
			A   A   A   A
									B	B	B	B	B
				C	C	C	C
		
	Possible: union of these discrete values: { 2, 3, 4, 5,  8, 9, 10, 11, 12 }
		m has to be in this set
		where n >= m
	
	Basically a set problem

It's a set problem. The algorithm is -
1. Create a set S1 as union of [min1, max1], [2*min1, 2*max1], [3*min1, 3*max1] ... note that after some point (LCM of min1, max1), the set would be - [LCM, +inf]. e.g. for min1 = 3, max1=4, the set would be - [3,4]U[6,8]U[9,12]U[12,+inf].
2. Create set S2, S3, etc as unions as in step 1 (replace min1, max1 with mini, maxi).
3. Just see if there is any overlap of [m,n] with S1, S2, S3. If there is overlap, return true, otherwise false.
4. An additional check can be added at the beginning if n < min1, min2, min3 then return false to reduce complexity.

Class Machine {
	public int min;
	public int max;
	}

	Map<Integer, Map<Integer, Boolean>> resultCaching = new HashMap<>();
Boolean checkForPossibility(List<Machine> machines, integer m, integer n) {
	if (m<0) return false;
	if (n<=0) return true;
	if (resultCaching.get(m) != null && resultCaching.get(m).get(n) != null) {
		return resultCaching.get(m).get(n);
}

	boolean isPossible = false;
	for(int i =0 ;i<machines.size();i++) {
	if (machine.max > m) continue;
	//if max is filled
	int newm=m-machine.max;
	int newn = n-machine.max;
	//can we fill remaining part?
	boolean resA = checkForPossibility(machines, newm, newn);

	//if min is filled
	newm = m-machine.min;
	newn = m- machine.min;

	boolean resB = checkForPossibility(machines, newm, newn, index);
	isPossible = resA && resB;
	}

	//Store result in cachemap, then return
	return p=isPossible;
	}