We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Encode and Decode TinyURL

Number: 535

Difficulty: Medium

Paid? No

Companies: Shopify, Adobe, Amazon, Microsoft, Google, Meta, Uber

Problem Description

Implement a URL shortening service that converts a long URL to a shortened version and decodes the shortened URL back to the original long URL. There is no restriction on how your algorithm should work, but ensure that a URL can be encoded to a tiny URL and that tiny URL can be reliably decoded to the original URL.

Key Insights

  • Use a hash table (or dictionary/map) to store the mapping between the tiny URL code and the original long URL.
  • Generate a unique key (e.g., a random 6-character string) to serve as the shortened identifier.
  • Handle potential collisions by regenerating the key when necessary.
  • Both encoding and decoding operations should be efficient (preferably O(1) time complexity).

Space and Time Complexity

Time Complexity: O(1) for both encode and decode operations on average.
Space Complexity: O(n), where n is the number of URLs stored.

Solution

We use a hash map to maintain the mapping between a randomly generated 6-character code and its corresponding long URL. For the encode function, a random code is generated and then concatenated with a base URL (e.g., http://tinyurl.com/). If the generated code already exists in the hash map (collision), we generate a new one until a unique code is obtained. The decode function simply extracts the code part from the tiny URL and looks up the original URL in the hash map.

Code Solutions

import string
import random

class Solution:
    def __init__(self):
        # Dictionary to map short code to long URL
        self.url_map = {}
        # Base URL for the tiny URL
        self.base_url = "http://tinyurl.com/"
    
    def encode(self, longUrl: str) -> str:
        # Generate a random 6-character string
        code = ''.join(random.choices(string.ascii_letters + string.digits, k=6))
        # Ensure the code is unique
        while code in self.url_map:
            code = ''.join(random.choices(string.ascii_letters + string.digits, k=6))
        # Map the code to the long URL
        self.url_map[code] = longUrl
        # Return the complete tiny URL
        return self.base_url + code

    def decode(self, shortUrl: str) -> str:
        # Extract code from the short URL by removing the base URL prefix
        code = shortUrl.split(self.base_url)[-1]
        # Return the original long URL
        return self.url_map.get(code, "")
← Back to All Questions