Leetcode 1041. Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north.  The robot can receive one of three instructions:

• "G": go straight 1 unit;
• "L": turn 90 degrees to the left;
• "R": turn 90 degress to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: "GGLLGG"
Output: true
Explanation: 
The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.

Example 2:

Input: "GG"
Output: false
Explanation: 
The robot moves north indefinitely.

Example 3:

Input: "GL"
Output: true
Explanation: 
The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Note:

1. 1 <= instructions.length <= 100
2. instructions[i] is in {'G', 'L', 'R'}

Code (Java):

class Solution {
    int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int curX = 0;
    int curY = 0;
    int curDir = 0;    
    public boolean isRobotBounded(String instructions) {
        if (instructions == null || instructions.length() == 0) {
            return true;
        }
        

        for (int count = 0; count < 4; count++) {
            for (int i = 0; i < instructions.length(); i++) {
                char c = instructions.charAt(i);
                if (c == 'G') {
                    move();    
                } else {
                    turn(c);
                }
            }
        }
        
        return curX == 0 && curY == 0;
    }
    
    private void move() {
        curX += dirs[curDir][0];
        curY += dirs[curDir][1];
    }
    
    private void turn(char dir) {
        int dirVal = (dir == 'L' ? -1 : 1);
        curDir = (curDir + 4 + dirVal) % 4;
    }
}

Lintcode 555. Counting Bloom Filter

Description

中文English

Implement a counting bloom filter. Support the following method:

1. add(string). Add a string into bloom filter.
2. contains(string). Check a string whether exists in bloom filter.
3. remove(string). Remove a string from bloom filter.

Have you met this question in a real interview?  

Example

Example1

Input:
CountingBloomFilter(3)
add("lint")
add("code")
contains("lint") 
remove("lint")
contains("lint") 

Output: 
[true,false]

Example2

Input:
CountingBloomFilter(3)
add("lint")
add("lint")
contains("lint")
remove("lint")
contains("lint")

Output: 
[true,true]

Code (java):

class HashFunction {
    private int size;
    private int base;
    public HashFunction(int size, int base) {
        this.size = size;
        this.base = base;
    }

    public int hash(String str) {
        int hashCode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashCode = (int)(((long)hashCode * base + Integer.valueOf(str.charAt(i))) % size);
        }

        return hashCode;
    }
}

public class CountingBloomFilter {
    private List<HashFunction> hashFunctions;
    private int[] bloomFilter;
    /*
    * @param k: An integer
    **/
    public CountingBloomFilter(int k) {
        // do intialization if necessary
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            HashFunction func = new HashFunction(100000, 2 * i + 3);
            hashFunctions.add(func);
            bloomFilter = new int[100000];
        }
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            bloomFilter[hashCode] += 1;
        }
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void remove(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            bloomFilter[hashCode] -= 1;
        }
    }

    /*
     * @param word: A string
     * @return: True if contains word
     */
    public boolean contains(String word) {
        // write your code here
        for (HashFunction hashFunc : hashFunctions) {
            int hashCode = hashFunc.hash(word);
            if (bloomFilter[hashCode] <= 0) {
                return false;
            }
        }

        return true;
    }
}

Lintcode 556. Standard Bloom Filter

Description

中文English

Implement a standard bloom filter. Support the following method:

1. StandardBloomFilter(k),The constructor and you need to create k hash functions.
2. add(string). add a string into bloom filter.
3. contains(string). Check a string whether exists in bloom filter.

Have you met this question in a real interview?  

Example

Example1

Input:
CountingBloomFilter(3)
add("lint")
add("code")
contains("lint") 
remove("lint")
contains("lint") 

Output: 
[true,false]

Example2

Input:
CountingBloomFilter(3)
add("lint")
add("lint")
contains("lint")
remove("lint")
contains("lint")

Output: 
[true,false]

Code (Java):

class HashFunction {
    private int size;
    private int base;
    public HashFunction(int size, int base) {
        this.size = size;
        this.base = base;
    }

