How to design URL shortener leetcode?

Whether you're prepping for a coding interview on LeetCode or just curious about how these services work, designing a URL shortener is a fantastic way to sharpen your skills. Let’s break it down step by step.

Understanding the Basics

A URL shortener takes a lengthy web address and converts it into a shorter, more manageable link. This makes sharing links easier and looks cleaner, especially on platforms with character limits.

Example

• Original URL: https://www.example.com/articles/how-to-design-a-url-shortener
• Short URL: https://short.ly/xyz789

When someone clicks on https://short.ly/xyz789, they’re redirected to the original long URL.

Key Components of a URL Shortener

Designing a URL shortener involves several important parts. Let’s explore each one.

1. Encoding the URL

This is where you convert the long URL into a short, unique code.

How It Works

• Generate a Unique Code: Create a short string (like xyz789) that uniquely represents the original URL.
• Mapping: Store this code along with the original URL in a database.

Simple Approach

Use a counter that increments with each new URL and convert it to a base62 string (using letters and numbers) to create the unique code.

2. Decoding the URL

This part takes the short code and retrieves the original URL.

How It Works

• Lookup: When someone clicks the short URL, the system looks up the code in the database.
• Redirect: The user is redirected to the original long URL.

3. Database Design

The database stores the relationship between short codes and original URLs.

Schema Example

• ID: Primary key.
• Short Code: Unique identifier for the short URL.
• Original URL: The full web address.
• Creation Date: When the short URL was created.

Implementing the URL Shortener on LeetCode

LeetCode often presents this problem as designing two functions: encode and decode.

Step-by-Step Implementation

1. Initialize Data Structures

   • Use a hash map to store the mappings between the short code and the original URL.
   • Use a counter to generate unique IDs.

2. Encode Function

   • Increment the counter.
   • Convert the counter to a base62 string to get the short code.
   • Store the mapping in the hash map.
   • Return the short URL by appending the short code to a base URL.

3. Decode Function

   • Extract the short code from the short URL.
   • Look up the original URL in the hash map using the short code.
   • Return the original URL.

Example Code in Python

class Codec:
    def __init__(self):
        self.url_map = {}
        self.counter = 0
        self.base_url = "https://short.ly/"

    def encode(self, longUrl: str) -> str:
        self.counter += 1
        short_code = self._encode_base62(self.counter)
        self.url_map[short_code] = longUrl
        return self.base_url + short_code

    def decode(self, shortUrl: str) -> str:
        short_code = shortUrl.replace(self.base_url, "")
        return self.url_map.get(short_code, "")

    def _encode_base62(self, num):
        chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
        base = 62
        encoded = []
        while num > 0:
            encoded.append(chars[num % base])
            num = num // base
        return ''.join(reversed(encoded)) if encoded else '0'

Recommended Courses

Boost your understanding and get hands-on practice with these courses from DesignGurus.io:

• Grokking the Coding Interview: Patterns for Coding Questions
  https://www.designgurus.io/course/grokking-the-coding-interview

• Grokking Data Structures & Algorithms for Coding Interviews
  https://www.designgurus.io/course/grokking-data-structures-for-coding-interviews

Final Tips

• Practice Regularly: Solve similar problems on LeetCode to build your confidence.
• Understand the Concepts: Focus on how encoding and decoding work rather than just memorizing the code.
• Optimize Your Solution: Think about how to handle edge cases and improve the efficiency of your implementation.

Additional Resources

Enhance your preparation with these resources from DesignGurus.io:

Recommended Blogs

• Mastering the FAANG Interview: The Ultimate Guide for Software Engineers
  https://www.designgurus.io/blog/mastering-the-faang-interview-the-ultimate-guide-for-software-engineers

• Essential Software Design Principles You Should Know Before the Interview
  https://www.designgurus.io/blog/essential-software-design-principles-you-should-know-before-the-interview

YouTube Videos

• How to answer any System Design Interview Question
  https://youtu.be/zFXUxjlOCoo?si=BBb3py-Ne1vYxPjB

• System Design Interview Basics
  https://youtu.be/OdBB9Tm79x8?si=l4mrAdmpJFgQDLG3

Final Thoughts

Designing a URL shortener is a fantastic way to practice your coding and system design skills. By understanding the core components and implementing them step by step, you can build a functional and efficient service. Use the courses and resources from DesignGurus.io to deepen your knowledge and enhance your preparation. Keep practicing, stay curious, and you’ll ace your coding interviews in no time. Good luck!