Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
but the the initial size of the heap we need is n right? so wont it make the complexity nlogn
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);
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)
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).
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();
}
}
}
If we need to find all k points, then it can be done in O(nlogk).
- navin.nitjsr May 20, 2012We 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)