Amazon Interview Question for Backend Developers


Country: United States
Interview Type: In-Person




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

that's a tricky one, it looks like one of the cluster algorithms, such as k-mean should be applied, but if your study didn't cover that, I would assume you are lost in some way.

1. Start by picking a first arbitrary point from the list of points not assigned to a cluster.
2. Then search within R-distance of that point at least one second point. If found, estimate a sphere center by averaging all those points coordinates. Then around this center, add all points within R distance of the center. If not found, extend the search to 2R. If not found, put that single point into a single sphere and do not further consider that point. If found, average the two points, try to find more points that potentially go into this sphere...
3. Repeat until no points are left which gives an initial guess of spheres.
(initial center selection could be done by observing point density and guess centers from a group of dense points, e.g. by separating the space into R/2 cubes in order to get a space-based index etc.
or another approach would be to first separate the space into this cubes and start searching from outside in ...)

4. At this stage a number of spheres will probably overlap and points can be assigned to multiple spheres.
5. use the points in conflict and assign it to the sphere with more points in it
6. clean up spheres that are empty, recompute centers, repeat 4 until no changes happen *

* it's not clear it will converge, so maybe a upper limit of passes and/or error limit must be given

- ChrisK May 18, 2017 | 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