017 — Encode and Decode TinyURL¶

Source¶

Original source: Classic hash-map registry / index-accelerator exercise
Platform: LeetCode — https://leetcode.com/problems/encode-and-decode-tinyurl/
Topic: hash map (bidirectional registry)
Difficulty: Medium
Pattern: hash as index accelerator
Basic idea inherited from: dict as bidirectional registry — একটা ছোট id দিয়ে আসল data খুঁজে আনা, আর data দিয়ে তার id

1. Problem in simple words¶

একটা URL-shortener system বানাতে হবে — দুটো method: encode(longUrl) যেটা একটা ছোট URL ফেরত দেয়, আর decode(shortUrl) যেটা সেই ছোট URL থেকে আবার আসল লম্বা URL ফিরিয়ে আনে। একমাত্র শর্ত: decode(encode(url)) সবসময় হুবহু আসল url। ছোট URL দেখতে কেমন হবে সেটা তোমার ইচ্ছা — শুধু round-trip ঠিক থাকতে হবে।

encode("https://leetcode.com/problems/design-tinyurl")  →  "http://tinyurl.com/0"
decode("http://tinyurl.com/0")                          →  "https://leetcode.com/problems/design-tinyurl"

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-তে এই 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 দেয়।

6. Real-life analogy¶

ভাবো cloakroom-এ ব্যাগ জমা দিচ্ছ। কর্মী তোমার ব্যাগ একটা তাকে রাখেন আর তোমাকে একটা ছোট টোকেন নম্বর দেন — "৪২"। তুমি ফিরে এসে শুধু "৪২" বললে উনি সঙ্গে সঙ্গে তোমার ব্যাগ বের করে দেন; পুরো cloakroom হাতড়াতে হয় না। ছোট টোকেন (code) আর আসল ব্যাগ (longUrl)-এর মধ্যে registry-টাই hash map, আর টোকেন নম্বর বাড়ে এক এক করে — সেটাই counter।

7. Visual explanation¶

দুটো URL encode করছি; counter এক এক করে বাড়ে, দুটো map জুড়ি বেঁধে ভরে:

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 নয়)

8. Example input and output¶

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)

9. Brute force thinking¶

প্রথম সরল চিন্তা: ছোট URL বানাতে এলোমেলো (random) অক্ষরের একটা code বানাই, আর decode-এ পুরো store-এ খুঁজে দেখি কোন entry-র code এটা।

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-র দিকে।

14. Step-by-step dry run¶

url = "https://x.com/p" দিয়ে:

শুরু: counter = 0, দুই map খালি।
encode(url): url map-এ নেই → code = "0"; url_to_code = {url: "0"}, code_to_url = {"0": url}; counter = 1; ফেরত "http://tinyurl.com/0"।
decode("http://tinyurl.com/0"): prefix ছেঁটে code = "0"; code_to_url["0"] = url → ফেরত আসল url।
encode(url) আবার: url এখন map-এ আছে → পুরোনো "http://tinyurl.com/0"-ই ফেরত (counter বাড়ে না)।

15. Python solution¶

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।

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!।

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):] নিরাপদ।

21. Which basic problem this inherits from¶

ভিত্তি: dict-কে registry/lookup-accelerator হিসেবে দেখা — এই chapter-এর ../concept.md-র "dict = O(1) lookup" idea-র সরাসরি প্রয়োগ, আর Pattern 6 (state/answer de-duplication)-এর registry রূপ। এই note দেখায় hashing মানে শুধু count/complement নয়, "id ↔ object" mapping-ও। সম্পূর্ণ আলোচনা ../patterns.md-র Pattern 6-এ।

22. Similar harder problems¶

LRU Cache — https://leetcode.com/problems/lru-cache/ (hash map + ordering; registry-র উপর eviction)
Insert Delete GetRandom O(1) — https://leetcode.com/problems/insert-delete-getrandom-o1/ (dict + list, index accelerator)
Design HashMap — https://leetcode.com/problems/design-hashmap/ (hash map নিজেই গোড়া থেকে বানাও)

23. Pattern learned¶

Hash as index accelerator (bidirectional registry): ছোট id ↔ আসল data-র দুই-দিকের dict রাখো; id বানাতে collision-হীন counter ব্যবহার করো; lookup, insert, ডুপ্লিকেট-check সবই O(1)।

24. Final summary¶

ভবিষ্যতের আমাকে: "design / id দাও / handle ↔ resource / shorten" শুনলেই hash-map registry মনে পড়বে। শর্ট করা মানে data ছোট করা নয় — একটা ছোট key দিয়ে পেছনে পুরো জিনিস টুকে রাখা (indirection)। counter দিয়ে collision-হীন id, দুই map দিয়ে দুই-দিকের O(1) — এই তিনটা মনে থাকলেই হলো।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।