Lintcode 529. Geohash

Geohash is a hash function that convert a location coordinate pair into a base32 string.

Check how to generate geohash on wiki: Geohash or just google it for more details.

Try http://geohash.co/.

You task is converting a (latitude, longitude) pair into a geohash string.

Example

Example1

Input: 
lat = 39.92816697 
lng = 116.38954991
precision = 12 
Output: "wx4g0s8q3jf9"

Example2

Input: 
lat = -90
lng = 180
precision = 12 
Output: "pbpbpbpbpbpb"

Notice

1 <= precision <=12

Code (Java):

public class GeoHash {
    /*
     * @param latitude: one of a location coordinate pair 
     * @param longitude: one of a location coordinate pair 
     * @param precision: an integer between 1 to 12
     * @return: a base32 string
     */
    public String encode(double latitude, double longitude, int precision) {
        // write your code here
        int len = (precision * 5) % 2 == 0 ? precision * 5 / 2 : precision * 5 / 2 + 1;
        String latStr = generateCode(latitude, -90, 90, len);
        String longStr = generateCode(longitude, -180, 180, len);
        
        String geoHashCode = getGeoHash(latStr, longStr);
        StringBuilder finalCode = new StringBuilder();

        String dict = "0123456789bcdefghjkmnpqrstuvwxyz";

        for (int i = 0; i <= geoHashCode.length() - 5; i += 5) {
            int num = 0;
            for (int j = i; j < i + 5; j++) {
                num = num * 2 + Character.getNumericValue(geoHashCode.charAt(j));
            }

            finalCode.append(dict.charAt(num));
        }

        return finalCode.toString();
    }

    private String generateCode(double loc, double start, double end, int len) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            double mid = start + (end - start) / 2;
            if (loc <= mid) {
                sb.append('0');
                end = mid;
            } else {
                sb.append('1');
                start = mid;
            }
        }

        return sb.toString();
    }

    private String getGeoHash(String latitude, String longtitude) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < longtitude.length(); i++) {
            sb.append(longtitude.charAt(i));
            sb.append(latitude.charAt(i));
        }

        return sb.toString();
    }
}