Problem link ও উৎস
- **Original source:** Classic hash-map registry / index-accelerator exercise
- **Platform:** LeetCode —
- **Topic:** hash map (bidirectional registry)
- **Difficulty:** Medium
- **Pattern:** hash as index accelerator
- **Basic idea inherited from:** dict as bidirectional registry — একটা ছোট id দিয়ে আসল data খুঁজে আনা, আর data দিয়ে তার id
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা URL-shortener system বানাতে হবে — দুটো method: `encode(longUrl)` যেটা একটা ছোট URL ফেরত দেয়, আর `decode(shortUrl)` যেটা সেই ছোট URL থেকে আবার আসল লম্বা URL ফিরিয়ে আনে। একমাত্র শর্ত: `decode(encode(url))` সবসময় হুবহু আসল `url`। ছোট URL দেখতে কেমন হবে সেটা তোমার ইচ্ছা — শুধু round-trip ঠিক থাকতে হবে।
```text
encode("https://leetcode.com/problems/design-tinyurl") → "http://tinyurl.com/0"
decode("http://tinyurl.com/0") → "https://leetcode.com/problems/design-tinyurl"
```
### Input ও output {#8-example-input-and-output}
```text
url = "https://leetcode.com/problems/design-tinyurl"
encode(url) = "http://tinyurl.com/0" decode("http://tinyurl.com/0") = url
url2 = "https://a.com/x?y=1&z=2"
encode(url2) = "http://tinyurl.com/1" decode("http://tinyurl.com/1") = url2
Edge : একই url আবার encode → আগের ছোট URL-ই ফেরত (idempotent)
Edge : encode("") = "http://tinyurl.com/2" decode(...) = "" (খালি string-ও বৈধ data)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো cloakroom-এ ব্যাগ জমা দিচ্ছ। কর্মী তোমার ব্যাগ একটা তাকে রাখেন আর তোমাকে একটা ছোট টোকেন নম্বর দেন — "৪২"। তুমি ফিরে এসে শুধু "৪২" বললে উনি সঙ্গে সঙ্গে তোমার ব্যাগ বের করে দেন; পুরো cloakroom হাতড়াতে হয় না। ছোট টোকেন (code) আর আসল ব্যাগ (longUrl)-এর মধ্যে registry-টাই hash map, আর টোকেন নম্বর বাড়ে এক এক করে — সেটাই counter।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **dict-কে registry হিসেবে ব্যবহার করার** উপর — hashing-এর সবচেয়ে সরল অথচ শক্তিশালী রূপ। আগের note-গুলোতে dict ছিল "value → count" বা "value → index"; এখানে সেটা "ছোট id → আসল data"। নতুন মোচড়টা হলো একটা ছোট, সহজে-তৈরি key (একটা counter) বানিয়ে সেটাকেই lookup-এর accelerator বানানো। [../patterns.md](../patterns.md)-তে এই de-duplication / registry চিন্তা Pattern 6।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic গণিত নয়, **mapping**: একটা bijection (one-to-one মিল) দরকার আসল URL আর ছোট code-এর মধ্যে, যাতে কোনো তথ্য না হারায়। সবচেয়ে নিরাপদ "hash" হলো একটা strictly increasing counter — `0, 1, 2, ...` — কারণ এটা কখনো collide করে না (প্রতিটা নতুন URL আলাদা সংখ্যা পায়)। আসল hash function (যেমন `hash(url)`)-এও করা যায়, কিন্তু তখন collision সামলাতে হয়; counter সেই ঝামেলাই এড়িয়ে যায়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো **hash map**: একটা `code → longUrl` (decode-এর জন্য আবশ্যক), আর একটা `longUrl → code` (একই URL দুবার এলে যাতে নতুন code না বানিয়ে পুরোনোটাই ফেরত দিই — idempotent থাকে)। সাথে একটা integer `counter` যা পরের ফাঁকা id দেয়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
decode-এ আমাদের code থেকে instant আসল URL চাই — hash map গড়ে **O(1)** lookup দেয়, list হলে প্রতিবার scan করতে হতো O(n)। দ্বিতীয় map (`longUrl → code`) থাকায় ডুপ্লিকেট URL চেনাও O(1), তাই storage অপচয় হয় না। counter হলো id-জেনারেটর — কোনো খোঁজাখুঁজি ছাড়াই পরের unique key দেয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: ছোট URL বানাতে এলোমেলো (random) অক্ষরের একটা code বানাই, আর decode-এ পুরো store-এ খুঁজে দেখি কোন entry-র code এটা।
```text
encode(url):
code = এলোমেলো ৬ অক্ষর
store-এ (code, url) রাখো
return prefix + code
decode(short):
store-এর প্রতিটা entry দেখো যতক্ষণ না code মেলে → তার url ফেরত
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
দুটো সমস্যা। এক, random code **collide** করতে পারে — একই code দুটো আলাদা URL-এ বসে গেলে decode ভুল উত্তর দেয়, তাই প্রতিবার "এই code কি আগে আছে?" check লাগে। দুই, যদি decode-এ map ব্যবহার না করে list scan করি, প্রতিটা decode **O(n)**। আসল অপচয়: lookup-টাকে আমরা search বানিয়ে ফেলছি, যেখানে hash map সেটাকে সরাসরি O(1) করে দিতে পারত।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **decode মানে একটা id থেকে data ফেরত আনা — এটা hash map-এর জন্মগত কাজ।** আর code-টা random হওয়ার দরকার নেই; একটা monotonically বাড়তে থাকা counter ব্যবহার করলে collision একদম শূন্য, আর key তৈরি হয় ধ্রুবক সময়ে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুটো map রাখো। `encode`-এ আগে দেখো URL-টা `url_to_code`-এ আছে কি না — থাকলে পুরোনো code-ই ফেরত দাও (ডুপ্লিকেট এড়াও)। নইলে `counter`-কে code বানাও, দুই map-এ জুড়ি বেঁধে রাখো, counter বাড়াও, prefix জুড়ে ফেরত দাও। `decode`-এ prefix ছেঁটে code বের করো, `code_to_url[code]` ফেরত দাও — পুরোটাই O(1)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** *"ছোট করো"-কে "একটা ছোট id দাও আর registry-তে টুকে রাখো"-তে বদলে ফেলো।* shortening মানে আসলে data সংকোচন নয়, বরং একটা indirection — ছোট key, পেছনে পুরো data। যখনই "id ↔ object", "handle ↔ resource", "token ↔ value" দেখবে, হাত যাবে hash-map registry-র দিকে।
### ছবিতে বোঝা {#7-visual-explanation}
দুটো URL encode করছি; `counter` এক এক করে বাড়ে, দুটো map জুড়ি বেঁধে ভরে:
```text
encode(U1): code="0" counter→1
code_to_url = {"0": U1}
url_to_code = {U1: "0"} → "http://tinyurl.com/0"
encode(U2): code="1" counter→2
code_to_url = {"0": U1, "1": U2}
url_to_code = {U1: "0", U2: "1"} → "http://tinyurl.com/1"
decode("http://tinyurl.com/1"): prefix ছেঁটে code="1" → code_to_url["1"] = U2
encode(U1) আবার: U1 already in url_to_code → পুরোনো "0"-ই ফেরত (নতুন code নয়)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`url = "https://x.com/p"` দিয়ে:
1. শুরু: `counter = 0`, দুই map খালি।
2. `encode(url)`: `url` map-এ নেই → `code = "0"`; `url_to_code = {url: "0"}`, `code_to_url = {"0": url}`; `counter = 1`; ফেরত `"http://tinyurl.com/0"`।
3. `decode("http://tinyurl.com/0")`: prefix ছেঁটে `code = "0"`; `code_to_url["0"] = url` → ফেরত আসল `url`।
4. `encode(url)` আবার: `url` এখন map-এ আছে → পুরোনো `"http://tinyurl.com/0"`-ই ফেরত (counter বাড়ে না)।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class Codec:
def __init__(self):
self.url_to_code = {} # longUrl -> code (ডুপ্লিকেট এড়াতে)
self.code_to_url = {} # code -> longUrl (decode-এর জন্য)
self.counter = 0 # পরের ফাঁকা id
self.prefix = "http://tinyurl.com/"
def encode(self, longUrl):
if longUrl in self.url_to_code: # আগে এসেছে? পুরোনো code-ই দাও
return self.prefix + self.url_to_code[longUrl]
code = str(self.counter) # collision-হীন ছোট key
self.counter += 1
self.url_to_code[longUrl] = code
self.code_to_url[code] = longUrl
return self.prefix + code
def decode(self, shortUrl):
code = shortUrl[len(self.prefix):] # prefix ছেঁটে শুধু code
return self.code_to_url[code]
# ---- tests ----
codec = Codec()
u1 = "https://leetcode.com/problems/design-tinyurl"
s1 = codec.encode(u1)
assert codec.decode(s1) == u1 # round-trip ঠিক
u2 = "https://a.com/x?y=1&z=2"
s2 = codec.encode(u2)
assert codec.decode(s2) == u2
assert s1 != s2 # আলাদা url → আলাদা code
assert codec.encode(u1) == s1 # একই url → একই code (idempotent)
assert codec.decode(codec.encode("")) == "" # খালি string-ও বৈধ
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `url_to_code`, `code_to_url` — দুই দিকের registry; একটা ডুপ্লিকেট ঠেকায়, একটা decode করে।
- `counter` — collision-হীন ছোট id-এর উৎস; প্রতিবার নতুন code-এ এক বাড়ে।
- `if longUrl in self.url_to_code` — একই URL দুবার এলে নতুন entry না বানিয়ে পুরোনো code ফেরত (idempotent)।
- `code = str(self.counter)` — counter-কেই string code বানাই; এটি কখনো আগের কোনো code-এর সমান হয় না।
- `self.url_to_code[...] = code` ও `self.code_to_url[code] = ...` — দুই map জুড়ি বেঁধে আপডেট।
- `code = shortUrl[len(self.prefix):]` — prefix-এর দৈর্ঘ্য ছেঁটে শুধু আসল code পাই, তারপর map থেকে O(1)-এ আসল URL।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম `encode(u1)` দেয় `.../0`, `decode` ঠিক `u1` ফেরায়। `encode(u2)` দেয় `.../1`, তাই `s1 != s2`। `u1` আবার encode করলে map-এ থাকায় আগের `.../0`-ই আসে — তাই `codec.encode(u1) == s1`। খালি string-ও একটা বৈধ code (`.../2`) পায় আর round-trip-এ `""` ফেরে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(1)** প্রতি `encode` ও `decode` — কয়েকটা hash map operation আর string জোড়া, সবই গড়ে ধ্রুবক সময়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — যতগুলো আলাদা URL encode হয়েছে, দুই map-এ তত entry জমে।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- শুধু এক দিকের map রাখা — `code → url` ছাড়া decode অসম্ভব; আবার `url → code` না থাকলে একই URL বারবার নতুন code পায় (storage অপচয়, idempotency নষ্ট)।
- random code নিয়ে collision check ভুলে যাওয়া — দুটো URL একই code পেলে decode চুপচাপ ভুল উত্তর দেয়; counter ব্যবহারে এই ঝুঁকি শূন্য।
- prefix ছাঁটতে ভুল — `decode`-এ prefix-এর দৈর্ঘ্য ঠিকঠাক বাদ না দিলে map-এ key মেলে না; `shortUrl[len(prefix):]` নিরাপদ।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: dict-কে registry/lookup-accelerator হিসেবে দেখা — এই chapter-এর [../concept.md](../concept.md)-র "dict = O(1) lookup" idea-র সরাসরি প্রয়োগ, আর Pattern 6 (state/answer de-duplication)-এর registry রূপ। এই note দেখায় hashing মানে শুধু count/complement নয়, "id ↔ object" mapping-ও। সম্পূর্ণ আলোচনা [../patterns.md](../patterns.md)-র Pattern 6-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- LRU Cache —