## engineer06

BAN USER- 0of 0 votes

AnswersImagine a horizontal corridor bounded by y = y1 and y = y2 lines on a 2D-plane. There are N sensors with centers (x, y) each of which operates in a range (r) on the plane . So, they cover some circular areas on the plane. See the figure below.

`o | _____o___o__|____________ y = y1 o |OOO __________oo|_____O______ y = y2 O | O _ _ _ _ _ _ | _ _ _ _ _ _ | o O | o O O | | O | |`

The question is whether a path exist from x=-inf to x=+inf via corridor without being detected any radar.

Constraints:

1. You are free to move any direction only if you stay in the corridor.

2. You are free to go through corridor borders.

3. N sensors are given as list of (x, y, r) like [(1, 3, 2), (-1, -3, 4)]. x and y are signed integers. r is a unsigned integer.

4. y1 and y2 are integers.

My solution:

1. Create an intersection graph of N sensors by comparing them each other via Euclidean distance`(x1 - x2)^2 + (y1 - y2)^2 <= (r1 + r2)^2`

2. If there is a path between y=y1 and y=y2 through intersected sensors, there do not exist any path from x=-inf to x=+inf. Otherwise, there do exist a path. So, I used BFS to search such a path.

Worst Case Complexity:

1. O(n^2)

2. O(V + E) = O(n + intersection_count)`Total: O(n^2)`

My Best Case Optimization for Intersection Graph:

- engineer06 in United States

1. For each sensor, create two events for start and end of circles vertically. y = (y1 - r) and y = (y1 + r)

2. For each sensor, register those two events into an array.

3. Use a line sweep algorithm over 2, which is O(nlogn + intersection_count) and intersection_count may be n^2 at worst case.

I wonder if I should have had a better solution with the worst case < O(n^2).| Report Duplicate | Flag | PURGE

Amazon SDE-2 Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

The sensors in figure are expanded versions of sensor. Given the center (x, y) and radius(r), all (xi, yi) points satisfying (x - xi)^2 + (y - yi)^2 <= r^2 are covered by sensor.

It should be like:

a -> center, x->covered, h-> half covered.

- engineer06 April 29, 2018Yes, in fact, any direction angle (0 <= angle < 360) is applicable. Also curves are applicable, paths may be just like some mountain paths.