## Microsoft Interview Question

Software Engineer / DevelopersPrasanna - I think your solution is the correct one. This is actually based (somewhat) off the euclidean algorithm.

Basically, you want to find the variables in 5x + 3y = 4. You can use the euclidean algorithm to find 5x + 3y = gcd(5,3) = 1.

5 = 3(1) + 2

3 = 2(1) + 1

reversing this process...

1 = 3 - 2(1)

2 = 5 - 3(1)

1 = 3 - (5-3(1))(1)

= 3 - 5(1) + 3(1)

= 3(2) + 5(-1)

This tells you that you will need to fill the 3 quart jug 2 times and empty the 5 quart jug once in order to get 1 quart. To get quarts, it's just a matter of filling the 3 quart jug one more time.

Can you try it with a 25 quart jug and a 18 quart jug where you're trying to get 1 quart?

Hint: use the euclidean algorithm to find the x,y such that 25x + 18y = 1

1. Empty both containers

2. fill the 5q container

3. fill the 3q container with the water in the 5q container

you have 2quarters in the 5q container

4. empty the 3q container

5. traspass the 2 quarters of water to the 3q container

6. fills the 5q container

7. fills the 3q container with the water of the 5q container so you have left 4 quarters of water in the 5q container = 1 gallon of water.

1 Gallon is 4 qts

1. Have an empty 5 qt Jug, and a full 3 qt jug

2. Fill up the 5 qt Jug to 3qts, using the 3 qt jug

3. Mark the level of the 3 qts on the 5 qt jug

4. Fill up the 5 qt jug and transfer 3qts to the 3 qt jug

5. Mark the 2 qt level on the 5 qt jug i.e. remaining water in 5 qts jug

6. Now empty the 5qt jug, and fill up the 3 qts jug, then transfer only upto the 2qts level to the 5 qt jug from the 3 qts jug

7. Now, 5qt jug has 2 qts water, and 3 qts has remaining 1 qt water.

8. Empty 5 qts jug and fill it upto the 3 qts level, transfer the remaining 1 qt from the 3 qt jug

Gayle,

- Prasanna October 30, 2005I don't think you can repeat the step 1 to get 4 quart (1 gallon) in one container. I think this is the correct solution.

1) Fill 3 quart jug and transfer it to 5 quart jug

2) Fill 3 quart jug again and tranfer 2 quart to 5 jug (5 quart become full now)

3) Empty 5 quart jug and tranfer the 1 quart from 3 to 5.

4) Fill 3 quart and transfer it to 5. Now 5 quart jug contains 4 quart which is 1 gallon.

right?