C++ Solution using Random (Just for fun)


  • 0
    Y

    Well, personally, I think this question is a sort of system design one that should include some other software like database, memory cache and etc. System design interviews usually target at system architect level design rather than algorithm design and analysis. The below solution of course is not stateless and not scalable unless the unordered_map becomes a distributed memcache.
    For a stateless solution, I think this stackoverflow link can be helpful (But it stills somewhat relies on database :-( ). Or we can just use some classic reversible encryption algorithm like DES and RSA of which the tinyUrl returned is the encrypted message of longUrl.

    class Solution {
    public:
        Solution(){
            shortToLongUrlMapping.clear();
            srand (time(NULL));
        }
        
        // Encodes a URL to a shortened URL.
        string encode(string longUrl) {
            string shortUrl('a',5);
            int idx = 0, randomVal = 0;
            while(shortToLongUrlMapping.find(shortUrl) != shortToLongUrlMapping.end()){
                randomVal = rand() % 62;
                if(randomVal >= 0 && randomVal < 26)
                    shortUrl[idx] = ('A' + randomVal);
                else if(randomVal >= 26 && randomVal < 52)
                    shortUrl[idx] = ('a' + (randomVal - 26));
                else
                    shortUrl[idx] = ('0' + (randomVal - 52));
                idx = (idx + 1)%5;
            }
            shortToLongUrlMapping[shortUrl] = longUrl;
            return shortUrl;
        }
    
        // Decodes a shortened URL to its original URL.
        string decode(string shortUrl) {
            string longUrl = shortToLongUrlMapping.find(shortUrl) != shortToLongUrlMapping.end() ? shortToLongUrlMapping[shortUrl] : shortUrl;
            return longUrl;
        }
    private:
        unordered_map<string,string> shortToLongUrlMapping;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.