As a follow up for Tiny URL, we are going to support custom tiny url, so that user can create their own tiny url.

Notice

Custom url may have more than 6 characters in path.

Have you met this question in a real interview?

Yes

Example

createCustom("http://www.lintcode.com/", "lccode")

>
>
 http://tiny.url/lccode
createCustom("http://www.lintcode.com/", "lc")

>
>
 error
longToShort("http://www.lintcode.com/problem/")

>
>
 http://tiny.url/1Ab38c   // this is just an example, you can have you own 6 characters.
shortToLong("http://tiny.url/lccode")

>
>
 http://www.lintcode.com/
shortToLong("http://tiny.url/1Ab38c")

>
>
 http://www.lintcode.com/problem/
shortToLong("http://tiny.url/1Ab38d")

>
>
 null

#include <cstdint>
using namespace std;

class TinyUrl2 {
public:
    /**
     * @param long_url a long url
     * @param a short key
     * @return a short url starts with http://tiny.url/
     */
    string createCustom(string& long_url, string& short_key) {
        // Write your code here
        string short_url = TINYURL + short_key;
        uint64_t id = shortKey2Id(short_key);

        if (id2url.find(id) != id2url.end() && 
            id2url[id] != long_url)
            return "error";

        if (url2id.find(long_url) != url2id.end() && 
            url2id[long_url] != id)
            return "error";

        if (id2url.find(id) != id2url.end() ||
            url2id.find(long_url) != url2id.end()) {
            return short_url;
        }

        if (custom_l2s.find(long_url) != custom_l2s.end() &&
            custom_l2s[long_url] != short_url) 
            return "error";

        if (custom_s2l.find(short_url) != custom_s2l.end() &&
            custom_s2l[short_url] != long_url) 
            return "error";

        custom_l2s[long_url] = short_url;
        custom_s2l[short_url] = long_url;

        return short_url;
    }

    /**
     * @param long_url a long url
     * @return a short 
     * url starts with http://tiny.url/
     */
    string longToShort(string& long_url) {
        // Write your code here
        if (custom_l2s.find(long_url) != custom_l2s.end())
            return custom_l2s[long_url];

        uint64_t id = 0;
        for (auto ch : long_url) {
            id = (id * 256ULL + ch) % MAX_ID;
        }

       if (url2id.find(long_url) != url2id.end()) {
           id = url2id[long_url];
       } else {
            while (id2url.find(id) != id2url.end() && id2url[id] != long_url)
            ++id;
       }

        id2url[id] = long_url;
        url2id[long_url] = id;

        string shortKey = id2ShortKey(id);

        return TINYURL + shortKey;
    }

    /**
     * @param short_url a short url starts with http://tiny.url/
     * @return a long url
     */
    string shortToLong(string& short_url) {
        // Write your code here
        if (custom_s2l.find(short_url) != custom_s2l.end())
            return custom_s2l[short_url];

        string shortKey = getShortKey(short_url);
        uint64_t id = shortKey2Id(shortKey);

        return id2url[id];
    }

private:
    map<string, string> custom_l2s;
    map<string, string> custom_s2l;
    map<uint64_t, string> id2url;
    map<string, uint64_t> url2id;


    const string TINYURL = "http://tiny.url/";
    const uint64_t MAX_ID = 56800235584ULL;

    string id2ShortKey(uint64_t id) {
        char c[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        string res;
        while (id > 0) {
            res += c[id % 62];
            id /= 62;
        }
        while (res.length() < 6) {
            res += 'a';
        }

        std::reverse(res.begin(), res.end());
        return res;
    }

    string getShortKey(string & short_url) {
        return short_url.substr(TINYURL.size());
    }

    uint64_t shortKey2Id(string &shortKey) {
        uint64_t id = 0;
        for (char ch : shortKey) {
            if (ch >= 'a' && ch <= 'z')
                id = id * 62 + ch - 'a';
            if (ch >= 'A' && ch <= 'Z')
                id = id * 62 + ch - 'A' + 26;
            if (ch >= '0' && ch <= '9')
                id = id * 62 + ch - '0' + 52;
        }
        return id;
    }

};