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 ?

- Anonymous April 29, 2018 | Flag Reply
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.

- engineer06 April 29, 2018 | Flag Reply
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.

- Chris May 01, 2018 | Flag Reply
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[][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;
}

- badboy May 01, 2018 | Flag Reply
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[][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;
}

- badboy May 01, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More