Interview Question

Software Engineer Intern Interview

-Dublin, Dublin


Compute all the intersections of two sets of segments in a line.


Interview Answers

2 Answers


Only implemented the naive solution O(M x N) time, should have implemented a line sweeping algorithm.

Anonymous on


int line1[line size] int line2[line size] int overlap[line size] for each segment in set1 for i = segment start to segment end line1[i]++ for each segment in set2 for i = segment start to segment end line2[i]++ for i = 1 to line size if line1[i] and line2[i] overlap[i] = 1

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.