Amazon Interview Question for SDE-2s
- 0of 0 votes
Imagine 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.
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.
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:
2. O(V + E) = O(n + intersection_count)
My Best Case Optimization for Intersection Graph:- engineer06 April 29, 2018 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
Interview Type: In-Person
Open Chat in New Window