## Amazon Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

how is the radius applied to a single sensor ?

if 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 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

C code:

``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void printsensors(int n, int m, int s[]) {
printf("[");
for(int i = n; i <= m; i++)
printf("(%d, %d, %d), ", s[i], s[i], s[i]);
printf("\b\b]\n");
}

void swap(int s[], 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[]) {
for(int i = 0; i < n;) {
int nextstart = i + 1;
int ymax = s[i] + s[i];
int ymin = s[i] - s[i];
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] - s[j];
int y = s[k] - s[j];
int r = s[k] + s[j];
if(x*x + y*y <= r*r) {
if(ymax < s[j] + s[j])
ymax = s[j] + s[j];
if(ymin > s[j] - s[j])
ymin = s[j] - s[j];
// 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);
int (*sensors)[N] = 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] = rand() % 100;
(*sensors)[i] = rand() % 100;
(*sensors)[i] = 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Optimization for test program:

``````int overlapping(int y1, int y2, int n, int s[]) {
int i = 0;
int j = n - 1;
while(i < j) {
if(s[i] + s[i] >= y2 && s[i] - s[i] <= y1) {
i++;
continue;
}
if(!(s[j] + s[j] >= y2 && s[j] - s[j] <= 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);
int (*sensors)[N] = 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] = rand() % 100;
(*sensors)[i] = rand() % 100;
(*sensors)[i] = 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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.