In-Memory URL Shortener: Encode and Decode

Problem Statement

Design an in-memory URL shortening service. Your task is to implement a class URLShortener that provides two primary operations:

1. encode(long_url: str) -> str: Encodes a given long URL to a unique shortened URL starting with the prefix "http://short.ly/" followed by a unique alphanumeric key (e.g., "http://short.ly/abc12").
2. decode(short_url: str) -> str: Decodes a shortened URL back to its original long URL. If the short URL does not exist or is invalid, return an empty string "".

Requirements

• Consistency: Repeatedly calling encode on the same long_url must return the same shortened URL.
• Uniqueness: Different long URLs must never resolve to the same shortened URL.
• Efficiency: Both encode and decode should run in O(1) average time complexity.

Class Interface

class URLShortener:
    def __init__(self):
        pass

    def encode(self, long_url: str) -> str:
        """Encodes a URL to a shortened URL."""
        pass

    def decode(self, short_url: str) -> str:
        """Decodes a shortened URL to its original URL."""
        pass

Examples

Example 1

shortener = URLShortener()

url1 = "https://www.example.com/articles/system-design-basics"
short1 = shortener.encode(url1)
# Output: e.g., "http://short.ly/1" or "http://short.ly/aBcDeF"

assert shortener.decode(short1) == url1
assert shortener.encode(url1) == short1  # Must return identical short URL

Example 2

shortener = URLShortener()
assert shortener.decode("http://short.ly/nonexistent") == ""

Constraints

• 1 <= len(long_url) <= 2048
• long_url consists of printable ASCII characters.
• Up to 10^5 total calls will be made to encode and decode combined.
• All generated keys should use alphanumeric characters ([a-zA-Z0-9]).