## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

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

If we need to find all k points, then it can be done in O(nlogk).

We can store only k points in a min-heap of size k.
The value for inserting the element in heap is distance from origin which is (x^2+y^2)
Since the heap size is logk.
Hence, for insertion of n elements, total TC :- O(nlogk)

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

but the the initial size of the heap we need is n right? so wont it make the complexity nlogn

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

You would want to use max heap and not min heap

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

Min heap won't work!
It should be max heap!

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

And again klogk is not possible. It should be nlogk. One clear reason , you can't take n out as it is not possible to say about which are k smallest if you have not seen all the element!

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

Did you mean O(n log(n))? If not, then what's ur algo?

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

He probably meant N log(K). Of course it has to be at least O(N) because if you haven't looked at all the points, you don't know that there's not a closer one.

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

Can u plz give the solution??

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

yeah, I think the tc would have to be a function of N. if I try finding the nearest 3 points out of total 5 or total 500, the times required will be a lot different.

as for the algo, how about using a min heap of size k to store the points arranged by their distances from the origin.

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

Can u plz give the solution??

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

We can store the distances of all N points from origin in an array.
And then we can use selection algorithm to find kth minimum in array and partition the array according to that point in O(n).
So the overall complexity will be O(N);

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

When you use selection sort, the overall time complexity becomes O(kn) not O(n) ?

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

Brian, that is not selection sort. It is just the Quick select algorithm.

Ajax, that is good too.

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

1st solution: build a min heap of N points in O(N) time and retrieve K points from the top, complexity: O(N + K log N)

2nd solution: find the kth smallest element in O(N), then return return all points with distance closer than kth smallest; complexity: O(N)

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

Your second solutions would require an additional array of O(N) for finding the 'kth' smallest element of the array. I assume you are talking about 'Quick Select' algorithm.
But nice one though,
Time Complexity O(N)
Space Complexity O(N).

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

building a min heap will take O(nLogn)

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

We need a max heap here, dont we?
My code with max heap works just fine.

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

Time complexity: O(N + N log K)

``````void firstKPoints(multimap<int, int> &twoDpoints, size_t k, multimap<int, int> &kpoints)
{
multimap<float, map<int,int> > distKey;

//compute distance
for (multimap<int, int>::iterator it = twoDpoints.begin(); it != twoDpoints.end(); it++){
if (it->first > (int)k || it->second > (int)k)
continue;
float dist = sqrt(pow((float)it->first, (float)2.0)+pow((float)it->second, (float)2.0));
map<int,int> pnt;
pnt[it->first] = it->second;
distKey.insert(pair<float,map<int,int> >(dist, pnt));
}

//use limited size heap to sort distance
priority_queue<float> heapK;
for (multimap<float, map<int,int> >::iterator it = distKey.begin(); it != distKey.end(); it++){
float dist = it->first;
heapK.push(dist);
if (heapK.size() > k){
heapK.pop();
}
}

//output points
int pnum = 0;
while (!heapK.empty()){
pair<multimap<float,map<int,int> >::iterator,multimap<float,map<int,int> >::iterator> keyRange = distKey.equal_range(heapK.top());

for (multimap<float,map<int,int> >::iterator it = keyRange.first; it != keyRange.second; it++){
kpoints.insert(pair<int,int>(it->second.begin()->first, it->second.begin()->second));
pnum++;
if (pnum == k){
return;
}
heapK.pop();
}
}
}``````

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

let min=first x,y co-ordinate
for rest all (x,y)
if((x*x)+(y*y))<min
min=that x,y co-ordinate

index with min is the point

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

@pkn:- tumhara amazon me selection hua??

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

Use a temporary scratch array where each index will be having x^2 + y^2[of each D point].
Take a max-heap of size k & act accordingly.
The heap will contain k nearest points.

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

The exact complexity of the code is k for building max heap and log k for each of the elemetns after that

so the total complexity is O(k+(n-k)log k)

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.