    public int hash(String str) {
        int hashCode = 0;
        for (int i = 0; i < str.length(); i++) {
            hashCode = ((hashCode * base) + Character.getNumericValue(str.charAt(i))) % size;
        }

        return hashCode;
    }
}

public class StandardBloomFilter {
    private BitSet bitSet;
    private int k;
    private List<HashFunction> hashFunctions;
    /*
    * @param k: An integer
    */public StandardBloomFilter(int k) {
        // do intialization if necessary
        this.k = k;
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            HashFunction func = new HashFunction(100000, 2 * i + 1);
            hashFunctions.add(func);
        }

        bitSet = new BitSet(100000);
    }

    /*
     * @param word: A string
     * @return: nothing
     */
    public void add(String word) {
        // write your code here
        for (int i = 0; i < k; i++) {
            int hashCode = hashFunctions.get(i).hash(word);
            bitSet.set(hashCode);
        }
    }

    /*
     * @param word: A string
     * @return: True if contains word
     */
    public boolean contains(String word) {
        // write your code here
        for (int i = 0 ; i < k; i++) {
            int hashCode = hashFunctions.get(i).hash(word);
            if (!bitSet.get(hashCode)) {
                return false;
            }
        }

        return true;
    }
}

Lintcode 566. GFS Client

Implement a simple client for GFS (Google File System, a distributed file system), it provides the following methods:

1. read(filename). Read the file with given filename from GFS.
2. write(filename, content). Write a file with given filename & content to GFS.

There are two private methods that already implemented in the base class:

1. readChunk(filename, chunkIndex). Read a chunk from GFS.
2. writeChunk(filename, chunkIndex, chunkData). Write a chunk to GFS.

To simplify this question, we can assume that the chunk size is chunkSize bytes. (In a real world system, it is 64M). The GFS Client's job is splitting a file into multiple chunks (if need) and save to the remote GFS server. chunkSize will be given in the constructor. You need to call these two private methods to implement read & write methods.

Example

GFSClient(5)
read("a.txt")
>> null
write("a.txt", "World")
>> You don't need to return anything, but you need to call writeChunk("a.txt", 0, "World") to write a 5 bytes chunk to GFS.
read("a.txt")
>> "World"
write("b.txt", "111112222233")
>> You need to save "11111" at chink 0, "22222" at chunk 1, "33" at chunk 2.
write("b.txt", "aaaaabbbbb")
read("b.txt")
>> "aaaaabbbbb"

Code (Java):

/* Definition of BaseGFSClient
 * class BaseGFSClient {
 *     private Map<String, String> chunk_list;
 *     public BaseGFSClient() {}
 *     public String readChunk(String filename, int chunkIndex) {
 *         // Read a chunk from GFS
 *     }
 *     public void writeChunk(String filename, int chunkIndex,
 *                            String content) {
 *         // Write a chunk to GFS
 *     }
 * }
 */



public class GFSClient extends BaseGFSClient {
    private int chunkSize;
    private Map<String, Integer> filenameToLastChunkIndexMap;
    /*
    * @param chunkSize: An integer
    */
public GFSClient(int chunkSize) {
        // do intialization if necessary
        this.chunkSize = chunkSize;
        filenameToLastChunkIndexMap = new HashMap<>();
    }

    /*
     * @param filename: a file name
     * @return: conetent of the file given from GFS
     */
    public String read(String filename) {
        if (!filenameToLastChunkIndexMap.containsKey(filename)) {
            return null;
        }
        // write your code here
        int lastChunkIndex = filenameToLastChunkIndexMap.get(filename);
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < lastChunkIndex; i++) {
            ans.append(readChunk(filename, i));
        }

        return ans.toString();
    }

    /*
     * @param filename: a file name
     * @param content: a string
     * @return: nothing
     */
    public void write(String filename, String content) {
        // write your code here
        int len = content.length();
        int chunkIndex = 0;
        for (int i = 0; i < len; i += chunkSize, chunkIndex++) {
            int end = Math.min(i + chunkSize, len);
            String chunkContent = content.substring(i, end);
            writeChunk(filename, chunkIndex, chunkContent);
        }

        filenameToLastChunkIndexMap.put(filename, chunkIndex);
    }
}

