Google Interview Question Software Engineer in Tests
Very good answer ...today my senior asked the same question and i think of it more but i vcant solve the qstn ..but my my senior trust on me that i can ..give him the right answer ..after sometime i searched it on google ..and i find it ...the qstn ...which u solved in simple manner ..really sir thank uuh so much
There is no solution to the (3,3) problem. So now, the problem is
a) Proving if it can be solved for (x,y) {men,lions}.
b) Providing an algorithm.
I believe the solution is feasible only when x>=y+2 for y>2 and x=y otherwise. I haven't been able to prove it though :(
Start state(a+2,a)
Algorithm:
a) Rower takes a lion to the other side. (a+1,a-1),(1,1)
b) Rower returns. (a+2,a-1),(0,1)
c) Rower takes a man to the other side.(a,a-1),(2,1)
d) Rower returns.(a+1,a-1),(1,1)
e) Rower takes a man to the other side. (a-1,a-1),(3,1)
f) Rower returns (a,a-1),(2,1)
g) Repeat a - d. {see below}
a) Rower takes a lion to the other side. (a-1,a-2),(3,2)
b) Rower returns. (a,a-2),(2,2)
c) Rower takes a man to the other side.(a-1,a-2),(3,2)
d) Rower returns.(a,a-2),(2,2)
at each iteration of (a-d) we will increment men and lion on the other side by 1.
Here is a proof why you require at least 2 more.
a) Consider the situation where the rower (man) is in the middle of the river. In this case, on either side of the river you need to have at least as many men as lions + the rower himself. Therefore we require at least 1 man extra.
b) In the situation described in a) if the rower moves to the source he has 2 options
a) Moving a lion (but this would increase the counts of lions on the other side by 1) or
b) Moving a human (but this would reduce the number of men on the source by 1)
Therefore, we will require one more human. Hence the count becomes 2 more humans than lions.
The algorithm is provided above.
how about this?
1 man+1 lion => drops the lion in other bank and man returns
takes 2nd lion => drops the lion in other bank and man returns
takes 2nd man => drops the man in other bank and man returns WITH A LION
drops 2nd lion + takes 3rd man => drops the man in other bank and man returns
now you have, 2 lions on one bank, and 1 lion+ 2men on the other bank
take each of the lions and drop on the other bank, 2 more steps.
Better Formatting:)
Here is the soln for 3M,3L
M L(Side 1) M L (Boat) M L (Side 2)
3 3 0 2 --> 0 2
3 2 0 1 <-- 0 1
3 2 0 2 --> 0 3
3 1 0 1 <-- 0 2
3 1 2 0 --> 2 2
2 2 1 1 <-- 1 1
2 2 2 0 --> 3 1
0 3 0 1 <-- 3 0
0 3 0 2 --> 3 2
0 2 0 1 <-- 3 1
0 2 0 2 --> 3 3
possible with 4 men and 3 lions.x=y+1
here are the numbers: first no denotes men,second lions.each grouping denotes a bank.
4,2 0,1
4,1 0,2
2,2 2,1
0,3 4,0
possible with 4 men and 3 lions.x=y+1
here are the numbers: first no denotes men,second lions.each grouping denotes a bank.
4,2 0,1
4,1 0,2
2,2 2,1
0,3 4,0
It is not possible to do this for N>3. Let me know if my proof is right guys.
Proof:
Let me denote (A,B) (C,D) X representing no of lion\main on each side of banks and X denoting where the boat is.(X=0 means on left side, X=1 means on right side)
Problem definition:
Change state from (N, N) (0,0) 0 -> (0,0) (N, N) 1.
If N>4, no solution exists.
Proof:
The first trip has to be lion else men on right bank will die.
So(N N) (0 0) 0 -> (N-1,N) (1,0) 0
Second trip has to be lion, else man on right bank will be (N-1,N-2) when boat leaves and they will die.
So 2nd trip is(N-1,N) (1,0) 0 ->(N-2,N) (2,0) 0
Now a lion cant be taken because the no of lions on the right bank would be more than 2 without any man and it means sure death for any first man who comes to the right bank in the future.
So a man has to be taken. It also means a lion has to return from right side so that 2 lions and 1 man wont be left on the right side.
So (N-2,N) (2,0) 0 -> (N-1,N-1) (1,1) 0
Now only lion should be taken else men on left side would die unless N=3. If he brings lion back, there is no change in state overall. If he brings man back, we end up in the same as one of the states above [(N-2,N) (2,0) 0].
So there is nothing we can do after this if N>3. The state wont change to any safe state.
There is a recursive solution for this problem. Please read through.
#include <stdio.h>
int func(int, int);
main()
{
int M,C;
scanf("%d%d",&M,&C);
printf("%d\n",func(M,C));
}
int func(int M, int C)
{
if(M==1 && C==1)
{
// printf("(1,1,1)\n(0,0,0)\n");
return 1;
}
else if(M==2 && C==2)
{
// printf("(2,2,1)\n(1,1,0)\n(2,1,1)\n(0,1,0)\n(1,1,1)\n(0,0,0)\n");
return 5;
}
else if(M == C)
{
/* printf("(%d,%d,1)\n(%d,%d,0)\n",M,C,M-1,C-1);
printf("(%d,%d,1)\n(%d,%d,0)\n",M,C-1,M,C-3);
printf("(%d,%d,1)\n(%d,%d,0)\n",M,C-2,M-2,C-2);
*/ return (6+func(M-1,C-1));
}
else //case where M > C
{
int i;
// for(i=0;i<(M-C);i++)
// printf("(%d,%d,1)\n(%d,%d,0)\n",M-i,C,M-(i+1),C-1);
return 2*(M-C)+func(C,C);
}
}
// some correction to your algo
#include <stdio.h>
int func(int, int);
main()
{
int M,C;
scanf("%d%d",&M,&C);
printf("%d\n",func(M,C));
}
int func(int M, int C)
{
if(M < C) {
printf("no soln exists\n");
return -1;
}
if(M==1 && C==1)
{
// printf("(1,1,1)\n(0,0,0)\n");
return 1;
}
else if(M==2 && C==2)
{
// printf("(2,2,1)\n(1,1,0)\n(2,1,1)\n(0,1,0)\n(1,1,1)\n(0,0,0)\n");
return 5;
}
else if(M == C)
{
return (4+func(M-1,C-1));
}
else //case where M > C
{
int i;
// for(i=0;i<(M-C);i++)
// printf("(%d,%d,1)\n(%d,%d,0)\n",M-i,C,M-(i+1),C-1);
return 2*(M-C)+func(C,C);
}
}
I think this question is not described correctly. There is N men and N person. If the condition that there are x men, x lion on one side, and N-x men, N-x lion on the other side appears, we can't make any progress. The next round, we can only put a man and a lion into the boat. Two men or two lion will cause a problem on one side.
For (N, N) condition, the situation described must be appear. Because both sides need the number of men is bigger than the number of the lion. At the same time, the total number of lion and the total number of men are equal.
Recursive solution. First define a state (men, lions, men2, lions2, forward) as meaning there are currently so many men & lions on original side, so many men2 and lions2 on opposite side, and that we are now moving forward. The capacity is a constant that indicates the capacity of the ferry.
At each step, for 3 men and 3 lions, we can either put M, MM, ML, L or LL on the ferry, represented by integers 1,2,4,3,6 respectively (see comment below). We simply try all ferry configuations and see if any will eventually lead to all men & lions on the opposite side. Note that I am using a HashSet to prevent us from ever revisiting the same state, otherwise we might get into infinite loop.
I have included a sample print method as well.
static HashSet<String> seen = new HashSet<String>();
static boolean cross(int men, int lions, int men2, int lions2, boolean forward, int capacity) {
if(men == 0 && lions == 0)
return true;
if((men > 0 && men < lions) || (men2 > 0 && men2 < lions2))
return false;
if(men < 0 || lions < 0 || men2 < 0 || lions2 < 0)
return false;
String state = "" + men + lions + men2 + lions2 + forward;
if(seen.contains(state))
return false;
else seen.add(state);
int base = capacity + 1;
for(int i=1; i<=capacity*base; i++) {
// if capacity=2, then base=3
// imagine i as base3, where the digits represent the number of men or lion
// 1,2 means 1,2 men respectively
// 3,6 means 1,2 lions respectively
// 4 means 1 man and 1 lion
int numMen = i%base;
int numLions = i/base;
if(numMen+numLions > capacity)
continue;
numMen *= (forward ? 1 : -1);
numLions *= (forward ? 1 : -1);
if(cross(men-numMen, lions-numLions, men2+numMen, lions2+numLions, !forward, capacity)) {
print(numMen, numLions);
return true;
}
}
return false;
}
static void print(int numMen, int numLions) {
boolean forward = (numMen > 0 || numLions > 0);
numMen = Math.abs(numMen);
numLions = Math.abs(numLions);
if(forward) {
for(int i=0; i<numMen; i++)
System.out.print("M");
for(int i=0; i<numLions; i++)
System.out.print("L");
System.out.print("->");
System.out.println();
} else {
System.out.print(" <-");
for(int i=0; i<numMen; i++)
System.out.print("M");
for(int i=0; i<numLions; i++)
System.out.print("L");
System.out.println();
}
}
Here's a generalized C# code:
public static void LionAndManCrossing(int men, int lions)
{
if (lions > men)
{
System.Console.WriteLine("LionAndManCrossing error: Lions can not be more than men");
return;
}
int BM = 0; // Men in boat
int BL = 0; // Lion in boat
int RM = 0; // Men in right bank
int RL = 0; // Lions in right bank
int LM = men; // Men in left bank
int LL = lions; // Lions in left bank
// Put captain in boat.
++BM;
--LM;
while (true)
{
if (LL >= LM && LM != 1)
{
// Put lion in boat.
--LL;
++BL;
}
else
{
// Put man in boat
--LM;
++BM;
}
// Travel Right...
Debug.Assert(LM == 0 || LL <= LM); // Boat man leaves. Verify bad condition.
// Unload passanger
if (BM > 1) { --BM; ++RM; } else if (BL == 1) { --BL; ++RL; }
// CHeck if we're finished
if (LL == 0 && LM == 0) break;
if (RL > RM && RM > 0)
{
// Put lion in boat.
++BL;
--RL;
}
// Travel Left ...
Debug.Assert(RM == 0 || RL <= RM); // Boat man leaves. Verify bad condition.
// Unload passanger
if (BM > 1) { --BM; ++LM; } else if (BL == 1) { --BL; ++LL; }
}
// Put captain in right bank.
--BM;
++RM;
}
Well I guess there are 3 men (x=3) and 3 lions (y=3) so the solution seems like this
- Carry one man and one lion in fist ferry (2M-2L ------------- 1M - 1L)
- Carry one man and one lion in second ferry (1M-1L ............... 2M - 2L)
- Carry one man and one lion in third ferry (0M-0L........................3M-3L).
At no point in this transaction there were more lions than men on any bank ( y > x was false)
Now if y > x to begin with then lions will eat all men and ferry wont happen, so x > y. (men must be more than or equal to lions to begin with for valid input).
Ferry x-y men first (YM - YL ...................... (X-Y) M) through (x-y)/2 trips
Then next carry one man and one lion using y/2 trips
1st step: 1men 1 lion to the other side , leave 1 lion there and 1 man returns.(1 lion )
2nd step: take 2 lions , leave 1 lion and 1 lion returns(2 lions)
3rd step: take 2 men other side, 1 man and 1 lion return.. (1 man and 1 lion on other side)
4th step: take 2 men, leave 2 men and 1 lion returns( 3 men on other side)
5th step: take 2 lions , leave 1 lion, 1 lion returns (3 men and 1 lion other side)
6th step: take 2 lions other side(3 men and 3 lions other side)
1. 2 lions go that side 1 return
2. 1 lion and 1 man. man returns
3. 2 man . lion returns
4. 1 man 1 lion. lion returns
5. both lions
All are wrong. Here is the answer :
1. 1 man 1 lion travels and 1 man returns.
After step one we have 2 lions and 3 men at start and 1 lion at target position.
2. 2 lions travel and 1 lion returns
After this step two we have 3 men and 1 lion at start and 2 lions at target
3. 2 men travel and 1 man and 1 lion returns
Now we have 2 men and 2 lions at start and 1 man and 1 lion at target
4. 2 man travels and 1 lion returns.
At this point we have 3 men at target location and 3 lions at starting location.
Moving those lions to target is simple.
The solution according to me is that first two lions will go across the river then one lion will return .Then two lions will cross the river and one lions will return;Then two men will go to the other side of the river and then one man and one lion will return.The Two men will cross the river and lion will return ;Then first two lion will come back.Then one of them will return and last two lion will cross the river .So all the conditio given in question will satisfied
- arvindnitw07 March 06, 2009