Interview Question
Country: India
1+2 : 2 min
1 back : 1 min
3 + 4 : 10 min
3 back : 5min rite..?
1st person takes 1 min, 2nd takes 2 min, 3rd takes 5 mins and 4th takes 10 min...
public class freetest {
public static void outputInterval(int [][] A,int m,int [][] B,int n)//output the interval which include A but exclude B
{//assume A and B are sorted by their first value(s)
int i = 1;
int j = 0;
int valid = 1;
int start = A[0][0];
int laststart = -1;
int end = A[0][1];
int excludeEnd = 0;
while((i + j) != (m + n ))
{
if(i>=m|(A[i][0]>=B[j][0]&&j<n))//explore B[j][0]
{//6 situations
if(excludeEnd <= B[j][1])
{
excludeEnd = B[j][1];
}
if(B[j][1] <= start)//do nothing
{ }
else if(B[j][0] <= start && B[j][1] <= end && B[j][1] >= start)
{
start = B[j][1];
}
else if(B[j][0] <= start && B[j][1] >= end)
{
valid = 0;
}
else if(B[j][0] <= end && B[j][0] >= start && B[j][1] <= end && B[j][1] >= start)
{
System.out.println(start + "-" + B[j][0]);
start = B[j][1];
}
else if(B[j][0] <= end && B[j][0] >= start && B[j][1] >= end)
{
System.out.println(start + "-" + B[j][0]);
valid = 0;
}
else if(B[j][0] >= end)
{
valid = 0;
}
j++;
}
else //explore A[i][0]
{
if(excludeEnd > A[i][1])
{
//do nothing
}
else if(A[i][0] <= excludeEnd && A[i][1] >=excludeEnd)
{
if(valid == 0)
{
valid = 1;
start = excludeEnd;
end = A[i][1];
}
else
{
if(A[i][1] >= end)
{
end = A[i][1];
}
}
}
else
{
if(valid == 0)
{
valid = 1;
start = A[i][0];
end = A[i][1];
}
else
{
if(A[i][0] >= end)
{
System.out.println(start + "-" + end);
start = A[i][0];
end = A[i][1];
}
}
}
i++;
}
}
if(valid == 1)
{
System.out.println(start+"-" + end);
}
}
public static void main(String args[]) {
System.out.println("Hello World!");
int [][] A = new int[100][2];
A[0][0] = 10;
A[0][1] = 100;
A[1][0] = 200;
A[1][1] = 300;
A[2][0] = 400;
A[2][1] = 500;
int [][] B = new int[100][2];
B[0][0] = 95;
B[0][1] = 205;
B[1][0] = 410;
B[1][1] = 420;
B[2][0] = 450;
B[2][1] = 510;
outputInterval(A,3,B,3);
}
}
person 1 and person 2 cross the bridge so time taken in crossing the bridge=2 min
then person 2 came back...time taken=2min
person 3 and person 4 cross the bridge ...time taken=10min
person 1 came back ..time taken=1min
person 1 and person 2 cross the bridge in time of 2 min
so total time =2+2+10+1+2=17min
1+2 : 2 min
- Russell February 04, 20121 back : 1 min
3+4 : 10 min
2 back : 2 min
1+2: 2 min