Katkat
Back

Design a URL Shortener

HackerRankSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSystem Design

Last updated

This question assesses the ability to design a URL shortening service (like Bitly) focusing on scalability, distributed ID generation, and efficient data retrieval.

Design a URL Shortener

Design a service that takes a long URL and returns a shorter, alias URL (e.g., bit.ly/xyz123). When a user visits the shortened URL, the service should redirect them to the original long URL.

Functional Requirements

  1. URL Shortening: Users can provide a long URL and receive a unique short link.
  2. Redirection: Visiting the short link must redirect to the original long URL.
  3. Custom Aliases: Users should optionally be able to define their own custom short URL.
  4. Analytics (Optional): Basic tracking of click counts.

Non-Functional Requirements

  1. Scalability: The system must support millions of requests per day.
  2. High Availability: Redirection must be extremely fast (latency < 100ms).
  3. Persistence: Shortened URLs should be stored reliably.

Constraints & Assumptions

  • Assume 100 million new URLs created per month.
  • Assume a 100:1 read-to-write ratio (10 billion redirects per month).
  • Links can expire after a certain period, or persist indefinitely.

Expectations

Provide a high-level design that includes:

  • API Endpoints: Define the request and response structures.
  • Data Model: Choose an appropriate database schema (SQL vs. NoSQL) and explain why.
  • ID Generation: Propose a mechanism for creating unique, collision-resistant short keys.
  • Caching Strategy: Explain how to optimize read-heavy traffic patterns.
  • System Diagram: Describe the components involved (Load Balancer, Web Server, Database, Cache).

Hints

Hint 1

Consider the trade-offs between using a random hash function versus a base-62 encoding of an auto-incrementing database ID.

Hint 2

Think about how a Distributed Cache like Redis can be placed in front of your database to handle the high volume of read requests.

Hint 3

Address how you would partition (shard) your data across multiple database instances if the total URL count grows into the billions.

Follow-up questions

  • How would you handle the 'collision' problem if two different users try to claim the same custom alias simultaneously?
  • How would you implement URL expiration or garbage collection for links that haven't been accessed in a year?
  • What strategies would you implement to prevent malicious users from spamming the system or creating short links to harmful content?