Amazon Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
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:
.hxh.
hxxxh
xxaxx
hxxxh
.hxh.
a -> center, x->covered, h-> half covered.
Yes, in fact, any direction angle (0 <= angle < 360) is applicable. Also curves are applicable, paths may be just like some mountain paths.
I am not sure I fully understand your approach. What I understand:
- find components of the graph (connected islands of sensors that are within reach)
- if such a components max y and min y is beyond both corridor lines it will block the way through
Finding those components can be done in O(n^2) naively, there is an optimization to this that does not improve worst case, but is better with lots of sensors. The question is, how to optimize looking at n-1 sensors to find adjacent sensors of a given sensor.
- rasterize the sensor positions and maintain a list of sensors located in a raster square
- for a given sensor, check the surrounding squares, if raster square is the sensor reach (diameter) you need to check 9 squares, accessing those sensors is O(1) e.g. with a hashtable on raster x,y... if all sensors are located in 9 or fewer squares, you do not win anything, if they are normally distributed over thousands of squares, you will end up in O(n*n/squarecount)
Cool question, thanks for sharing.
C code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void printsensors(int n, int m, int s[][3]) {
printf("[");
for(int i = n; i <= m; i++)
printf("(%d, %d, %d), ", s[i][0], s[i][1], s[i][2]);
printf("\b\b]\n");
}
void swap(int s[][3], int i, int j) {
for(int k = 0; k < 3; k++) {
int t = s[i][k];
s[i][k] = s[j][k];
s[j][k] = t;
}
}
int corridor(int y1, int y2, int n, int s[][3]) {
for(int i = 0; i < n;) {
int nextstart = i + 1;
int ymax = s[i][1] + s[i][2];
int ymin = s[i][1] - s[i][2];
for(int j = i + 1; j < n; j++) {
// check if s[j] intersect any of intersecting sensors group s[i] to s[nextstart - 1]
for(int k = i; k < nextstart && nextstart <= j; k++) {
int x = s[k][0] - s[j][0];
int y = s[k][1] - s[j][1];
int r = s[k][2] + s[j][2];
if(x*x + y*y <= r*r) {
if(ymax < s[j][1] + s[j][2])
ymax = s[j][1] + s[j][2];
if(ymin > s[j][1] - s[j][2])
ymin = s[j][1] - s[j][2];
// bring intersecting sensors closer to each-other
swap(s, nextstart++, j);
}
}
}
printf("intersecting group's ymax = %d, ymin = %d\n", ymax, ymin);
if(ymax >= y1 && ymin <= y2) {
// intersecting group of sensors cover full height
printf("following group with above ymax and ymin covers full height\n");
printsensors(i, nextstart - 1, s);
return 0; // corridor doesn't exists
}
i = nextstart; // next sensor which didn't form intersecting group with previously considered sensors
}
return 1; // corridor exists
}
Test Program:
int main(int argc, char** argv) {
int N = 10;
if(argc > 1)
N = atoi(argv[1]);
int (*sensors)[N][3] = malloc(sizeof(*sensors));
srand(time(0));
int y2 = rand() % 50;
int y1 = y2 + rand() % 50 + 1;
for(int i = 0; i < N; i++) {
(*sensors)[i][0] = rand() % 100;
(*sensors)[i][1] = rand() % 100;
(*sensors)[i][2] = rand() % 10 + 1;
}
printf("[y1=%d, y2=%d]\n", y1, y2);
printsensors(0, N - 1, *sensors);
int ret = corridor(y1, y2, N, *sensors);
printf("corridor %sexists\n", ret? "": "doesn't ");
return 0;
}
Optimization for test program:
int overlapping(int y1, int y2, int n, int s[][3]) {
int i = 0;
int j = n - 1;
while(i < j) {
if(s[i][1] + s[i][2] >= y2 && s[i][1] - s[i][2] <= y1) {
i++;
continue;
}
if(!(s[j][1] + s[j][2] >= y2 && s[j][1] - s[j][2] <= y1)) {
j--;
continue;
}
if(i < j)
swap(s, i++ , j--);
}
n = (i == j)? i+1: i;
printf("sensors which atleast touch area bounded by y1[%d] and y2[%d]: %d\n", y1, y2, n);
printsensors(0, n - 1, s);
return n;
}
int main(int argc, char** argv) {
int N = 10;
if(argc > 1)
N = atoi(argv[1]);
int (*sensors)[N][3] = malloc(sizeof(*sensors));
srand(time(0));
int y2 = rand() % 50;
int y1 = y2 + rand() % 50 + 1;
for(int i = 0; i < N; i++) {
(*sensors)[i][0] = rand() % 100;
(*sensors)[i][1] = rand() % 100;
(*sensors)[i][2] = rand() % 10 + 1;
}
printf("[y1=%d, y2=%d]\n", y1, y2);
printsensors(0, N - 1, *sensors);
// optimization to consider sensors which atleast touch area bounded by y1 and y2;
N = overlapping(y1, y2, N, *sensors);
int ret = corridor(y1, y2, N, *sensors);
printf("corridor %sexists\n", ret? "": "doesn't ");
return 0;
}
how is the radius applied to a single sensor ?
- Anonymous April 29, 2018if radius is 2 and sensor is indicated by 'a',is below radius valid ?
x x x
xxx
xxaxx
xxx
x x x
Also can you travel diagonally on path without being detected ?