Amazon Interview Question

Country: United States

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

I guess it is about employing K-Nearest Neighbors(KNN) algorithm to solve the problem.

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

I can be wrong, but it looks very similar to the clustering problem. This algorithm might be used here - en.wikipedia.org/wiki/K-means_clustering

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

Is it to find any k nearest stars or find k-nearest stars to a given star?
Also what is the distance metric to be used?
eg: Euclidean, Manhattan or any other.

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

using kd tree is best option for this..

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

1) Is it closest to earth or a given star ?
In this case, u can just use max-heap

2) Is it find k closest among the given stars ?
This will be more complex and u might need KD trees.

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

K-D Trees are best when it comes to coordinates.
We can find k nearest stars to a given star but not sure how to find k nearest stars when no star is given.

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

May be we can follow the below approach.

1. Select a region with maximum density distribution.
2. Find the centroid of this region.
3. Find the k nearest stars to the centroid using K-D trees implementation.

I believe this should work, any one having any second thoughts on this?

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

@Varun - yes, what if k = 2 and there are two closest stars whose relative distance is smaller than their respective distance from the centroid. In short, the centroid need not always be a part of the set of 'k' closest stars.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use a max heap of k elements and add the stars based on the distance in 3D. You don't need to calculate the exact distance, just use this formula (x * x + y * y + z * z).

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

I think it has to do with relative distance rather than their distance from origin.
2 stars can be nearest to each other but might not even find a place in your heap.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Try this if it is to find the k closest stars from a given coordinate.

``````public Star[] findKClosest (Star[] stars, Coordinate origin, int k) {
PriorityQueue<Star> pqueue = PriorityQueue<Star> (k, new StarComperator());

for (int i = 0; i < stars.length; i++) {
int dist = dist(origin, starts[i].coord());

if (pqueue.size() == k && pqeue.peek() > dist) {
pqueue.pop();
}

}

return pqueue.toArray(new Star [0]);
}``````

Comment hidden because of low score. Click to expand.
-1
of 3 vote

An Amazon project manager(From Indian) asked me the same question in an interview.
Please note: 1 "huge set of stars as three dimensional coordinates" and 2 'k' has nothing to do with the distance by my understanding in the interview.
After the interview , I thought It might be have something with hash, because they always ask me 'hash this, hash that..' .
I had tried to use distance formula (x * x + y * y + z * z), but they said no. And even the closest
stars have a huge amount. I have no idea about K-Nearest Neighbors(KNN) and KD tree. But the question is how to deal with the huge amount stars by tree?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I totally agree with this.

They are looking for custom Hash implementation.

In Hashing, assume we are using alphabets to insert and hash algorithm is to insert the element equivalent to it's numeric value
[a=1,b=2,...z=26]

now nearest to any alphabet will have closest hash value.
So if you search closest hash value, you found nearest elements to given alphabet [here star]

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.