Lintcode 565. Heart Beat

Description

中文English

In the Master-Slave architecture, slave server will ping master in every k seconds to tell master server he is alive. If a master server didn't receive any ping request from a slave server in 2 * k seconds, the master will trigger an alarm (for example send an email) to administrator.

Let's mock the master server, you need to implement the following three methods:

1. initialize(slaves_ip_list, k). salves_ip_list is a list of slaves' ip addresses. k is define above.
2. ping(timestamp, slave_ip). This method will be called every time master received a ping request from one of the slave server. timestamp is the current timestamp in seconds. slave_ip is the ip address of the slave server who pinged master.
3. getDiedSlaves(timestamp). This method will be called periodically (it's not guaranteed how long between two calls). timestamp is the current timestamp in seconds, and you need to return a list of slaves' ip addresses that died. Return an empty list if no died slaves found.

You can assume that when the master started, the timestamp is 0, and every method will be called with an global increasing timestamp.

Have you met this question in a real interview?  

Example

Example1

Input: 
initialize(["10.173.0.2", "10.173.0.3"], 10)
ping(1, "10.173.0.2")
getDiedSlaves(20)
getDiedSlaves(21)
ping(22, "10.173.0.2")
ping(23, "10.173.0.3")
getDiedSlaves(24)
getDiedSlaves(42)

Output: 
["10.173.0.3"]
["10.173.0.2", "10.173.0.3"]
[]
["10.173.0.2"]

Explanation:
initialize(["10.173.0.2", "10.173.0.3"], 10)
ping(1, "10.173.0.2")
getDiedSlaves(20)
>> ["10.173.0.3"]
getDiedSlaves(21)
>> ["10.173.0.2", "10.173.0.3"]
ping(22, "10.173.0.2")
ping(23, "10.173.0.3")
getDiedSlaves(24)
>> []
getDiedSlaves(42)
>> ["10.173.0.2"]

Code (Java)

public class HeartBeat {
    Map<String, Integer> ipToTimestampMap;
    int k;
    public HeartBeat() {
        // do intialization if necessary
        ipToTimestampMap = new HashMap<>();
    }

    /*
     * @param slaves_ip_list: a list of slaves'ip addresses
     * @param k: An integer
     * @return: nothing
     */
    public void initialize(List<String> slaves_ip_list, int k) {
        // write your code here
        this.k = k;
        for (String ip : slaves_ip_list) {
            ipToTimestampMap.put(ip, -1);
        }
    }

    /*
     * @param timestamp: current timestamp in seconds
     * @param slave_ip: the ip address of the slave server
     * @return: nothing
     */
    public void ping(int timestamp, String slave_ip) {
        // write your code here
        if (ipToTimestampMap.containsKey(slave_ip)) {
            ipToTimestampMap.put(slave_ip, timestamp);
        }
    }

    /*
     * @param timestamp: current timestamp in seconds
     * @return: a list of slaves'ip addresses that died
     */
    public List<String> getDiedSlaves(int timestamp) {
        // write your code here
        List<String> diedIps = new ArrayList<>();
        for (String ip : ipToTimestampMap.keySet()) {
            int lastPingTime = ipToTimestampMap.get(ip);
            if (timestamp - lastPingTime >= 2 * k) {
                diedIps.add(ip);
            }
        }

        return diedIps;
    }
}

Lintcode 1786. Pub Sub Pattern

Description

中文English

Pub/Sub pattern is a wide used pattern in system design. In this problem, you need to implement a pub/sub pattern to support user subscribes on a specific channel and get notification messages from subscribed channels.

There are 3 methods you need to implement:

• subscribe(channel, user_id): Subscribe the given user to the given channel.
• unsubscribe(channel, user_id): Unsubscribe the given user from the given channel.
• publish(channel, message): You need to publish the message to the channel so that everyone subscribed on the channel will receive this message. Call PushNotification.notify(user_id, message) to push the message to the user.

Have you met this question in a real interview?  

Example

subscribe("group1",  1)
publish("group1", "hello")
>> user 1 received "Hello"
subscribe("group1", 2)
publish("group1", "thank you")
>> user 1 received "thank you"
>> user 2 received "thank you"
unsubscribe("group2", 3)
>> user 3 is not in group2, do nothing
unsubscribe("group1", 1)
publish("group1", "thank you very much")
>> user 2 received "thank you very much"
publish("group2", "are you ok?")
>> # you don't need to push this message to anyone

If there are more than 1 user subscribed on the same channel, it doesn't matter the order of time users receiving the message. It's ok if you push the message to user 2 before user 1.

Code (Java):

/* Definition of PushNotification
 * class PushNotification {
 *     public static void notify(int user_id, String the_message)
 *  };
 */
//
public class PubSubPattern {
    Map<String, Set<Integer>> channelTable;
    public PubSubPattern(){
     // Write your code here
     channelTable = new HashMap<>();
    }
    
    /**
     * @param channel: the channel's name
     * @param user_id: the user who subscribes the channel
     * @return: nothing
     */
    public void subscribe(String channel, int user_id) {
        // Write your code here
        Set<Integer> users = channelTable.getOrDefault(channel, new HashSet<>());
        users.add(user_id);
        channelTable.put(channel, users);
    }

    /**
     * @param channel: the channel's name
     * @param user_id: the user who unsubscribes the channel
     * @return: nothing
     */
    public void unsubscribe(String channel, int user_id) {
        // Write your code here
        if (channelTable.containsKey(channel)) {
            Set<Integer> users = channelTable.get(channel);
            users.remove(user_id);
        }
    }

    /**
     * @param channel: the channel's name
     * @param message: the message need to be delivered to the channel's subscribers
     * @return: nothing
     */
    public void publish(String channel, String message) {
        // Write your code here
        if (channelTable.containsKey(channel)) {
            Set<Integer> users = channelTable.get(channel);
            for (Integer user : users) {
                PushNotification.notify(user, message);
            }
        }
    }
}

Lintcode 525. Mini Uber

Description

中文English

Support two basic uber features:

1. Drivers report their locations.
2. Rider request a uber, return a matched driver.

When rider request a uber, match a closest available driver with him, then mark the driver not available.

When next time this matched driver report his location, return with the rider's information.

You can implement it with the following instructions:

• report(driver_id, lat, lng)
  • return null if no matched rider.
  • return matched trip information.
• request(rider_id, lat, lng)
  1. create a trip with rider's information.
  2. find a closest driver, mark this driver not available.
  3. fill driver_id into this trip.
  4. return trip

This is the definition of Trip in Java:

public class Trip {
    public int id; // trip's id, primary key
    public int driver_id, rider_id; // foreign key
    public double lat, lng; // pick up location
}

Have you met this question in a real interview?  

Example

Example 1:

Input:
  report(1, 36.1344, 77.5672) 
  report(2, 45.1344, 76.5672) 
  request(2, 39.1344, 76.5672) 
  report(1, 38.1344, 75.5672) 
  report(2, 45.1344, 76.5672) 
Output:
  null
  null
  Trip(rider_id: 2, driver_id: 1, lat: 39.1344, lng: 76.5672)
  Trip(rider_id: 2, driver_id: 1, lat: 39.1344, lng: 76.5672)
  null

Example 2:

Input:
  report(1, 36.1344, 77.5672)
  report(2, 45.1344, 76.5672)
  request(2, 39.1344, 76.5672)
  request(3, 78.1344, 134.5672)
Output:
  null
  null
  LOG(INFO): Trip(rider_id: 2, driver_id: 1, lat: 39.1344, lng: 76.5672)
  LOG(INFO): Trip(rider_id: 3, driver_id: 2, lat: 78.1344, lng: 134.5672)

Code (Java):

/**
 * Definition of Trip:
 * public class Trip {
 *     public int id; // trip's id, primary key
 *     public int driver_id, rider_id; // foreign key
 *     public double lat, lng; // pick up location
 *     public Trip(int rider_id, double lat, double lng);
 * }
 * Definition of Helper
 * class Helper {
 *     public static double get_distance(double lat1, double lng1,
                                         double lat2, double lng2) {
 *         // return distance between (lat1, lng1) and (lat2, lng2)
 *     }
 * };
 */

class Location {
    double lat;
    double lng;
    public Location(double lat, double lng) {
        this.lat = lat;
        this.lng = lng;
    }
}
public class MiniUber {
    private Map<Integer, Trip> tripTable;
    private Map<Integer, Location> locTable;

    public MiniUber() {
        // initialize your data structure here.
        tripTable = new HashMap<>();
        locTable = new HashMap<>();
    }

    // @param driver_id an integer
    // @param lat, lng driver's location
    // return matched trip information if there have matched rider or null
    public Trip report(int driver_id, double lat, double lng) {
        // if trip table contains driver_id, return it
        if (tripTable.containsKey(driver_id)) {
            return tripTable.get(driver_id);
        }
        
        Location loc = new Location(lat, lng);
        
        // report loc to location table
        locTable.put(driver_id, loc);
        
        return null;
    }

    // @param rider_id an integer
    // @param lat, lng rider's location
    // return a trip
    public Trip request(int rider_id, double lat, double lng) {
        // Write your code here
        Trip trip = new Trip(rider_id, lat, lng);

        double minDist = Integer.MAX_VALUE;
        int matchedDriver = -1;
        // find the cloeset driver
        for (Integer driver_id : locTable.keySet()) {
            Location loc = locTable.get(driver_id);
            double dist = Helper.get_distance(lat, lng, loc.lat, loc.lng);
            if (dist < minDist) {
                minDist = dist;
                matchedDriver = driver_id;
            }
        }

        if (matchedDriver != -1) {
            locTable.remove(matchedDriver);
        }

        trip.driver_id = matchedDriver;
        tripTable.put(matchedDriver, trip);

        return trip;
    }
}

Note:
For rider reports its location. It should first check the driver in the trip table. If yes, just return it first. 

Lintcode 530. Geohash II

This is a followup question for Geohash.

Convert a Geohash string to latitude and longitude.

Try http://geohash.co/.

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

Example

Example1

Input: "wx4g0s"`
Output: lat = 39.92706299 and lng = 116.39465332

Example2

Input: "w"
Output: lat = 22.50000000 and lng = 112.50000000

Code (Java):

public class GeoHash {
    /*
     * @param geohash: geohash a base32 string
     * @return: latitude and longitude a location coordinate pair
     */
    public double[] decode(String geohash) {
        // step1: get binary code
        //
        String binaryGeoHash = getBinaryGeoHash(geohash);

        // step 2: get binary representation of the long and latitude
        String[] binaryLongLati = getBinaryLongAndLati(binaryGeoHash);

        double longtitude = getLocation(binaryLongLati[0], -180, 180);
        double latitude = getLocation(binaryLongLati[1], -90, 90);

        double[] ans = new double[2];
        ans[0] = latitude;
        ans[1] = longtitude;

        return ans;
    }

    private double getLocation(String code, double start, double end) {
        double mid = start + (end - start) / 2;
        for (int i = 0; i < code.length(); i++) {
            if (code.charAt(i) == '0') {
                end = mid;
            } else {
                start = mid;
            }

            mid = start + (end - start) / 2;
        }

        return mid;
    }

    private String[] getBinaryLongAndLati(String binaryGeoHash) {
        String[] ans = new String[2];
        StringBuilder longtitude = new StringBuilder();
        StringBuilder latitude = new StringBuilder();

        for (int i = 0; i < binaryGeoHash.length(); i += 2) {
            longtitude.append(binaryGeoHash.charAt(i));
            if (i + 1 < binaryGeoHash.length()) {
                latitude.append(binaryGeoHash.charAt(i + 1));
            }
        }

        ans[0] = longtitude.toString();
        ans[1] = latitude.toString();

        return ans;
    }

    private String getBinaryGeoHash(String geohash) {
        String dict = "0123456789bcdefghjkmnpqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < geohash.length(); i++) {
            int base32 = dict.indexOf(geohash.charAt(i));
            sb.append(toBase2(base32));
        }

        return sb.toString();
    }

    private String toBase2(int num) {
        StringBuilder sb = new StringBuilder();
        while (num > 0) {
            sb.insert(0, num % 2);
            num /= 2;
        }
        
        // pad with zeros
        while (sb.length() < 5) {
            sb.insert(0, '0');
        }

        return sb.toString();
    }
}

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();
    }
}

lintcode 232. Tiny Url

Given a long url, make it shorter.

You should implement two methods:

• longToShort(url) Convert a long url to a short url which starts with http://tiny.url/.
• shortToLong(url) Convert a short url to a long url.

You can design any shorten algorithm, the judge only cares about two things:

1. The short key's length should equal to 6 (without domain and slash). And the acceptable characters are [a-zA-Z0-9]. For example: abcD9E
2. No two long urls mapping to the same short url and no two short urls mapping to the same long url.

Example

Example 1:

Input: shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
Output: "http://www.lintcode.com/faq/?id=10"
Explanation: 
  When longToShort() called, you can return any short url.
  For example, "http://tiny.url/abcdef".
  And "http://tiny.url/ABCDEF" is ok as well.

Example 2:

Input:
  shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
  shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
Output:
  "http://www.lintcode.com/faq/?id=10"
  "http://www.lintcode.com/faq/?id=10"

Code (Java):

public class TinyUrl {
    private GlobalCounter counter;
    private Map<Integer, String> idToLongURL;
    private Map<String, Integer> longURLToId;
    private String dict = "0123456789" + "abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public TinyUrl() {
        counter = new GlobalCounter();
        idToLongURL = new HashMap<>();
        longURLToId = new HashMap<>();
    }

    public String longToShort(String url) {
        // write your code here
        // find if the short url already exists
        if (longURLToId.containsKey(url)) {
            int id = longURLToId.get(url);
            return idToShortURL(id);
        }
        
        int id = counter.getNext();
        String shortURL = idToShortURL(id);
        
        idToLongURL.put(id, url);
        longURLToId.put(url, id);
        
        return shortURL;
    }

    /*
     * @param url: a short url starts with http://tiny.url/
     * @return: a long url
     */
    public String shortToLong(String url) {
        // write your code here
        int id = shortURLToId(url);
        
        return idToLongURL.get(id);
    }
    
    
    private String idToShortURL(int id) {
        StringBuilder sb = new StringBuilder();
        while (id > 0) {
            sb.insert(0, dict.charAt(id % 62));
            id /= 62;
        }

        while (sb.length() < 6) {
            sb.insert(0, '0');
        }
        
        String shortURL = "http://tiny.url/" + sb.toString();
        
        return shortURL;
    }
    
    private int shortURLToId(String shortURL) {
        int id = 0;
        shortURL = shortURL.substring(shortURL.length() - 6);
        for (int i = 0; i < shortURL.length(); i++) {
            id = id * 62 + base62(shortURL.charAt(i));
        }
        
        return id;
    }
    
    private int base62(char c) {
        if (c >= '0' && c <= '9') {
            return c - '0';
        } else if (c >= 'a' && c <= 'z') {
            return c - 'a' + 10;
        } else if (c >= 'A' && c <= 'Z') {
            return c - 'A' + 36;
        }
        
        return 0;
    }
}

class GlobalCounter {
    private int counter;
    public GlobalCounter() {
        counter = 1;
    }

    public int getNext() {
        int next = counter;
        counter += 1;
        return next;
    }
}