CareerCup

Question need to be precise Mental Graphix, though you can use a graph here and do a BFS. You also need dictionary, that given a name, return a pointer to the node in the graph so it is taken as a source vertex for running BFS.

use a graph to store all the cities and their distance, and use a hash map to store the city and weather report.

If most cities do not have their own stations, then I think a tree solution wouldn't work too well. In that case, you could stored weather stations in a hash map, using a two-dimensional spatial hash, subdividing the world into 'squares' with each weather station being hashed according to the 'square' into which it falls. Use different resolutions (from large to small squares) to quickly be able to narrow down the search to a small number of stations, then calculate the distance from the city in question to the remaining weather stations.
In the average case such a solution would be roughly constant in speed, as long as you have a fine-enough resolution for your hash squares.

we can implement this using singlely linked list ,consisting two items station name and temperature(to be precise) and pointer to next node(having nearest station name ). list is sorted on the basis of station name. So in order to get particular staion report we have to search in list(as list is sorted ,time consumed will be less) ,if found it will return temperature else temperature of next node

You may think of creating the Voronoi diagram of a 2D space and group all the cities based on that diagram. See the link below:
en.wikipedia.org/wiki/Voronoi_diagram

i would like someone to write an optimised code for this using hashmap...why hash map is useful in tnis case.

Graph for storing the location of city and also a flag which is set if a city having there weather station. Hash_map for storing weather report of city having there own weather station if any city don't have there weather station its value will be NULL (or any ).
Now check the city in graph if it have weather station then go to has table to find the weather report. If not check the nearest city having weather station.

Graph for storing the location of city and also a flag which is set if a city having there weather station. Hash_map for storing weather report of city having there own weather station if any city don't have there weather station its value will be NULL (or any ).
Now check the city in graph if it have weather station then go to has table to find the weather report. If not check the nearest city having weather station.

The meat of the problem is in determining the nearest weather station optimally. We can store two sorted lists - one by the x-coordinate and another by the y-coordinate of the cities. Then to find the closest cities we can start by finding the closest x and closest y coordinates from both lists; this would give two points from both lists. A point common between these pairs would be the closet neighboring city. If no such intersection exists, repeat again with next higher x and y values ( This would result in O(logn) searches)

Any cases where this could fail ?

Measure half of both

#include<iostream>
#include<queue>
#include<vector>
#include<climits>
#include<conio.h>
#include<string>
#include<string.h>
#include<set>
#include<algorithm>

using namespace std;

class W_report
{
private:
string city;
string report;


public:

int distance;

W_report()
{
city='\0';
report='\0';
distance=0;
}

W_report(string f, string l, int p) : city(f),report(l),distance(p)
{

}

void display()
{
if(distance>0 )
std::cout << " CITY : " << city << endl << " Weather Report : " << report << endl ;
}

void ldisplay() const
{
if(distance>0 )
std::cout << " CITY : " << city << endl << " Weather Report : " << report << endl ;
}

friend bool operator < (const W_report &p1, const W_report& p);

friend bool operator == (const W_report &p1, const W_report &p);
bool searchcity (const W_report p) const
{
if(city==p.city)
return true;
return false;
}
};


bool operator < (const W_report &p1,const W_report& p)
{
if(p1.distance < p.distance)
return true;

return false;
}

bool operator == (const W_report &p1, const W_report &p)
{
if((p1.distance==p.distance))
return true;
else
return false;
}

void printreport(W_report w)
{
w.display();
}

void main()
{
W_report w1("JALANDHAR","It will Rain",200);
W_report w2("DELHI","MAX temperature will be 32 degrees",300);
W_report w3("JAIPUR","MAX temperature will be 45 degrees",400);
W_report w4("PATNA","It could rain in the morning",500);
W_report w5("RANCHI","There will be no rain for 2 days",600);
W_report w6("CHANDIGARH","It will Rain heavily for today",250);
W_report w7("SRINAGAR","There will be snowfall today!!! ",150);
W_report w8("HISAR","No RAIN but MAX temperature will be 20 degrees only ",572);
W_report w9("NAINITAL","COULD be snowfall today",700);
W_report w10("MUMBAI","MAX temp will exceed 50 degrees ",1000);
W_report w11("BANGALORE","There will be no rain but MAX temperature will be 24 degrees ",1400);
W_report w12("CALCUTTA","MAX Temperature will be 40 degrees till evening, after that it could rain ",1600);
W_report w13("CHENNAI","In will rain for whole night ",1900);
W_report w14("HYDERABAD","There could be rain ",1300);

set <W_report, less<W_report> > perset;
perset.insert(w1);
perset.insert(w2);
perset.insert(w3);
perset.insert(w4);
perset.insert(w5);
perset.insert(w6);
perset.insert(w7);
perset.insert(w8);
perset.insert(w9);
perset.insert(w10);
perset.insert(w11);
perset.insert(w12);
perset.insert(w13);
perset.insert(w14);

set <W_report, less<W_report> > :: iterator persit;

persit=perset.begin();

for_each(perset.begin(),perset.end(),printreport );

W_report search_city("BARNALA","XYZ",380);

for(int i=0;persit != perset.end();persit++,i++)
{

if((*persit).searchcity(search_city))
{
(*persit).ldisplay();
break;
}

}

int ldistance=10000;
set <W_report, less<W_report> > :: iterator nearest_report;


if(persit == perset.end() )
{
cout << " CITY REPORT NOT FOUND IN THE GIVEN DATABASE : RETURNING NEAREST REPORT " << endl;
persit=perset.begin();
nearest_report=persit;
for(int i=0;persit != perset.end();persit++,i++)
{
if(ldistance<abs((*persit).distance-search_city.distance))
{
(*nearest_report).ldisplay();
break;
}
else
{
ldistance=abs((*persit).distance-search_city.distance);
nearest_report=persit;
}
}
}

getch();
}

We can have a data structure defined like this:
struct City
{ string Name,
string StateProvince,
string Country,
string Zip,
XCoordinate x,
YCoordinate y,
int Temerature
}

If City is found, return its Tempature;
else
{
find neighboring city within same zip,
if no zip find same stateprovince
calculate the distance of these cities via XCoordinate,YCoordinate
return the temperature of city obtained from previous step
}