Interview Question

Software Engineer Intern Interview

-Dublin, Dublin

Google

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

Answer

Interview Answers

2 Answers

0

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

Anonymous on

0

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.