Interview question, can anyone think of good solution.

[mahbub79]

Hi,

My brother recently went for an interview at a Investment Bank and was given these 2 questions, can anyone think of a good solution?, the 2nd question seems to be a bit vague.. This was a Java based role but I'm sure solutions will be relatively similar.


1) write algorithm: write classes/methods to calculate the total
length of a set of lines given the start and end points taking into
account overlapping.

E.g.
Line 1 Line 2
start end start end
-------- ------ --------- -------
-1.4 3.2 2.9 4.1

Total length would be 5.5 as line 1 length = 4.6 and line 2 length =
1.2, but line 2 overlaps line 1 by 0.3.


2) rewrite a calculation class to run on multi-processor server
to speed up processing time (Threads). Currently uses static methods,
lazy initialisation.

[cilu]

I did not understand the logic of the first question.

[DeepT]

This is like a recent problem I solved for aggregating lits of IPs, eliminating duplicates, and creating ranges out of neigboring IPs and other ranges blocks.

There is no simple answer, but what I did was create an IP data type (which in your case would be a line segment data type) which had operators such as union, intersection, addition, and subtraction.

On borders, such as a number of 1 and 2, if asking if they intersected, id say yes to make the logic simpler (opposed to also creating neighbor operators too).

So then once you do all that, It became simple by saying things like:

if A intersects B, then A += B;

Then the add operators would take care of all the cases of knowing how to add B if it is before A, lies in A, or is right after A.

Then you simply take a collection of these line segments, and then perform the If Intersect operation from the top of the llist to the bottom of the list, adding where neccairy.

I figured out a way to do it in in one pass, although I do not remember off the top of my head. I could look it up if I needed to. You could just do two nested loops and if there are no adds done though a complete pass (like a bubble sort) then you assume the entire list has ben condensed as far as it can be.

Finally, when the list is as small as it can get, then you just go through each element, and ask how long it is and add them together, and you have your answer.

As for the second question, how to optimize it and all for a multi proccing enviroment, that is more tricky. Basically you can have one thread which runs though the master list and kicks off addtions and intersections of each element as a seperate thread. However this becomes very messy because you will have a bunch of sychrnonization problems between threads and memory. Id like to say a good compiler written for a parallel computing enviroment would figure all this out for you, but Java isn't really compiled (like C++ is). It is more like partially digested instead of compiled.

[mahbub79]

sorry, it seems like the formatting didn't come out right,
here it is again:

write classes/methods to calculate the total
length of a set of lines given the start and end points taking into
account overlapping.

E.g.
Line 1
start: -1.4, end: 3.2

Line 2
start: 2.9, end: 4.1
etc..

I think what he meant to say was,
Total length would be:
line 1 length = 4.6 (you have to get length of each line)
line 2 length =1.2, (you have to get length of each line)
but as line 2 overlaps line 1 by 0.3, therefore length of set is 5.5(rather than 5.8).

hope this makes things clearer

any suggestions/ideas for multi thread question would be helpful, thanks

[DeepT]

Did you understand my answer to part 1? Or are you looking for a coded solution?

[JMS]

Ahhhh elementary geometry.. excellent...

(1)The formula for a line is y = mx+b... where
M is the slope = rise over run = y1-y2/x1-x2 ( ie.. when x = 0 Y = b)
B is the y intercept.. or where the line hits the y axis..
X and Y are just points of the line and are usually left as variables.. thus if you know X or Y for any line you will automajically be able to calculate the other value.

So now.. No line can or will overlap unless it's line formula is the same..
Same Y intercept and same slope. That's a basic law of geometry..

So your algorithm would look something like this...

Calculate slope for line 1
Calculate slope for line 2

If they're the same.. then caculate the Y intercept for both... Y intercept can be calculated once you've found the slope by plugging the X+Y values of any end point back into the line formula above and solving for b..!!

If the slopes aren't the same then caculate the length of each of the segments and add them together. Your done.. The length of a line segment can be calculated by the pythagorium therom.. just use your end points for the hypotoneus..

length = (x2-x1)**2/(Y2-Y1)**2


If the Y intercepts for the line are the same then and only then you check for an overlap..

To check for an overlap, knowing slope and y intercept are the same all you have to do is see if the X value and Y value of any point in line 1 is between or the same as the X and Y values for line 2. and visa versa Once you Know they overlap then just plug the two outer points into the line length expression above and your done....

