Microsoft Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

Gayle,
I 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?

- Prasanna October 30, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fill 3 quart jug & put in 5 quart jug.
Next fill 3 quart jug & use it to fill the remaining part of the 5 qt jug.
You will end up with 1 quart in the 3 quart jug.

- SN October 15, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

even better: fill 5 quarts, fill with it 3 quart jug, you are left with 2 quarts in the 5 quart jug. This can be used to fill half of one galon. Repeat.

This method accomplishes the task in half the time

- Andrey Jivsov October 22, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What do you mean by "fill half of one gallon"? How do you measure half of one gallon?

I believe there's a much simpler solution.

Oh - and does anyone know what algorithm solutions to this problem can be based off of?

- Gayle L McDowell October 23, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Gayle:

1) fill 5 quart jug with "source water";
2) using water from 5 quart jug fill up 3 quart jug (without wasting any water); you are left with 5-3=2 quarts in the 5 quart jug;
This is exactly half a gallon;
3) repeat step 1).

- Andrey Jivsov October 24, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hehe... nevermind, I didn't see the unit change (gallons vs quarts) :-)

- Gayle L McDowell October 25, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Prasanna - 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

- Gayle L McDowell October 30, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Acme January 02, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Manish August 21, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Worst solution ever, Manish.

1) Dump full 3 into 5
2) Dump full 3 into 5 until 5 is full
* 3 now contains 1 qt.
3) Empty 5
4) Dump 1 qt into 5 from 3
5) Dump full 3 into 5
* 5 now contains 4 qts.

- Mommy September 03, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks Mommy!!

Yes it is a bruteforce solution with the worst complexity ... thanks for the optmized solution ...

--Manish

- Manish September 04, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) fill 5 quart jug with 3quart jug and mark it there on 5 quart jug indicating 3 quart level on 5 quart jug
2) now fill 5 quart jug full then empty the 5quart jug until 3 quart mark into Gallon
repeat the step 2 again.

- ss October 02, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) fill 5 quart jug with 3quart jug and mark it there on 5 quart jug indicating 3 quart level on 5 quart jug
2) now fill 5 quart jug full then empty the 5quart jug until 3 quart mark into Gallon
repeat the step 2 again.

- ss October 02, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) fill 5 quart jug with 3quart jug and mark it there on 5 quart jug indicating 3 quart level on 5 quart jug
2) now fill 5 quart jug full then empty the 5quart jug until 3 quart mark into Gallon
repeat the step 2 again.

- ss October 02, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

watch die hard III

The same question in the movie

- J.C. March 10, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Fill 5 and transfer it to 3
2) Empty 3 and transfer the 2 remaining quarts from 5 to 3
3) Fill 5 quart and transfer all you can to 3. Now 5 contains 4 quarts.

1) 5(5) -> 3(0) = { 5(2) , 3(3) }
3) 5(5) -> 3(2) = { 5(4) , 3(3) }

- Anonymous August 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

5 quart 3 quart
----------- -----------
step 1: 5 0
step 2: 2 3
step 3: 2 0
step 4: 0 2
step 5: 5 2
step 6: 4 3

- Deepak Ranjan August 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This thing did not help es una porqueria no me gusta para nada

- Claudia April 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All sounds complicated. I would just put the 5 quart jug on my bathroom scale and and pour water in it until it weighs 8 pounds pulse the weight of the jug.

- Darrell June 09, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More