Google Interview Question: Compute all the intersections... | Glassdoor

Interview Question

Software Engineer Intern Interview Dublin, Co. Dublin (Ireland)

Compute all the intersections of two sets of segments in a

  line.
Tags:
python, line sweeping
Answer

Interview Answer

2 Answers

0

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

Interview Candidate on Feb 9, 2011
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 Jan 8, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.