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
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.