Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
Note: This is a companion problem to the System Design problem: Design TinyURL.
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.
There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
Implement the Solution class:
Solution() Initializes the object of the system.String encode(String longUrl) Returns a tiny URL for the given longUrl.String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.Example 1:
Input: url = "https://leetcode.com/problems/design-tinyurl" Output: "https://leetcode.com/problems/design-tinyurl" Explanation: Solution obj = new Solution(); string tiny = obj.encode(url); // returns the encoded tiny url. string ans = obj.decode(tiny); // returns the original url after decoding it.
Constraints:
1 <= url.length <= 104url is guranteed to be a valid URL.Problem summary: Note: This is a companion problem to the System Design problem: Design TinyURL. TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL. Implement the Solution class: Solution() Initializes the object of the system. String encode(String longUrl) Returns a tiny URL for the given longUrl. String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Design
"https://leetcode.com/problems/design-tinyurl"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #535: Encode and Decode TinyURL
public class Codec {
private Map<String, String> m = new HashMap<>();
private int idx = 0;
private String domain = "https://tinyurl.com/";
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
String v = String.valueOf(++idx);
m.put(v, longUrl);
return domain + v;
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
int i = shortUrl.lastIndexOf('/') + 1;
return m.get(shortUrl.substring(i));
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
// Accepted solution for LeetCode #535: Encode and Decode TinyURL
type Codec struct {
m map[int]string
idx int
}
func Constructor() Codec {
m := map[int]string{}
return Codec{m, 0}
}
// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
this.idx++
this.m[this.idx] = longUrl
return "https://tinyurl.com/" + strconv.Itoa(this.idx)
}
// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
i := strings.LastIndexByte(shortUrl, '/')
v, _ := strconv.Atoi(shortUrl[i+1:])
return this.m[v]
}
/**
* Your Codec object will be instantiated and called as such:
* obj := Constructor();
* url := obj.encode(longUrl);
* ans := obj.decode(url);
*/
# Accepted solution for LeetCode #535: Encode and Decode TinyURL
class Codec:
def __init__(self):
self.m = defaultdict()
self.idx = 0
self.domain = 'https://tinyurl.com/'
def encode(self, longUrl: str) -> str:
"""Encodes a URL to a shortened URL."""
self.idx += 1
self.m[str(self.idx)] = longUrl
return f'{self.domain}{self.idx}'
def decode(self, shortUrl: str) -> str:
"""Decodes a shortened URL to its original URL."""
idx = shortUrl.split('/')[-1]
return self.m[idx]
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))
// Accepted solution for LeetCode #535: Encode and Decode TinyURL
use std::collections::HashMap;
const BASE: &str = "http://tinyurl.com";
struct Codec {
url_map: HashMap<String, String>,
}
impl Codec {
fn new() -> Self {
Self {
url_map: HashMap::new(),
}
}
// Encodes a URL to a shortened URL.
fn encode(&mut self, longURL: String) -> String {
let short_url = format!("{}{}", BASE, Self::generate_hash(&longURL));
self.url_map.insert(short_url.clone(), longURL.clone());
short_url
}
// Decodes a shortened URL to its original URL.
fn decode(&self, shortURL: String) -> String {
self.url_map.get(&shortURL).unwrap().clone()
}
fn generate_hash(url: &String) -> i32 {
let mut hash = 5831;
for ch in url.chars() {
hash = ((hash << 5) + hash) + (ch as i32);
}
hash
}
}
// Accepted solution for LeetCode #535: Encode and Decode TinyURL
const encodeMap = {};
const decodeMap = {};
let size = 0;
/**
* Encodes a URL to a shortened URL.
*/
function encode(longUrl: string): string {
if (!encodeMap.hasOwnProperty(longUrl)) {
let shortUrl = size + 1;
size += 1;
encodeMap[longUrl] = shortUrl;
decodeMap[shortUrl] = longUrl;
}
return encodeMap[longUrl];
}
/**
* Decodes a shortened URL to its original URL.
*/
function decode(shortUrl: string): string {
return decodeMap[shortUrl];
}
/**
* Your functions will be called as such:
* decode(encode(strs));
*/
Use this to step through a reusable interview workflow for this problem.
Use a simple list or array for storage. Each operation (get, put, remove) requires a linear scan to find the target element — O(n) per operation. Space is O(n) to store the data. The linear search makes this impractical for frequent operations.
Design problems target O(1) amortized per operation by combining data structures (hash map + doubly-linked list for LRU, stack + min-tracking for MinStack). Space is always at least O(n) to store the data. The challenge is achieving constant-time operations through clever structure composition.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.