Amazon Interview Question Software Engineer / Developers
Country: -
Here M < K and N < K
If you GCD of M,N it will be < K
and your algo will say it won't work
Seems using GCD is good idea to test if a solution exist. As here, M = 3, N = 4, GCD(3,4) = 1 which divides K=5. Hence, solution exists. On the other hand, if M = 6, N = 9, and K = 8; no solution exists.
Your answer doesn't make sense to me, in the example you gave the GCD between 3 and 4 is 1, which just happens to be the difference between those numbers. It's just a coincidence that it works.
Here's a counter example:
Look at M=2, N=7, K=8.
GCD(2,7) = 1, and 8%1 = 0, so your algorithm would report that you can fill an 8 litre jug, which is the wrong answer.
I think recursion is the way to go.
bool canFillJug(int jugSize1, int jugSize2, int finalJugSize) {
int jugSizeDiff = abs(jugSize1 - jugSize2);
return (canFillJug(jugSize1, jugSize2, finalJugSize - jugSize1) ||
canFillJug(jugSize1, jugSize2, finalJugSize - jugSize2) ||
canFillJug(jugSize1, jugSize2, finalJugSize - jugSizeDiff));
}
-1 for the previous anonymous, since we can repeat four times the actions of filling the 2 liter jug and pouring into the 8.
@anonymous (proposing recursive solution):
I doubt if you UNDERSTAND the problem. First do it, and then say what is WRONG or RIGHT. FYI, read it : perlmonks.org/?node_id=757452
It's a classic number theory problem.
I am agree with you Anon . I think finding GCD is the most suitable problem for this question .
M=2, N=7, K=8
Fill N (0,7)
Take out M and throw away (0,5)
Take out M and throw away (0,3)
Take out M and throw away (0,1)
Move N to M (1,0)
Fill N (1, 7)
That is how you get 8.
To get 9 you fill up both N and M.
I thought you can not get 10 because you don't have bucket K to pour stuff into...
However the GCD people seem to make it seem like you can get the 10 because you can fill the K while solving the problem (just use the 2 sized bucket 5 time)...
Consider this algorithm.
Lets say jug M and N currently have x1 and x2 amount of water. Naturally you start off with x1=x2=0.
At this point you can do one of them following.
1) Fill up M with water from outside
2) Fill up N with water from outside
3) Empty N if not empty already
4) Empty M if not empty already
5) Fill M from N as much as possible
6) Fill N from M as much as possible
So you could code a recursive algorithm. Each state can potentially branch to six other branches. Stop when you find a solution or when you have processed such a configuration before.
If you look at above solution as graph. Consider all possible configuration. Both jugs empty , first jug =1 liter second is empty etc etc. So there are M * N such jug configuration ( nodes ). From each node you can have six potential outgoing edges for each of the possible things you can do . The problem reduces to finding a path from (0,0) node to a solution node. A solution node for something like above problem is either
1,4
2,3
3,2
4,1
You are trying to solve a simple problem with complex ideas. I think you will end up eating amazon's time if you are hired. You are rejected by amazon.
BullShit, even if all amazon does is fill jugs with water. There will always be a problem with a simple solution that one will come up with a complex answer first.
To original anon, please don't get discouraged by idiotic comments like the above.
I guess all the computer science mumbo jumbo was too complicated for you. I have coded it in c++. Very simple if you understand. I will solve and print solutions to the cout.
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
class JugProblem
{
const int mTarget , mFirstCapacity , mSecondCapacity;
std::set< std::pair<int , int > > mProcessSolutions;
std::vector< std::pair<int , int > > mCurSolution;
public:
JugProblem( int target , int firstJug , int secondJug ):
mTarget(target) , mFirstCapacity(firstJug) , mSecondCapacity(secondJug){}
void Solve( int firstLevel = 0 , int secondLevel = 0)
{
std::pair<int,int> temp(firstLevel,secondLevel);
if ( mProcessSolutions.insert( temp ).second == true )
{
mCurSolution.push_back(temp);
if ( mTarget == ( firstLevel + secondLevel ) )
{
for_each (mCurSolution.begin(), mCurSolution.end(), PrintSolution);
std::cout << std::endl;
}
Solve( firstLevel , mSecondCapacity );
Solve( mFirstCapacity , secondLevel );
Solve( (firstLevel+secondLevel) % mFirstCapacity , 0 );
Solve( 0 , (firstLevel+secondLevel) % mSecondCapacity );
Solve( 0 , secondLevel );
Solve( firstLevel , 0 );
mCurSolution.pop_back();
}
}
static void PrintSolution( const std::pair<int , int >& cur )
{
std::cout << "[" << cur.first << "," << cur.second << "] ->";
}
};
int _tmain(int argc, _TCHAR* argv[])
{
JugProblem pr( 5 , 3 ,4 );
pr.Solve();
return 0;
}
For the particular problem it prints
[0,0] ->[0,4] ->[3,4] ->[1,0] ->[1,4] ->
[0,0] ->[0,4] ->[3,4] ->[1,0] ->[1,4] ->[2,0] ->[2,4] ->[0,2] ->[3,2] ->
Hi anonymous,
What's the running complexity of your solution? I tested with this input and ran the program for 30+ seconds (but no output).
K=10001 M=12345 N=212
as GCD (M,N) = 1, all K from 1 to M+N is possible to make. I guess your approach is not polynomial in worst case, which leads time limit. Any idea to make it run in polynomial time?
Thanks.
Code in Java
private static boolean measuringJars1(int jar1, int jar2,int value) {
//Can be further improvised to include multiples
if ((value == 0) || (value == Math.abs(jar1-jar2))) {
return true;
}
if (jar1 <= value) {
// select jar1 and continue with value-jar1 recursively
if (measuringJars1(jar1,jar2,value-jar1))
return true;
}
if (jar2 <=value) {
// select jar2 and continue with value-jar2 recursively
if(measuringJars1(jar1,jar2,value-jar2))
return true;
}
int diffCapacity = Math.abs(jar1-jar2);
if (value >= diffCapacity) {
int remValue = Math.abs(value - Math.abs(jar1-jar2));
if (measuringJars1(jar1,jar2,remValue))
return true;
}
return false;
}
Consider this test case...
M = 7, N = 3, K = 2
It is possible, but the code doesn't handle this scenario
This should help...
int diffCapacity2;
if(jar1 > jar2)
{
diffCapacity2 = jar2;
while(diffCapacity2 < jar1)
{
diffCapacity2 *= jar2;
}
diffCapacity2 -= jar1;
}
else
{
diffCapacity2 = jar1;
while(diffCapacity2 < jar2)
{
diffCapacity2 *= jar1;
}
diffCapacity2 -= jar2;
}
if (value >= diffCapacity2)
{
int remValue = Math.abs(value - diffCapacity2);
if (measuringJars1(jar1,jar2,remValue))
return true;
}
GCD solution is good and straightforward. Other solutions may not fit well here. Some guys only criticize others and don't even make an effort to post their ideas here.
M=5, N=3 and K=1. With the GCD solution it is possible to measure K but in reality it is not possible
it is possible
fill M [ 5 , 0]
pour M into N [ 2 , 3]
empty N [ 2 , 0]
pour M into N [ 0 , 2]
Fill M [ 5 , 2]
Pour M into N [ 4 , 3]
Empty M [ 4, 0]
Pour N into M [ 1 , 3]
Now you have 1 in the first jug
A solution based on GCD is sound. Here's a proof:
g := gcd(m,n) = a*m + b*n where a and b are nonzero integers and is the lowest such positive number that can be written in this form (Bezout's identity).
Obtaining k liters is possible if you can write k in the form k = x*m + y*n, where x and y are any integers.
First, show that if k%g = 0, you can obtain k liters:
k%g = 0 --> k = q*g = q*a*m + q*b*n. Thus you can obtain k liters by emptying and filling m and n.
Second, show if k%g is not 0, you cannot obtain k liters.
Proof by contradiction: k%g is not 0, but assume you can write k in the form k = x*n + y*m.
Since k%g > 0, k = q*g + r = q*(a*n+b*m) + r where 0 < r < g = a*m + b*n.
Thus k = x*n + y*m = q*a*n + q*b*m + r
--> (x-q*a)*n + (y-q*b)*m = r
Since 0 < r< a*m + b*n
--> 0 < (x-q*a)*n + (y-q*b)*m < a*m + b*n = g
However, this contradicts the statement that a*m + b*n = g is the lowest such number that can be written in this form.
Thus, if k%g is not 0, you cannot write k = x*m + y*n so you cannot obtain k liters.
#include<stdio.h>
void canfilljug(int jugsize1, int jugsize2, int total_litre){
if((total_litre%jugsize1==0)||(total_litre%jugsize2 == 0))
printf("yes it can be done with these jugs\n");
else if(total_litre%gcd(jugsize1,jugsize2)==0)
printf("yes it can be done with these jugs(gcd)\n");
else
printf("it can't be\n");
}
int gcd(int a, int b){
if(a==0)
return b;
else if(b==0)
return a;
else
return gcd(b,a % b);
}
main(){
int jugsize1,jugsize2,total_litre,check;
printf("enter the jugsize and total litre\n");
scanf("%d%d%d",&jugsize1,&jugsize2,&total_litre);
canfilljug(jugsize1,jugsize2,total_litre);
}
/* i think this code gives all the correct answers. And it is implemented using GCD idea*/
#include<stdio.h>
void canfilljug(int jugsize1, int jugsize2, int total_litre){
if((total_litre%jugsize1==0)||(total_litre%jugsize2 == 0))
printf("yes it can be done with these jugs\n");
else if(total_litre%gcd(jugsize1,jugsize2)==0)
printf("yes it can be done with these jugs(gcd)\n");
else
printf("it can't be\n");
}
int gcd(int a, int b){
if(a==0)
return b;
else if(b==0)
return a;
else
return gcd(b,a % b);
}
main(){
int jugsize1,jugsize2,total_litre,check;
printf("enter the jugsize and total litre\n");
scanf("%d%d%d",&jugsize1,&jugsize2,&total_litre);
canfilljug(jugsize1,jugsize2,total_litre);
}
As you can see, my solution has nothing to do with GCD:
bool IsKFilable(int K, int M, int N)
{
// rationale: look for integers a and b,
// at least one of them positive,so that
// K == a*M + b*N;
// therefore, (1)-->
// K%M == (b*N)%M;
// and (2)-->
// K%N == (a*M)%N;
for (int b = 0; b < M; b++)
{
if (K%M == (b*N)%M) return true;
}
for (int a = 0; a < N; a++)
{
if (K%N == (a*M)%N) return true;
}
return false;
}
another amazon moronic puzzle. i am sick of it. do they want programmers or rocket scientists ... yuckkkkk!!!
It is possible to fill K > M+N also.
take M = 7, N = 2, GCD = 1.
For K = 10 (> M+N)
we can fill like this:
pour 7 ltr into jug-K using jug-M
pour 2 ltr into jug-K using Jug-N
so jug-K has 9 ltr now.
fill jug-N and pour into M three times, so M has 6 ltr now.
fill jug-N and pour into jug-M until it is full, so Jug-N has one ltr now.
pour this one ltr into jug-K.
so jug-K has 10 ltr now.
//We will adopt a greedy strategy
public static boolean isVolumePossible(int volume, int mLitres, int nLitres){
int sum = mLitres + nLitres;
int max = Math.max(mLitres, nLitres);
int diff = Math.abs(mLitres - nLitres);
int min = Math.min(mLitres, nLitres);
int max1 = Math.max(diff, min);
int max2 = Math.min(diff, min);
if(volume >= sum){
volume = volume % sum;
if(volume == 0){
return true;
}
}
if(volume >= max){
volume = volume % max;
if(volume == 0){
return true;
}
}
if(volume >= max1){
volume = volume % max1;
if(volume == 0){
return true;
}
}
if(volume >= max2){
volume = volume % max2;
if(volume == 0){
return true;
}
}
return false;
}
public static void main(String[] args){
System.out.println(isVolumePossible(5,4,3));
}
The idea is to find the GCD of M and N. We can use Euclid's algorithm for that.
- Random September 21, 2011Let us say GCD(M,M) = R, that we have found using the algorithm. Then if K%R == 0, K litres can be formed.