Microsoft Interview Question for Software Engineer / Developers


Team: STB
Country: India
Interview Type: In-Person




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

lets name couples as H1,W1,H2,W2,H3,W3,H4,W4
initially all are in side 1
1.H1 and W1 will cross the river.W1 will stay in side 2 and H1 will come back.
2.H2 and W2 will cross the river.W2 will stay in side 2 and H2 will come back.
3.H1 and H2 will cross the river.H1 will stay in side 2 and H2 & W2 will come back.
4.W2 and W3 will cross the river.Both W2 and W3 will stay in side 2 and H1 will come back.
5.H1 and H2 will cross the river.Both H1 and H2 will stay in side 2 and W3 will come back.
6.H3 and W3 will cross the river.Both H3 and W3 will stay in side 2 and W1 & W2 will come back.
7.H4 and W4 will cross the river.Both H4 and W4 will stay in side 2 and W3 will come back.
8.W1 and W2 will cross the river.W1 will stay in side 2 and W2 will come back.
9.Finally both W2 and W3 will cross the river.

- Abhishek July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Step: 2 will create a problem. because W1 is standing there and H2 has reached there. so both are together

- Sachin July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yeah..but W1 is not staying with H2..H2 just crossed the river and came back.

- Abhishek July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very elegant solution.

- Spock July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess it's all about your interpretation of the problem's constraints. I interpreted it the same way as Sachin, and proceded to prove that no solution to this problem was possible.

- eugene.yarovoi July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

given condition is dissatisfied after step 6

- master August 13, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

abhishek...
very nice approach bro..
but i guess they interviewer needs a solution with less no. of round thats why he has given an island in between ..
it gets solved with quite less movements...using island..:)
still great and clean approach

- shreyans August 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

google "jealous husband problem" u ll get a lot of stuff

- codez July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

similler kind of puzzle
priest-gost-logic.html

- atul gupta July 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer is really simple if we drop ego of mind in this problem

- -|- Pramod Chandoria July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think some of the trips can be shortened by using the island!

If all the interviewer cared about were the number of trips - that might not change form the above solution, 17 one way trips. But, the distance traveled and time taken can definitely be reduced. I estimate that only 12 or 13 river-breadth distances need to be traveled, as compared to the 17 river-breadths traveled in the above solution.

- ivanyaru July 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not getting complexity in the problem. Whats the problem If all the couples crosses the river one by one. like first trip h1w1 second trip h2w2 and so on..

I guess something is missing in this problem .. Like number of trips

- Nihal July 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ohh.. My bad.. Ok so Solution can be like this

1. H1W1 goes to island w1 stays and H1 brings the boat back
2. H2W2 takes boat w2 stays on the other side and h2 brings back
3. Now h1h2 goes to other side and h1 comes back
iterate step 2 and 3 for next two couples.. 3step H1 will always bring back the boat).
Finally h1 goes to island and pick w1.

- Nihal July 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nice solution ..thnx ..

- Jash July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can this problem be solved in the general case of n couples ?

- Anonymous September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) H1,W1 travels to side 2 , W1 stays on side 2, H1 travel back (1 round trip)
2) H2,W2 travel to side 2, W2 stays on side 2, H2 travel back (1 round trip)
3) H3,W3 travel to side 2, W3 stays on side 2, H3 travel back (1 round trip)
4) H4,W4 travel to side 2, W4 stays on side 2, H4 travel back(1 round trip).
5) Both H1 & H2 travel to side2, and W3,W4 travel to side 1, W3 now gets off @ island and W4 travels to side 1 (1 round trip)
6) H3 & H4 travel to side 2, H3 gets off at side 2, H4 returns to side 1 (1 round trip)
7) H4 travels back to side1 to pick up W4 and returns to side 2 (1 round trip)
8) H3 travels to island, picks up W3 and returns to side 2 (1/2 round trip)

side1		island		side2
h1w1
h2w2
h3w3
h4w4
____________________________
h1						w1
h2w2				
h3w3
h4w4
____________________________
h1						w1
h2						w2
h3w3
h4w4
____________________________
h1						w1
h2						w2
h3						w3
h4w4
____________________________
h1						w1
h2						w2
h3						w3
h4						w4
____________________________
						h1w1
						h2w2
h3			w3
h4w4
____________________________
						h1w1
						h2w2
			w3			h3
h4w4
____________________________
						h1w1
						h2w2
			w3			h4w4
						h3
____________________________
						h1w1
						h2w2
						h3w3
						h4w4

- confused_banda December 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your step 5 is an issue.. Both H1 & H2 travel to side2, and W3,W4 travel to side 1 .... Now, when h1,h2 get off on side 2, w3,w4 are still there....so its not allowed.

- Advait October 07, 2014 | Flag


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