Design a URL Shortener That Gives Each Long URL Exactly One Short URL

Design a URL shortener in the style of TinyURL. A user submits a long URL and gets back a short URL; anyone who opens the short URL is redirected to the long URL. Each short URL has an expiration date, after which it stops redirecting. The interview added one rule that shapes the rest of the design: the same long URL must always map to a single short URL. Shortening a long URL that already has a short URL returns the existing one instead of creating another. Without that rule, every request could simply create its own short URL with its own expiration date; with it, the design must also decide what a repeat request does to the existing expiration date, and what happens when two users shorten the same long URL at the same moment. Traffic, retention and latency targets were not reported, so agree on them with the interviewer first. ### Clarifying Questions - How many URLs are shortened per day, how many redirects per second arrive at peak, and how long must mappings be kept? - Is the one-short-URL rule global across all users, or does it apply per user or account? - Does "the same long URL" mean an identical string, or should equivalent spellings (letter case in the scheme and host, a default port, an empty path) count as the same URL? - Does every request carry its own expiration date, is there a default lifetime, and can a link be created that never expires? - After a short URL expires, may its code ever point to a different long URL? ### Part 1 — Create and redirect Design the create API and the redirect path: how short codes are generated, how mappings are stored, and how a redirect is served with low latency, including for codes that have expired. ```hint Size the code space Estimate how many short URLs will exist over the retention period, then ask how many characters a code needs and what each way of producing codes means for collisions. ``` #### What This Part Should Cover - Create and redirect APIs, including the HTTP status a redirect returns and what an expired or unknown code returns - Code generation and how it avoids or resolves collisions - The data model, and a read path served mostly from a cache that never outlives a link's expiration date ### Part 2 — One short URL per long URL, and its expiration date Enforce the rule that a long URL with an existing short URL gets that short URL back. Then decide what a second request for the same long URL does to the expiration date when it asks for a different lifetime than the first request did. ```hint Look it up the other way The redirect finds a mapping by its code. Ask what the create path must find it by, and how you would index a value that can be thousands of characters long. ``` ```hint Two requesters, one link Take a first requester who asked for a short lifetime and a second who asks for a long one, then the reverse, and ask what each of them expects to happen to the link they were given. ``` #### Clarifying Questions for this Part - May a later request shorten a link that an earlier requester was promised for longer? - When a long URL's short URL has already expired, should a new request get the old code back or a new one? #### What This Part Should Cover - Finding an existing mapping by its long URL, and what counts as the same URL - An explicit rule for the expiration date of a shared link, and its effect on earlier requesters - What happens after expiry: reviving the old code or issuing a new one, and never pointing a code at a different URL ### Part 3 — Two users shorten the same long URL at once Two users submit the same long URL, which has no short URL yet, at the same moment. Show that the system still ends up with exactly one short URL for it and that both users receive that short URL. ```hint Interleave the requests Trace two requests that both look for the long URL, both find nothing, and both insert. Ask which component can make that interleaving impossible rather than merely unlikely. ``` #### What This Part Should Cover - Why checking for the URL and then inserting it in application code is not enough - An atomic guarantee in the storage layer, and what the request that loses the race does - How the guarantee holds once the data is spread across several shards ### What a Strong Answer Covers - Requirements and scale estimates agreed before the design - A redirect path that stays fast under heavy reads and honours expiration dates - A precise definition of the same long URL, with the uniqueness rule enforced in one place - An expiration policy for shared links that is stated and justified rather than left implicit - Concurrency handled by an atomic storage-level guarantee, plus failure handling and monitoring ### Follow-up Questions - The mappings are sharded by short code for the redirect path. How do you still enforce one short URL per long URL? - Expired mappings must eventually be deleted to save space. How do you purge them without racing a new request for the same long URL, and without reusing a code for a different URL? - How would the design change if each user could have their own short URL for the same long URL, each with its own expiration date? - How would you keep the service from being used to disguise malicious links?