How to design URL shortener leetcode?

Free Coding Questions Catalog
Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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'

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

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:

YouTube Videos

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!

TAGS
System Design Interview
CONTRIBUTOR
Design Gurus Team

GET YOUR FREE

Coding Questions Catalog

Design Gurus Newsletter - Latest from our Blog
Boost your coding skills with our essential coding questions catalog.
Take a step towards a better tech career now!
Explore Answers
What are the different types of concurrency?
What are interview questions on microservices architecture?
What are the differences between struct and class in C++?
Related Courses
Image
Grokking the Coding Interview: Patterns for Coding Questions
Grokking the Coding Interview Patterns in Java, Python, JS, C++, C#, and Go. The most comprehensive course with 476 Lessons.
Image
Grokking Data Structures & Algorithms for Coding Interviews
Unlock Coding Interview Success: Dive Deep into Data Structures and Algorithms.
Image
Grokking Advanced Coding Patterns for Interviews
Master advanced coding patterns for interviews: Unlock the key to acing MAANG-level coding questions.
Image
One-Stop Portal For Tech Interviews.
Copyright © 2024 Designgurus, Inc. All rights reserved.