If the Y intercepts aren't the same then caculate the length of each of the segments and add them together. Your done..

Simple....

To do this as a multi threaded program you could have one thread calculating the lengths and a second thread calculating the line forumulas.. Both threads would be updating a central data structure.. Might save you a billionth of a second..

[DeepT]

I think his lines are one dimensional.

[cilu]

Might save you a billionth of a second..
With 2 lines. But with a billion lines it can save you some time... Thing is that we don't talk about lines here, but segments.

[cilu]

[ moved thread ]

[JMS]

int LineLength( float fStart1, float fEnd1, float fStart2, float fEnd2);
float CalculateLength ( float fStart, float fEnd );
int TheyOverlap(float fStart1, float fEnd1, float fStart2, float fEnd2 );

LineLength( float fStart1, float fEnd1, float fStart2, float fEnd2)
{
float fReturnLength = 0.0;

// do the sements overlap??
if( TheyOverlap(fStart1, fEnd1, fStart2, fEnd2 ))
{
// Yes the segments overlap
float fStart = 0.0;
float fEnd = 0.0;

// don't know if Java has the ?: statement.. if so it makes it way fewer lines
// fEnd = ( fStart1 > fStart2 ) ? fStart1 : fStart2;
if( fStart1 > fStart2 )
{
fStart = fStart1;
}
else
{
fStart = fStart2;
}

// fEnd = ( fEnd1 > fEnd2 ) ? fEnd1 : fEnd2;
if( fEnd1 > fEnd2)
{
fEnd = fEnd1;
}
end
{
fEnd = fEnd2;
}
fReturnLength = CalculateLength( fStart, fEnd);
}
else
{
fReturnLength = CalculateLength( fStart1, fEnd1);
fReturnLength += CalculateLength( fStart2, fEnd2);

}

return fReturnLength;
}

// calculate the length of a line segment given beginning and end point
float CalculateLength ( float fStart, float fEnd )
{
float fReturnLength = 0.0;

if( fStart > fEnd )
{
fReturnLength = fStart-fEnd;
}
else
{
fReturnLength = fEnd - fStart;
}

return fReturnLength;
}


// take two line segments and return whether they overlap
int TheyOverlap(float fStart1, float fEnd1, float fStart2, float fEnd2 )
{
int iRc = 0;
float ftStart1 = (fStart1>=fStart2) ?fStart1:fStart2;
float ftStart2 = (fStart2>=fStart1) ?fStart2:fStart1;
float ftEnd1 =( fEnd1>=fEnd2) ?fEnd1:fEnd2;
float ftEnd2 =( fEnd2>=fEnd1) ?fEnd2:fEnd1;



if ( ftStart1 > ftStart2)
{
if( ftEnd1 > ftEnd2 )
{
if( ftEnd2 > ftStart1 )
iRc = 1;
else
iRc = 0;
}
else
{
if( ftEnd1 > ftStart1 )
iRc = 1;
else
iRc = 0;
}
}
else
{
if( ftEnd1 > ftEnd2 )
{
if( ftEnd2 > ftStart2 )
iRc = 1;
else
iRc = 0;
}
else
{
if( ftEnd1 > ftStar2 )
iRc = 1;
else
iRc = 0;
}
}

return iRc;
}


if you had to break it up into multiple threads you would want to create a datastructure to contain the line segment lengths in one thread, calculate if they overlap in another thread, and then once both calculations were complete you could calculate the resulting length..... you could synchronize your threads with a semphore.....

a better improvement would be to add your line segments to a stack and then have a class which could take a variable amount of lines and always calculate the composite length....

I have way too much time on my hands...

[mahbub79]

Coded solution would be great, I'm trying to put sample questions and solutions to such questions. I'm sure there are several variants but they all must share similar answer. Thanks

[mahbub79]

seems like you've just put one, wonderful. I'll try it out at some stage. This forum is excellent & updated regularly!

[Yves M]

For algorithm 1, you can just sort the segments by starting position and then you go through it in this way:
sum initialized to the length of the first segment
last_end initialized to the end of the first segment.

At each step, you just check whether the start of the segment is <= than last_end.

If yes, check whether current_end <= last_end

yes, then do nothing (the new segment is contained in the previous one)
No, then add current_end - last_end to the sum and set last_end to current_end

If no, then the segment is not overlapping, so add current_end - current_start to the sum and set last_end to current_end.