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