1. Designing a URL Shortener in Java: FAANG Interviews

 

Designing a URL shortener is a classic system design problem that combines data structures, algorithms, and scalability considerations. In this article, we will explore how to design and implement a URL shortener in Java.

Requirements for a URL Shortener

Functional Requirements:

• Generate a short and unique URL for a given long URL.

• Redirect users from the short URL to the original long URL.

Non-Functional Requirements:

• Handle millions of URL mappings efficiently.

• Minimize latency in URL resolution.

• Ensure high availability and scalability.

---

Key Concepts

1. Data Structures

To map long URLs to short URLs efficiently, we use a HashMap:

• Key: The short URL identifier.

• Value: The original long URL.

Map<String, String> urlMap = new HashMap<>();

2. Collision Resolution Strategies

We need a strategy to generate unique identifiers to avoid collisions:

• Base62 Encoding: Use alphanumeric characters ([a-zA-Z0-9]) to encode unique IDs.

  public String encode(int id) {
      String chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
      StringBuilder sb = new StringBuilder();
      while (id > 0) {
          sb.append(chars.charAt(id % 62));
          id /= 62;
      }
      return sb.reverse().toString();
  }

• Hashing: Use a hashing algorithm like MD5 or SHA-256 to generate a hash of the long URL, and take a subset of the hash to create the short URL.

  public String generateHash(String url) throws NoSuchAlgorithmException {
      MessageDigest md = MessageDigest.getInstance("SHA-256");
      byte[] hash = md.digest(url.getBytes(StandardCharsets.UTF_8));
      return Base64.getUrlEncoder().withoutPadding().encodeToString(hash).substring(0, 8);
  }

3. Scalability and Performance Considerations

• Load Balancing: Distribute traffic among multiple servers to ensure high availability.

• Horizontal Scaling: Add more servers for data storage and request handling.

• Sharding: Partition data based on the first few characters of the short URL.

4. Database Design

For storing mappings between long and short URLs, a relational database schema might look like this:

Column	Data Type	Description
id	BIGINT	Primary key, auto-increment
short_url	VARCHAR(10)	Unique short URL identifier
long_url	TEXT	Original long URL
created_at	TIMESTAMP	Timestamp for creation

Indexes on

short_url

and

long_url

will optimize lookups.

Alternatively, use NoSQL databases like MongoDB for scalability:

{
  "short_url": "abc123",
  "long_url": "https://example.com/very/long/url",
  "created_at": "2025-01-01T12:00:00Z"
}

5. Cache Management

Use caching to speed up lookups for frequently accessed short URLs:

• Use Redis or Memcached.

• Implement a Time-to-Live (TTL) to manage cache expiration.

import redis.clients.jedis.Jedis;
Jedis jedis = new Jedis("localhost");
jedis.set("abc123", "https://example.com/very/long/url");

---

Implementation in Java

URL Shortening Service

import java.util.*;

public class URLShortener {
    private Map<String, String> urlMap;
    private Map<String, String> reverseMap;
    private static final String DOMAIN = "https://short.ly/";
    private static final String CHARSET = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private static final int BASE = 62;

    public URLShortener() {
        urlMap = new HashMap<>();
        reverseMap = new HashMap<>();
    }

    public String shortenURL(String longUrl) {
        if (reverseMap.containsKey(longUrl)) {
            return DOMAIN + reverseMap.get(longUrl);
        }
        String shortUrl = generateShortUrl();
        urlMap.put(shortUrl, longUrl);
        reverseMap.put(longUrl, shortUrl);
        return DOMAIN + shortUrl;
    }

    public String expandURL(String shortUrl) {
        String key = shortUrl.replace(DOMAIN, "");
        return urlMap.getOrDefault(key, "URL not found");
    }

    private String generateShortUrl() {
        Random random = new Random();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.append(CHARSET.charAt(random.nextInt(BASE)));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        URLShortener shortener = new URLShortener();
        String shortUrl = shortener.shortenURL("https://example.com/very/long/url");
        System.out.println("Short URL: " + shortUrl);
        System.out.println("Original URL: " + shortener.expandURL(shortUrl));
    }
}

---

Advanced Features

• Custom Short URLs: Allow users to define their custom alias.

• Analytics: Track click counts and geographical data.

• Expiration: Set expiration for short URLs.

---

Conclusion

By leveraging the above strategies, you can design a scalable and efficient URL shortener in Java. This problem demonstrates the importance of data structures, hashing, database design, and performance optimization.

Please stay tune, I will update Point 2 of FANNG Interview series, Please check top 10 interview questions here.