CareerCup

Read m values from the list into array, make a max heap out of it.

Now for each new value you read from the list, Peek at the max in the heap, if new value is lesser, remove the max from heap and insert the new value into the heap.

To compare two values, use the euclidean Distance.

Once you are done with the list, the array will contain the m closest.

Code will look something like this:

Point3D [] pointsArray = new Point3D [m];
 
for (int i = 0; i < m; i++)
{
    pointsArray[i] = LargeList.GetNext();
}
 
Heap <Point3D, EuclideanDistanceComparator> maxHeap = new Heap Heap <Point3D, EuclideanDistanceComparator>();
 
// Make sure heap uses this array.
// Not exactly good code, but... who cares?
 
maxHeap.SetArray(pointsArray);
  
  
while(LargeList.HasNext())
{
    Point3D currentPoint = LargeList.GetNext();
    Point3D currentMax = maxHeap.PeekMax();

    // currentPoint closer to earth than currentMax
    if (EuclideanDistanceComparator(currentPoint, currentMax) < 0)
    {
        maxHeap.DeleteMax();
        maxHeap.Insert(currentPoint);
    }
}

comment form the complexity part
mlogm for heap creation now suppose all the n-m entries will cause a shift in the heap so that will be (n-m)logm.
finally mlogm+(n-m)logm
(nlogm.)

Maintain a min-heap of m records and go through all the nodes...O(mlogn) time and O(m) space..

what's the definition of m-closest? any URL?

The origin is (0,0,0), so the closest will have the shortest distance from the origin. Distance from the origin = sqrt(x * x + y * y + z * z)

If we get these n distances in a list and sort them then the first m entires will give us the required result. But since n is O(billions) , sorting wont be a good option.

Keep min heap of m-records and find the max and min of that heap. Take (m+1)th record (say x).

if( x > max ) move to (m+2)
if( x< min || (min<x<max))remove max from heap, put x in place of that, and re-heapify

When all records are finished, the records i heap is the result. or u can do a heapsort at last.

maintaining a min-heap solves the problem, but no one mentioned the fact that everytime you test a node you have to calculate the value of d=sqrt(x^2+y^2+z^2) and then make a min-heap of the d's calculated so far...i mentioned it to make things clear for others...

yeh rightly said.

Square root is not needed.
Distance can be squared also - it is just a metric.
[And it is symmetrical about origin. Exchanging x,y,z does not change the distance.]
what does that mean?
That means |x_i -x_j| is also a distant metric.
Now I do not know in case I am making the statement correct or not - but |x| + |y| + |z| can be treated as distance from origin.

Shouldn't it be max-heap? So that when a new element comes, it always compares the root and possibly replaces it.

Yes it should be max heap.
make a max heap of first m records.
now compare rest of records to root. if distance is lesser replace it with root and call heapify again.
(n-m)logm

#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <math.h>
#include <time.h>
#include <queue>

class Point {
int x;
int y;
int z;
double distance;
public:
double distanceFromOrigin() {
return distance;
}
Point(int x_arg, int y_arg, int z_arg) {
x = x_arg;
y = y_arg;
z = z_arg;
distance = sqrt ( (double) (x * x + y * y + z * z) );
}
friend bool operator< (const Point &leftPoint, const Point &rightPoint);
friend std::ostream& operator<< ( std::ostream &outstr, const Point &p);
};

bool operator< (const Point &leftPoint, const Point &rightPoint) {
if (leftPoint.distance < rightPoint.distance)
return true;
else
return false;
}
std::ostream& operator<< ( std::ostream &outstr, const Point &P) {
outstr << "X:"<< P.x << " Y:"<< P.y<< " Z:" << P.z << " distance:" << P.distance;
return outstr;
}

template <size_t NUMCLOSEST>
void getNClosestPoints(std::vector<Point> &pointList, std::priority_queue<Point> &closestPoints) {
for(std::vector<Point>::iterator nextPoint = pointList.begin(); nextPoint!= pointList.end(); nextPoint++) {
if (closestPoints.size() < NUMCLOSEST) {
closestPoints.push(*nextPoint);
}
else
{
closestPoints.push(*nextPoint);
closestPoints.pop();
}
}

}

