[Microsoft Question][LeetCode] Encode and Decode TinyURL

Problem: TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Approach: There are many approaches which we can take:

1. Counter: The problem here is the number of URLs can't be more than int / long range and the codes are predictable.
2. Random number: Problem here is again the number of URLs can't be more than int / long range and also collision can happen so encryption performance can be degraded.

Now our final approach is to generate random fixed length (say length = 6) and assign it to url while encrypting. The number of URLs can be generated using this approach is 62 ^ 6 which is very large number. We can increase the length if we want more URLs. 

Prediction of next code and collision are highly unlikely. 

Implementation in C#:

public class Codec 

{

    private const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

    private const int tinyUrlSize = 6;

    private const string tinyUrlPrefix = "http://tinyurl.com/";

    

    public string encode(string longUrl) 

    {    

        Random random = new Random();

        while(true)

        {

            string tinyUrl = string.Empty;

            for (int i = 0; i < tinyUrlSize; ++i)

            {

                tinyUrl += chars[random.Next(chars.Length)];

            }

            if (!urlMap.ContainsKey(tinyUrl))

            {

                urlMap[tinyUrl] = longUrl;

                return tinyUrlPrefix + tinyUrl;

            }

        }

    }

    public string decode(string shortUrl) 

    {    

        string key = shortUrl.Substring(tinyUrlPrefix.Length);

        if (!urlMap.ContainsKey(key))

        {

            return string.Empty;

        }

        return urlMap[key];

    }

    Dictionary<string, string> urlMap = new Dictionary<string, string>();

}

Complexity: O(length of chars)