Design a scalable URL shortening service
Quick Overview
This question evaluates system-design and distributed-systems skills—including scalability, data modeling, unique ID generation and encoding, caching strategies, consistency, and operational fault tolerance—within the Coding & Algorithms domain for a Data Engineer position.
Microsoft
Feb 14, 2025, 12:00 AM
Data Engineer
Technical Screen
Coding & Algorithms
0
0
Design a highly scalable URL shortening service (like bit.ly).
Requirements:
- Provide an API to create a short URL for a given long URL.
- Provide an API to redirect (resolve) a short code back to the original long URL.
- The mapping must be unique (no two long URLs should end up with the same short code unless explicitly intended) and reversible (given a short code, you can retrieve the original URL).
- The system should handle high read traffic (redirects) and support horizontal scaling.
- Discuss caching and persistence choices.
Deliverables:
- High-level architecture (services, storage, caches, CDN/edge considerations).
- Data model/schema for storing mappings.
-
Strategy for generating short codes:
- Option A: hashing the long URL
- Option B: generating globally unique IDs and encoding them (e.g., Base62)
- How to guarantee global uniqueness across multiple instances/regions.
- Follow-up: If you use hashing, how do you detect and handle hash collisions? Provide at least two approaches and their tradeoffs.
Assumptions (state any others you need):
- Short codes should be as short as possible (e.g., 6–10 characters) and URL-safe.
- Redirect latency should be low (e.g., p95 < 50 ms) and the service must tolerate partial failures.