void inputAndFindClosest(unsigned int numPoints) {
std::vector<Point> pointList;
std::priority_queue<Point> closestList;
srand ( (unsigned int) time(NULL) );
for (unsigned int i = 0; i < numPoints; i++) {
pointList.push_back(Point(rand() % 1000, rand() % 1000, rand() % 1000));
}
getNClosestPoints<30> (pointList, closestList);
std::cout << "Point List " << std::endl;
for (std::vector<Point>::iterator iter = pointList.begin(); iter != pointList.end(); iter++)
{
std::cout << *iter << std::endl;
}
std::cout << "PointList " << std::endl;
for (std::vector<Point>::iterator iter = pointList.begin(); iter != pointList.end(); iter++)
{
std::cout << *iter << std::endl;
}
std::cout << "Closest List " << std::endl;
while (!closestList.empty()) {
std::cout << closestList.top() << std::endl;
closestList.pop();
}
}

void test2() {
inputAndFindClosest(10);
inputAndFindClosest(30);
inputAndFindClosest(100);
}

sachin sinh gaur : plz don't write such big chunk of codes without proper explanation. but i think you're following the standard approach, in that case its fine. but again you missed Lord's recommendation of not using the sqrt just getting the sum of x^2+y^2+z^2 is good enough. keep things simple as far as possible.

Hi All,

I think the approach is right by making a min heap and maintaining its size of m. But I think the code can be further optimised by keeping the variable max of(+ and -ve) x,y,z-coordinates of the heap that creates a cube centered around the point, this square is then shrunked when the heap is updated. This shall reducing computations as only points within the cube is checked for distance and is updated if needed

... this cube is then shrunked ... {Instead of square, it must be cube}

music interest groups <a href=http://royalmp3.net/artist28731/saimir-pirgu-discography/>Saimir Pirgu</a> music they all laughed at christopher columbus http://royalmp3.net/artist4204/m-sphere-discography/ thai country music http://royalmp3.net/artist3334/blazing-eternity-discography/
out of the blue movie http://moviestrawberry.com/hqmoviesbycountry/country_canada/?page=9 hairy mature hardcore movie gay <a href=http://moviestrawberry.com/films/film_john_doe/>fargo movie</a> now and then movie release <a href=http://moviestrawberry.com/films/film_canes/>canes</a>
available arizona music and poetry grants 2007 2008 <a href=http://royalmp3.net/artist14882/dj-trax-discography/>DJ Trax</a> skinhead music videos download <a href=http://royalmp3.net/artist248/anima-in-fiamme-discography/>music notes jpegs</a>
movie database links http://moviestrawberry.com/films/film_mr_bones/ ultraviolet movie links view free online <a href=http://moviestrawberry.com/hqmoviesbycountry/country_uk/?page=10>movie about korean war and greek soldiers</a> daily sex movie free <a href=http://moviestrawberry.com/films/film_bless_the_child/>bless the child</a>
amor eterno music sheets for the violine <a href=http://royalmp3.net/artist19522/duplex-100-discography/>Duplex 100</a> new music building <a href=http://royalmp3.net/artist3974/dj-pubert-discography/>plimsoles music</a>
the nanny diaries movie endings http://rusfilms.com/page/3/ catalina cruz lesbian movie <a href=http://rusfilms.com/page/4/>gift movie</a>

class Heap{
      PriorityQueue<Double> Q;
      int m;
      Heap(File f,int m)
      {  
           this.m = m;
           Q = new ProrityQueue<Double>(m,new Comparator<Double>{compareTo(Double a,Integer b){return -a.compareTo(b)}})
           Scanner sc = new Scanner(f);
           int a[] , i=0; 
           while(sc.hasNextDouble && m>0)
           {
              a[i]=sc.nextDouble();m--;
              if(i==3){
              Q.add(calculateDistance(a));i=0;
              }
           }
           while(sc.hasNextDouble)
           {
             double x = sc.nextDouble();
             if(x < Q.peek()
             {
               Q.poll();
               Q.add(x);
             } 
           } 
      }
 Double calculateDistance(int a[]){
    return (a[0]*a[0]+a[1]*a[1]+a[2]*a[2]);
 }

 public PriorityQueue<Double> getMNear()
 {
       return Q;
 } 
}