Scale Engineer

Encode and Decode TinyURL

Med
#0519Time: `encode`: O(L) on average, where L is the length of the long URL. However, the worst-case time is unbounded due to the random generation loop. `decode`: O(S), where S is the length of the short URL, for string parsing and map lookup.Space: O(N * L), where N is the number of unique URLs encoded and L is the average length of a URL. We need to store two maps.1 company
Patterns
DesignHash Function
Data structures
Hash TableString
Companies
Shopify

Prompt

Note: This is a companion problem to the System Design problem: Design TinyURL.

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 a class to encode a URL and decode a tiny URL.

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.

Implement the Solution class:

  • Solution() Initializes the object of the system.
  • String encode(String longUrl) Returns a tiny URL for the given longUrl.
  • String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.

 

Example 1:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.com/problems/design-tinyurl"

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

 

Constraints:

  • 1 <= url.length <= 104
  • url is guranteed to be a valid URL.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach generates a random alphanumeric string of a fixed length (e.g., 6 characters) to serve as the unique key for each long URL. To handle potential collisions (where a newly generated random code is already in use), it retries the generation process until a unique code is found.

Algorithm

  • Encode(longUrl):
    1. Check if the longUrl has been encoded before by looking it up in a urlToCode map. If yes, return the existing short URL.
    2. If not, start a loop: a. Generate a random alphanumeric string (code) of a fixed length (e.g., 6). b. Check if this code already exists as a key in a codeToUrl map. c. If it's unique, exit the loop. Otherwise, repeat.
    3. Store the new mapping in both maps: codeToUrl.put(code, longUrl) and urlToCode.put(longUrl, code).
    4. Construct the full short URL by prepending a base host (e.g., http://tinyurl.com/) to the code and return it.
  • Decode(shortUrl):
    1. Extract the code from the shortUrl by removing the base host prefix.
    2. Look up this code in the codeToUrl map to find the original longUrl.
    3. Return the longUrl.

Walkthrough

When encode(longUrl) is called, we first check if we have already generated a short URL for this longUrl. If so, we return the stored short URL.

Otherwise, we enter a loop. In each iteration, we generate a random string of a fixed length using a predefined set of characters (e.g., 'a'-'z', 'A'-'Z', '0'-'9'). We then check if this randomly generated string (the code) has already been used as a key in our map. If the code is unique, we break the loop and store the mapping from this code to the longUrl, and also the reverse mapping from longUrl to the code for future lookups. The final short URL is constructed by appending this unique code to a base URL like http://tinyurl.com/.

The decode(shortUrl) function simply extracts the code from the shortUrl and looks it up in our map to retrieve the original longUrl.

public class Codec {    Map<String, String> codeToUrl = new HashMap<>();    Map<String, String> urlToCode = new HashMap<>();    static final String BASE_HOST = "http://tinyurl.com/";    static final String CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";    static final int CODE_LENGTH = 6;    Random rand = new Random();     public String encode(String longUrl) {        if (urlToCode.containsKey(longUrl)) {            return BASE_HOST + urlToCode.get(longUrl);        }        String code;        do {            StringBuilder sb = new StringBuilder();            for (int i = 0; i < CODE_LENGTH; i++) {                sb.append(CHARS.charAt(rand.nextInt(CHARS.length())));            }            code = sb.toString();        } while (codeToUrl.containsKey(code));         codeToUrl.put(code, longUrl);        urlToCode.put(longUrl, code);        return BASE_HOST + code;    }     public String decode(String shortUrl) {        return codeToUrl.get(shortUrl.replace(BASE_HOST, ""));    }}

Complexity

Time

`encode`: O(L) on average, where L is the length of the long URL. However, the worst-case time is unbounded due to the random generation loop. `decode`: O(S), where S is the length of the short URL, for string parsing and map lookup.

Space

O(N * L), where N is the number of unique URLs encoded and L is the average length of a URL. We need to store two maps.

Trade-offs

Pros

  • The generated short URLs are not predictable, which can be a desirable security feature.

  • The length of the short URL's path is fixed.

Cons

  • The encode operation has a non-deterministic time complexity. In the worst-case scenario, where many collisions occur, it could loop for a long time before finding a unique code.

  • Performance degrades significantly as the number of stored URLs increases, because the probability of collision rises.

  • It requires two maps to store the bidirectional relationship, increasing space usage compared to counter-based approaches that can derive the code from an ID.

Solutions

public class Encode_and_Decode_TinyURL { class Codec { private static final String BASE_HOST = "http://tinyurl.com/" ; private static final String SEED = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" ; // maintain 2 mapping relationships, could be in memory or database or disk file private Map < String , String > keyToUrl = new HashMap <>(); private Map < String , String > urlToKey = new HashMap <>(); // Encodes a URL to a shortened URL. public String encode ( String longUrl ) { if ( urlToKey . containsKey ( longUrl )) { // could also be collision and hash to different tinyUrl return BASE_HOST + urlToKey . get ( longUrl ); } String key = null ; do { StringBuilder sb = new StringBuilder (); for ( int i = 0 ; i < 6 ; i ++) { int r = ( int )( Math . random () * SEED . length ()); sb . append ( SEED . charAt ( r )); } key = sb . toString (); } while ( keyToUrl . containsKey ( key )); keyToUrl . put ( key , longUrl ); urlToKey . put ( longUrl , key ); return BASE_HOST + key ; } // Decodes a shortened URL to its original URL. public String decode ( String shortUrl ) { return keyToUrl . get ( shortUrl . replace ( BASE_HOST , "" )); } } } ############ public class Codec { private Map < String , String > m = new HashMap <>(); private int idx = 0 ; private String domain = "https://tinyurl.com/" ; // Encodes a URL to a shortened URL. public String encode ( String longUrl ) { String v = String . valueOf (++ idx ); m . put ( v , longUrl ); return domain + v ; } // Decodes a shortened URL to its original URL. public String decode ( String shortUrl ) { int i = shortUrl . lastIndexOf ( '/' ) + 1 ; return m . get ( shortUrl . substring ( i )); } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.decode(codec.encode(url));

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem