Design a URL Shortener (LLD)
The object model behind TinyURL — encoders, repositories, and expiry, without the distributed-systems layer.
Problem Statement
Design the low-level object model for a URL shortener. A client submits a long URL and receives a compact code; later, resolving that code returns the original URL if the mapping still exists and has not expired.
Keep the interview scope at LLD/OOD depth: classes, interfaces, ownership, invariants, and extension seams. Do not spend time on distributed key generation, regional replication, CDN routing, or analytics pipelines.
Business context
URL Shortener is a common Amazon, Microsoft, and Flipkart interview problem because it looks simple but quickly reveals design maturity. A strong answer separates key-generation policy from persistence, handles collisions explicitly, models expiry and hit counts cleanly, and exposes a small service facade instead of leaking map operations to callers.
Functional Requirements
Shorten a valid HTTP or HTTPS URL into a compact code.
Resolve a code back to the original URL when the mapping is active.
Support expiring mappings using a TTL supplied at shorten time or a default TTL.
Track the number of successful resolves per shortened URL.
Handle generated-code collisions by retrying a bounded number of times.
Support a custom alias path where the caller supplies the desired code.
Allow different shortening strategies, such as Base62 counter encoding or random tokens, without changing the service flow.
Non-Functional Requirements
Correctness
A code must map to at most one active URL. Collision handling must be part of the shorten flow, not a best-effort assumption.
Extensibility
New strategies such as random tokens, custom aliases, or branded prefixes should be additive classes behind ShorteningStrategy.
Low latency
The base design uses an in-memory map, so shorten and resolve are expected to be constant-time for interview-scale data.
Testability
Inject the repository, strategy, and clock so expiry, collisions, and code generation can be tested deterministically.
Encapsulation
Hit counts, expiry checks, and repository writes should be hidden behind domain objects and a service facade.
Requirement Clarification
QAre we designing a distributed tiny URL service?
No. This walkthrough is the object-design view. We model the service, repository, mapping, and generation strategy; distributed ID allocation is a production extension.
QDo custom aliases need special validation?
Yes. The sample accepts only alphanumeric characters plus hyphen and underscore. A real product can plug in stricter brand, abuse, or reserved-word rules.
QWhat happens when a code expires?
Resolve treats it as missing, deletes it from the repository, and does not increment the hit count. Cleanup can also be run asynchronously in production.
QShould hit count include failed resolves?
No. The base model increments hits only after a non-expired mapping successfully resolves.
QIs Base62 generation deterministic?
Yes. The repository owns a monotonic counter and Base62Strategy encodes each numeric id. Random and custom-alias strategies share the same service contract.
UML Class Diagram
Sequence Diagram
Entity Identification
UrlShortenerService
Facade for the use cases. It validates input, asks a strategy for a candidate code, saves atomically through the repository, resolves active mappings, and exposes hit counts.
UrlMapping
Domain record for one shortened URL. It stores the code, long URL, creation time, optional expiry, and successful hit count.
ShorteningStrategy
Policy interface for producing candidate codes. The service does not know whether the code came from a Base62 counter, random token, or caller-supplied alias.
Base62Strategy
Deterministic strategy that asks the repository for the next numeric id and encodes it using a fixed Base62 alphabet.
RandomTokenStrategy
Alternative strategy that builds fixed-length random tokens. Collisions are possible, so the service retry loop remains necessary.
CustomAliasStrategy
Alternative strategy that returns the caller-provided alias after validation. A collision becomes an alias-taken error instead of a silent overwrite.
UrlRepository
Repository abstraction for code lookup, atomic insertion, deletion, existence checks, and sequence allocation.
InMemoryUrlRepository
Interview-friendly repository backed by a concurrent map and atomic counter. It can be replaced by SQL, Redis, or another durable store without changing service logic.
Design Patterns Used
ShorteningStrategy isolates code-generation policy. Base62 counter encoding, random tokens, and custom aliases implement the same method and can be injected into the service.
UrlRepository hides storage details and exposes domain-friendly operations such as saveIfAbsent and nextId. The service does not depend on a map directly.
Static factory methods such as withBase62Defaults, ShorteningStrategy.random, and ShorteningStrategy.customAlias create configured variants without spreading constructor wiring across clients.
Step-by-Step Design
1Make the shortened URL a domain object
UrlMapping is more than a pair of strings. It owns creation time, optional expiry, and hit count, so lifecycle rules do not leak into controllers.
public boolean isExpired(Instant now) { Objects.requireNonNull(now, "now"); return expiresAt != null && !expiresAt.isAfter(now); } public synchronized long recordHit() { hitCount++; return hitCount; }2Put code generation behind a strategy
The service asks for a candidate code and does not care whether it came from a sequence, random generator, or custom alias. This keeps the orchestration stable.
public interface ShorteningStrategy { String generateCode(String longUrl, String customAlias, UrlRepository repository); }3Implement Base62 with a fixed alphabet
Base62Strategy must encode and decode consistently. The decode path multiplies by 62 and adds the digit value, exactly reversing positional encoding.
public String encode(long number) { if (number == 0) { return "0"; } StringBuilder encoded = new StringBuilder(); while (number > 0) { encoded.append(ALPHABET.charAt((int) (number % BASE))); number = number / BASE; } return encoded.reverse().toString(); }4Use repository save-if-absent as the collision boundary
Checking exists and then saving is not enough under concurrency. The repository exposes saveIfAbsent so insert is atomic and the service can retry on false.
if (repository.saveIfAbsent(mapping)) { return code; } if (hasCustomAlias(customAlias)) { throw new IllegalArgumentException("custom alias already exists: " + code); }5Resolve by checking expiry before counting hits
An expired code should behave like a miss and should not inflate analytics. Resolve removes expired mappings opportunistically and returns empty.
6Expose factory methods for common configurations
UrlShortenerService.withBase62Defaults gives demos and clients a safe default, while constructors still allow tests to inject a clock, repository, and strategy.
Complete Java Implementation
Explanation of Every Class
UrlMapping
Immutable identity and lifecycle fields plus a synchronized hit counter. It owns the expiry predicate and only increments hits through recordHit.
ShorteningStrategy
Strategy interface for candidate-code generation. It also exposes factory methods for random-token and custom-alias strategies so clients can choose policies without newing concrete helpers directly.
RandomTokenStrategy
Package-private strategy returned by ShorteningStrategy.random. It uses SecureRandom and a Base62 alphabet, so collisions are possible but rare and handled by the service retry loop.
CustomAliasStrategy
Package-private strategy returned by ShorteningStrategy.customAlias. It requires a caller-supplied alias and lets the service turn duplicate aliases into a clear error.
Base62Strategy
Deterministic strategy that calls repository.nextId and converts the number to Base62. Its decode method validates characters and reverses the positional encoding safely.
UrlRepository
Repository abstraction for lookup, atomic insert, deletion, existence checks, and numeric id allocation. This is the persistence seam for replacing memory with a database later.
InMemoryUrlRepository
Concurrent-map implementation of UrlRepository. putIfAbsent makes collision handling atomic and AtomicLong provides the counter used by Base62 generation.
UrlShortenerService
Facade that orchestrates validation, candidate-code generation, collision retries, expiry calculation, resolve, and hit-count reads. It depends only on the strategy and repository interfaces.
Main
Executable demo that shows Base62 default shortening, custom-alias shortening, successful resolve hit counting, and Base62 encode/decode round-tripping.
Dry Run
Sample input
Repository starts with sequence 100000 and no mappings. Default TTL is 30 days. Actions: shorten a product URL with Base62, resolve it twice, shorten a careers URL with custom alias jobs, then try the same alias again.
| Step | Action | Candidate code | Repository state | Hit count | Result |
|---|---|---|---|---|---|
| 1 | shorten(product URL) | Q0v | {Q0v -> product} | 0 | Returns Q0v |
| 2 | resolve(Q0v) | Q0v | {Q0v -> product} | 1 | Returns product URL |
| 3 | resolve(Q0v) | Q0v | {Q0v -> product} | 2 | Returns product URL again |
| 4 | shorten(careers URL, jobs) | jobs | {Q0v -> product, jobs -> careers} | 0 | Returns jobs |
| 5 | shorten(other URL, jobs) | jobs | unchanged | 0 | Throws alias already exists |
| 6 | resolve(expired Q0v) | Q0v | {jobs -> careers} | 2 | Returns empty and deletes Q0v |
Step 1 uses Base62 for repository id 100001, which encodes to Q0v with the chosen alphabet. Steps 2 and 3 increment hits only on active resolves. Step 5 shows custom alias collision behavior, and step 6 shows expiry cleanup.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| shorten with Base62 | O(maxAttempts × codeLength) | O(1) | Each attempt generates a short code and performs an atomic map insert. With a monotonic counter, collisions should be exceptional. |
| shorten with random token | O(maxAttempts × tokenLength) | O(1) | Random generation can collide, so the retry bound matters. |
| resolve active code | O(1) | O(1) | Map lookup, expiry check, synchronized hit increment, and return. |
| resolve expired code | O(1) | O(1) | Map lookup plus delete. No hit is recorded. |
| repository storage | - | O(N) | One mapping per active short code. |
The constant-time claims rely on average O(1) map operations and small codes. In production, durable stores, indexes, and cross-node coordination would dominate the latency model, but the object design remains the same.
Extensibility
New key strategy
Add a new ShorteningStrategy implementation, such as hash-based slugs, tenant-prefixed aliases, or dictionary words. The service loop still validates and saves atomically.
Durable repository
Implement UrlRepository using SQL, Redis, or a document store. Preserve saveIfAbsent as a uniqueness constraint or compare-and-set operation.
Custom alias policies
Add an alias validator or reservation list before CustomAliasStrategy returns a code. This handles profanity, brand names, and security-sensitive words.
Analytics events
Keep the synchronous hit counter for quick reads, then publish a resolve event to an analytics pipeline outside the core service.
Clock-driven tests
Because Clock is injected, tests can advance time deterministically and verify expiry without sleeping.
Alternative Designs
Hash the long URL
Generate the code from a hash of the long URL instead of a counter or random token. Identical URLs can naturally produce the same code if desired.
Tradeoffs
Deterministic, but collisions still exist and the code can become longer if you need stronger collision resistance.
Separate analytics service
Move hit counting out of UrlMapping and emit resolve events to an AnalyticsService or queue.
Tradeoffs
Better write throughput and richer analytics, but eventual consistency means hit count reads may lag.
Code allocator object
Extract retry and collision handling into a CodeAllocator that owns strategy plus repository uniqueness checks.
Tradeoffs
Useful when allocation rules become complex, but it adds another abstraction to a problem whose core flow is already small.
Common Mistakes
- ×
Mixing Base62, random, and custom-alias logic in one giant if statement inside the service.
- ×
Checking exists and then saving without an atomic insert, which can overwrite a mapping under concurrency.
- ×
Incrementing hit count before checking expiry, causing expired links to look popular.
- ×
Treating a custom alias collision like a random collision and silently choosing a different code.
- ×
Letting repository callers mutate the internal map directly instead of exposing domain operations.
- ×
Spending the entire answer on distributed HLD concerns and never naming the classes or patterns.
- ×
Using a Base62 decoder that ignores invalid characters or overflows silently.
Follow-up Interview Questions
QHow would you make the repository durable?
Implement UrlRepository with a database table keyed by code. saveIfAbsent becomes an insert with a unique constraint; nextId can come from a sequence.
QHow do you support per-user quotas?
Add an owner field to UrlMapping and check a QuotaPolicy before saving. Keep quota policy separate from code generation.
QWhat changes for random-code generation?
Inject ShorteningStrategy.random(length). The service already retries when saveIfAbsent returns false, so the collision path is shared.
QHow do you prevent abusive custom aliases?
Add an alias validator or moderation policy before save. Reject reserved words, trademarks, path traversal tokens, and suspicious Unicode confusables.
QHow would you return analytics without slowing resolve?
Return the URL after the local hit increment and publish an asynchronous event for detailed analytics. The core resolve path stays short.
Production Considerations
Uniqueness guarantee
Back saveIfAbsent with a database unique index, Redis SETNX, or another atomic primitive. This is the critical correctness boundary.
Abuse and safety
Validate destination URLs, block malware domains, rate-limit creation, and moderate custom aliases before exposing them publicly.
Expiry cleanup
Resolve can delete expired mappings opportunistically, but production systems should also run scheduled cleanup to control storage growth.
Observability
Track shorten success rate, collision retries, alias conflicts, expired resolves, and p95 resolve latency.
Migration path
The repository boundary lets you start in memory for interviews, move to SQL for correctness, then add cache layers without changing the facade.
What Interviewers Look For
Did you keep key generation behind ShorteningStrategy instead of hard-coding Base62 in the service?
Did you model saveIfAbsent as the collision boundary rather than a fragile check-then-put?
Did you explain custom alias behavior separately from random collision retries?
Did you check expiry before incrementing hit count?
Can you swap the in-memory repository for a durable implementation without changing service logic?
Did you keep the answer focused on LLD and avoid drifting into full distributed-system design?
Quiz
0/5 answered
1.Why is **ShorteningStrategy** an interface?
2.What is the purpose of **saveIfAbsent**?
3.When should hit count be incremented?
4.Why is a duplicate custom alias handled differently from a random collision?
5.What does **Base62Strategy.decode** do conceptually?
Practice Variants
Add user-owned links
IntermediateAdd ownerId to UrlMapping, require owners to resolve management APIs, and enforce per-user creation quotas.
Add an alias validator
BeginnerIntroduce an AliasPolicy that rejects reserved words, unsafe characters, too-short aliases, and profanity before the custom alias strategy returns.
Add a durable SQL repository
AdvancedImplement UrlRepository with a SQL table, unique index on code, a sequence for ids, and tests proving duplicate inserts fail cleanly.
Flashcards
Cheat Sheet
Core model: UrlShortenerService facade, UrlMapping domain object, UrlRepository abstraction, InMemoryUrlRepository storage, ShorteningStrategy interface.
Patterns: Strategy for code generation, Repository for storage, Factory Method for preconfigured service and strategy creation.
Shorten flow: validate URL → calculate expiry → generate candidate code → create UrlMapping → saveIfAbsent → retry or return code.
Resolve flow: validate code → find mapping → if missing return empty → if expired delete and return empty → record hit → return long URL.
Base62: encode repeatedly divides by 62 and reverses digits; decode multiplies accumulated value by 62 and adds the next digit.
Invariants: one code maps to at most one URL; custom alias collision is an error; expired links do not count as hits; repository insert is atomic.
Complexity: shorten O(maxAttempts × codeLength), resolve O(1), storage O(N).
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Gamma, Helm, Johnson, Vlissides
- BookEffective Java — Item 1 and Item 17 — Joshua Bloch
- DocsRefactoring Guru — Strategy Pattern
- BlogMartin Fowler — Repository — Martin Fowler