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

python, line sweeping

Interview Answer

2 Answers


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

Interview Candidate on Feb 9, 2011

int line1[line size]
int line2[line size]
int overlap[line size]

for each segment in set1
  for i = segment start to segment end

for each segment in set2
  for i = segment start to segment end

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.