Design a simple yelp system. Support the following features:

1. Add a restaurant with name and location.
2. Remove a restaurant with id.
3. Search the nearby restaurants by given location.

A location is represented by latitude and longitude, both in double. ALocationclass is given in code.

Nearby is defined by distance smaller thankKm .

Restaurantclass is already provided and you can directly callRestaurant.create()to create a new object. Also, aHelperclass is provided to calculate the distance between two location, useHelper.get_distance(location1, location2).

AGeoHashclass is provided to convert a location to a string. TryGeoHash.encode(location)to convert location to a geohash string andGeoHash.decode(string)to convert a string to location.

Notice

Learn aboutGeoHashhttp://www.lintcode.com/en/help/geohash/

Have you met this question in a real interview?

Yes

Example

addRestauraunt("Lint Cafe", 10.4999999, 11.599999) // return 1
addRestauraunt("Code Cafe", 10.4999999, 11.512109) // return 2
neighbors(10.5, 11.6, 6.7) // return ["Lint Cafe"]
removeRestauraunt(1) 
neighbors(10.5, 9.6, 6.7) // return []


// The distance between location(10.5, 11.6) and "Lint Code" is 0.0001099 km
// The distance between location(10.5, 11.6) and "Code Code" is 9.6120978 km

/**
 * Definition of Location:
 * class Location {
 * public:
 *     double latitude, longitude;
 *     static Location create(double lati, double longi) {
 *         // This will create a new location object
 *     }
 * };
 * Definition of Restaurant
 * class Restaurant {
 * public:
 *     int id;
 *     string name;
 *     Location location;
 *     static Restaurant create(string &name, Location &location) {
 *         // This will create a new restaurant object,
 *         // and auto fill id
 *     }
 * };
 * Definition of Helper
 * class Helper {
 * public:
 *     static get_distance(Location &location1, Location &location2) {
 *         // return distance between location1 and location2.
 *     }
 * };
 * class GeoHash {
 * public:
 *     static string encode(Location &location) {
 *         // return convert location to a GeoHash string
 *     }
 *     static Location decode(string &hashcode) {
 *          // return convert a GeoHash string to location
 *     }
 * };
 */

struct Node {
    double distance;
    Restaurant restaurant;
    Node(Restaurant _restaurant, double _distance) {
        restaurant = _restaurant;
        distance = _distance;
    }
    bool operator<(const Node& node) const {
        return distance < node.distance;
    }
};

class MiniYelp {
private:
    map<int, string> id2code;
    map<string, Restaurant> id2rest;
public:
    MiniYelp() {
        // initialize your data structure here.
    }

    // @param name a string
    // @param location a Location
    // @return an integer, restaurant's id
    int addRestaurant(string name, Location &location) {
        // Write your code here
        Restaurant restaurant = Restaurant::create(name, location);
        string hashcode = GeoHash::encode(location);
        hashcode = hashcode + "." + to_string(restaurant.id);
        id2code[restaurant.id] = hashcode;
        id2rest[hashcode] = restaurant;
        return restaurant.id;
    }

    // @param restaurant_id an integer
    void removeRestaurant(int restaurant_id) {
        // Write your code here
        if (id2code.find(restaurant_id) != id2code.end()) {
            id2rest.erase(id2code[restaurant_id]);
            id2code.erase(restaurant_id);
        }
    }

    // @param location a Location
    // @param k an integer, distance smaller than k miles
    // @return a list of restaurant's name and sort by 
    // distance from near to far.
    vector<string> neighbors(Location &location, double k) {
        // Write your code here
        vector<string> res;
        vector<Node> nodes;
        int len = get_length(k);
        string code = GeoHash::encode(location).substr(0, len);
        auto it = id2rest.lower_bound(code);
        for (; it != id2rest.end(); ++it) {
            if (it->first.substr(0, len) != code)
                break;
            double distance = Helper::get_distance(it->second.location, location);
            if (distance < k)
                nodes.push_back(Node(it->second, distance));
        }

        sort(nodes.begin(), nodes.end());
        for (const Node& node : nodes)
            res.push_back(node.restaurant.name);

        return res;
    }

    int get_length(double k) {
        vector<double >ERROR = {2500, 630, 78, 20, 2.4, 0.61, 0.076, 0.01911, 0.00478, 0.0005971, 0.0001492, 0.0000186};
        for (int i = 0; i < ERROR.size(); ++i)
            if (k  > ERROR[i])
                return i;
        return ERROR.size();
    }
};