Microsoft Interview Question
Software Engineer / DevelopersTeam: STB
Country: India
Interview Type: In-Person
Step: 2 will create a problem. because W1 is standing there and H2 has reached there. so both are together
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.
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.
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
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.
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
lets name couples as H1,W1,H2,W2,H3,W3,H4,W4
- Abhishek July 03, 2012initially 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.