Encode and Decode TinyURL

Encode and Decode TinyURL

What is this problem about?

The Encode and Decode TinyURL coding problem is a system design-lite task. You need to implement a service that shortens a long URL into a short one (like http://tinyurl.com/4e9iAk) and then redirects the short URL back to the original long one. You must provide two functions: encode(longUrl) and decode(shortUrl).

Why is this asked in interviews?

This is a very popular question at companies like Uber, Amazon, and Salesforce because it mirrors a real-world system architecture problem. It evaluates a candidate's knowledge of hash table interview pattern and their ability to generate unique identifiers. It also opens up discussions about collision handling, database scaling, and the trade-offs between different hashing algorithms.

Algorithmic pattern used

The problem is typically solved using a Bi-directional Mapping with a Hash Map.

1. Hash Map: Store the relationship between short codes and long URLs.
2. Unique Code Generation:
   • Counter-based: Use an auto-incrementing integer and convert it to Base62.
   • Randomized: Generate a random string of fixed length (e.g., 6 characters) and check for collisions in the map.
   • Hashing: Use a hash function (like MD5) on the long URL, though this requires handling collisions explicitly.

Example explanation

Long URL: https://www.google.com

1. Encoding:
   • Generate a unique code: a1B2c3.
   • Store in map: { "a1B2c3": "https://www.google.com" }.
   • Return: http://tinyurl.com/a1B2c3.
2. Decoding:
   • Extract code from the URL: a1B2c3.
   • Look up in map: Returns https://www.google.com.

Common mistakes candidates make

• Not handling collisions: Assuming a random code will always be unique without checking the database/map.
• Inefficient storage: Storing the same long URL multiple times with different short codes (unless the problem specifically allows it).
• Security: Using predictable sequential IDs which might allow someone to "scrape" all shortened URLs.

Interview preparation tip

During the interview, mention the scale. For a real TinyURL service, you'd need to consider how many URLs are generated per second and how long they should be stored. This shows you can think about the problem from a distributed systems perspective.