Interviewer पूछेगा:
Unsorted array में Two Sum O(n) में करके दिखाओ, या HashMap O(1) कैसे है?
Library register से HashMap तक. Let’s make it click.
College library में 50,000 books हैं. Librarian हर shelf नहीं छानता. Register में book code डालता है और shelf मिल जाती है. HashMap का idea भी यही है: key को ऐसी location में बदलो जहाँ से value जल्दी मिले. लेकिन collision, resizing और worst case समझे बिना O(1) बोल देना अधूरा answer है.
01 / Key → hash → bucket → value
Hash Function किसी key को deterministic integer में बदलता है. Same key के लिए same hash जरूरी है. Bucket index सामान्यतः hash(key) % capacity से मिलता है. Collision तब है जब अलग keys same bucket तक पहुँचती हैं. Hash equality का मतलब key equality नहीं — actual keys compare करनी हैं.
Library register analogy में book name key, shelf number bucket, और book details value हैं. Hash function अच्छी तरह फैला हुआ होना चाहिए, वरना पूरा college एक shelf पर पहुँच जाएगा. HashMap में keys stable और equality/hash compatible होने चाहिए. Mutable fields बदलने से inserted key दुबारा न मिल पाने का bug हो सकता है.
02 / Collision: chaining या open addressing
Separate Chaining: हर bucket में entries की list. Collision पर उसी list में key compare करके update / insert करते हैं. Load factor α = entries / buckets; expected lookup O(1 + α), अगर distribution अच्छा हो.
Open Addressing: entries table में ही रहती हैं. Slot occupied हो तो probing — linear, quadratic या double hashing — से अगला slot ढूँढो. Delete पर अक्सर tombstone चाहिए, वरना probe chain टूट जाएगी. Linear probing में clustering आती है; capacity से पहले resize करना जरूरी है.
- Chaining: collisions bucket list में, α 1 से ऊपर भी हो सकता है.
- Open addressing: α < 1; empty slots जरूरी हैं.
- Expected insert / get / delete: O(1), good hashing + bounded α के साथ.
- Worst-case insert / get / delete: O(n), अगर सभी keys collide करें.
- Iteration O(n + capacity), storage O(n + capacity); typical bounded-load setup में O(n).
03 / Load factor 0.75: resize का signal, universal law नहीं
Load factor = size / capacity. इस guide का implementation α >= 0.75 पर capacity double करता है. पहले capacity 8 और 6 entries हुईं, तो नई capacity 16. हर old entry को new_capacity से hash करके दोबारा place करो — buckets को सिर्फ copy करना गलत है.
Resize वाला एक operation O(n) है. मगर geometric growth में sizes 8 + 16 + 32 + … < 2n होते हैं, इसलिए बहुत सारे inserts पर resizing cost amortized O(1) प्रति insert रहती है. 0.75 common policy है, सभी languages या hash table implementations की fixed rule नहीं.
04 / पाँच implementation patterns
नीचे हर pattern Python, Java और C++ में पूरा है: chaining HashMap, custom polynomial hash, rolling string hash, frequency counter और Two Sum. Chaining implementation में update, lookup, delete और dynamic resizing भी हैं.
Polynomial hash में h = (h × 31 + code) mod (10⁹+7). यह educational / algorithmic hash है, cryptographic नहीं. Short examples ASCII / lowercase constraints रखते हैं. Java char, Python code point और C++ byte non-ASCII text पर अलग semantics रखते हैं; production cross-language keys में consistent encoding define करो.
05 / Rolling hash: अगली window को पूरा rehash मत करो
Length m की string window के लिए पहले highest power 31^(m−1) mod M रखो. अगली window: outgoing_char × highest_power घटाओ, result को 31 से multiply करो, incoming char जोड़ो. Negative modulo normalize करना मत भूलना.
Hash match सिर्फ candidate है. नीचे Rabin–Karp implementation substring compare करके collision verify करती है, इसलिए false matches नहीं देती. Hashing pass O(n+m); repeated candidate verification के कारण worst-case O(nm), expected near-linear on typical input. Hash fingerprint alone से guaranteed equality claim मत करना.
06 / Two Sum: check पहले, store बाद में
nums = [3, 2, 4], target = 6. पहले num=3 पर complement=3 खोजो. Map empty है, इसलिए insert seen[3]=0. Next 2 का complement 4 नहीं मिला, insert. Next 4 का complement 2 मिला — answer [1,2].
Insert पहले किया तो first 3 map में खुद को ढूँढ लेगा और [0,0] return करेगा. यही Spoonfeed demo का bug है. Duplicate values valid हो सकती हैं: [3,3] target 6 का सही result [0,1], क्योंकि check earlier indices पर होता है.
07 / Prefix sum + HashMap: negative numbers भी चलेंगे
Current prefix P है. अगर कोई previous prefix P−k है, तो उनके बीच का subarray sum k है. इसलिए count += freq[P−k], फिर freq[P]++. Frequency map को {0:1} से seed करना जरूरी है ताकि index 0 से शुरू होने वाले subarrays count हों.
Frequency चाहिए, सिर्फ set नहीं: एक ही prefix कई बार आ सकता है और हर occurrence अलग starting point है. O(n) expected time, O(n) space. Negative values के साथ भी valid; positive-sum sliding window वाली monotonicity की जरूरत नहीं.
08 / LRU Cache: fast lookup + recency order
Least Recently Used item निकालना है. HashMap key → node देता है, doubly linked list most-recent से least-recent order रखती है. get hit पर node को front पर move करो. put existing key पर update + move. New key capacity से ऊपर जाए तो tail से पिछला node remove और map से delete.
Sentinel head/tail nodes edge cases घटाते हैं. get/put expected O(1), space O(capacity). नीचे तीनों languages में explicit nodes और doubly linked list हैं. Capacity zero भी safely handle है. Java में LinkedHashMap access-order alternative है; Python OrderedDict और C++ list+unordered_map practical choices हैं.
09 / कब HashMap नहीं उठानी
Sorted output या predecessor/successor चाहिए तो balanced tree देखो. 26 lowercase letters का count है तो 26-slot array अक्सर simpler. Worst-case guaranteed latency चाहिए तो plain expected-O(1) hash table का guarantee समझो. Memory budget tight और input sorted है तो two pointers बेहतर हो सकते हैं.
Security-sensitive input में predictable custom hash पर collision attacks possible हैं. Language/runtime का hardened map use करो; password storage या signatures के लिए ये polynomial hashes बिल्कुल नहीं हैं.
Complexity, बिना hand-waving
| Operation | Expected / amortized | Worst case |
|---|---|---|
| Lookup | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Resize / rehash | O(n) for one resize | O(n) |
| Auxiliary storage | O(n + capacity) | O(n + capacity) |
Expected bounds assume good hash distribution and a bounded load factor. The example map doubles its capacity at 0.75.
“Hash table key को hash function से bucket index में map करती है. Good distribution और controlled load factor पर lookup, insert, delete expected O(1) होते हैं; collisions में key equality भी check होती है. Worst case O(n) हो सकता है. Resizing rehashes entries और amortized cost को stable रखती है. Unsorted Two Sum में पहले complement lookup, फिर current element store करूँगा ताकि self-match न हो.”
Read it once. फिर अपने words में बोल के देखो.Pattern पहचानो.
| Problem में ये दिखे | तब ये use करो | यहाँ नहीं |
|---|---|---|
| Pair sum / complement | Map value → earlier index | Sorted input + strict O(1) extra space: pointers |
| Count occurrences / most frequent | Frequency map | Tiny fixed alphabet: plain array may be simpler |
| Group anagrams | Canonical signature → group | Hash only without checking collisions |
| Duplicates / seen before | HashSet | Sorted stream can compare neighbours |
| Subarray sum = K, negative numbers | Prefix sum frequencies; seed {0:1} | Naive sliding window with negatives |
| Distinct / counts in window | Sliding window + frequency map | Need sorted range queries |
| LRU cache | HashMap + doubly linked list | Map alone cannot track recency in O(1) |
| Sorted iteration / predecessor | Balanced tree (O(log n)) | HashMap cannot guarantee sorted key order |
अब code लिखते हैं.
Pattern 1 / HashMap with separate chaining + dynamic resizing
Integer-key educational map. Resize at load factor ≥ 0.75; rehash every entry. Expected O(1) operations, O(n) worst case.
class ChainedMap:
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(max(2, capacity))]
self.size = 0
def _index(self, key):
return hash(key) % len(self.buckets)
def get(self, key, default=None):
for k, value in self.buckets[self._index(key)]:
if k == key:
return value
return default
def put(self, key, value):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
self.size += 1
if self.size / len(self.buckets) >= 0.75:
self._resize()
def remove(self, key):
bucket = self.buckets[self._index(key)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket.pop(i)
self.size -= 1
return True
return False
def _resize(self):
old = self.buckets
self.buckets = [[] for _ in range(2 * len(old))]
self.size = 0
for bucket in old:
for key, value in bucket:
self.put(key, value)
table = ChainedMap()
for i in range(20):
table.put(i, i * 10)
assert table.get(13) == 130
assert table.remove(13) and table.get(13) is NonePattern 2 / Custom polynomial hash
multiplier = 31; mod = 10⁹ + 7. O(m) for m characters. Not a cryptographic hash.
def polynomial_hash(text):
base, mod = 31, 1_000_000_007
value = 0
for char in text:
value = (value * base + ord(char)) % mod
return value
assert polynomial_hash("abc") == 96354Pattern 3 / Rolling hash for strings (Rabin–Karp)
O(1) hash update per shift, with exact match verification. Expected near-linear; worst-case O(nm) including verification. Empty pattern matches at every boundary.
def rolling_find(text, pattern):
base, mod = 31, 1_000_000_007
n, m = len(text), len(pattern)
if m == 0:
return list(range(n + 1))
if m > n:
return []
power = pow(base, m - 1, mod)
target = window = 0
for i in range(m):
target = (target * base + ord(pattern[i])) % mod
window = (window * base + ord(text[i])) % mod
matches = []
for left in range(n - m + 1):
if window == target and text[left:left + m] == pattern:
matches.append(left)
if left + m < n:
window = (window - ord(text[left]) * power) % mod
window = (window * base + ord(text[left + m])) % mod
return matches
assert rolling_find("ababcabc", "abc") == [2, 5]Pattern 4 / Frequency counter
Key = item, value = count. O(n) expected time, O(u) space for u distinct items.
def frequencies(items):
counts = {}
for item in items:
counts[item] = counts.get(item, 0) + 1
return counts
assert frequencies("banana") == {"b": 1, "a": 3, "n": 2}Pattern 5 / Two Sum complement lookup · LC 1
Check before inserting. O(n) expected time, O(n) extra space. Returns zero-based indices.
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]Advanced / Prefix sum frequencies · LC 560
Works with negatives. Seed the empty prefix. O(n) expected time, O(n) space.
def subarray_sum(nums, k):
frequency = {0: 1}
prefix = answer = 0
for value in nums:
prefix += value
answer += frequency.get(prefix - k, 0)
frequency[prefix] = frequency.get(prefix, 0) + 1
return answer
assert subarray_sum([1, -1, 0], 0) == 3Advanced / Full LRU Cache · LC 146
HashMap + explicit doubly linked list. get / put expected O(1), O(capacity) space. Zero capacity is supported; −1 means missing.
class Node:
def __init__(self, key=0, value=0):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = max(0, capacity)
self.nodes = {}
self.head, self.tail = Node(), Node()
self.head.next = self.tail
self.tail.prev = self.head
def _unlink(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _front(self, node):
node.prev, node.next = self.head, self.head.next
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.nodes.get(key)
if node is None:
return -1
self._unlink(node)
self._front(node)
return node.value
def put(self, key, value):
if self.capacity == 0:
return
if key in self.nodes:
node = self.nodes[key]
node.value = value
self._unlink(node)
self._front(node)
return
node = Node(key, value)
self.nodes[key] = node
self._front(node)
if len(self.nodes) > self.capacity:
oldest = self.tail.prev
self._unlink(oldest)
del self.nodes[oldest.key]
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
assert cache.get(1) == 10
cache.put(3, 30)
assert cache.get(2) == -1Practice करो. Confidence आएगा.
Your progress stays on this device. Solve first, tick later. तू खुद से cheat मत करना.
कल interview है? ये साथ ले जाओ.
Day 6 का full guide — concepts, patterns, code और practice, एक PDF में.
अभी भी doubt है?
HashMap सच में O(1) है?+
Expected / average O(1), जब hash distribution अच्छा और load factor bounded हो. Adversarial collisions में worst case O(n) हो सकता है. कुछ implementations extra mitigations करती हैं; universal guaranteed O(1) मत बोलो.
HashSet और HashMap में क्या फर्क?+
Set सिर्फ key membership रखता है. Map key के साथ value भी. Duplicate detection के लिए set; counts, index lookup या grouping के लिए map.
Collision और duplicate key same हैं?+
नहीं. Duplicate key equality से same key है, इसलिए value update होती है. Collision में अलग keys same bucket / hash पर आती हैं; दोनों entries बचनी चाहिए.
0.75 पर ही resize क्यों?+
यह practical time/space trade-off का एक common choice है, universal threshold नहीं. Chaining, open addressing और runtime policies अलग thresholds रख सकती हैं.
Two Sum में [3,3] कैसे handle होगा?+
First 3 check के बाद index 0 पर store होगा. Second 3 का complement 3 मिलेगा, इसलिए [0,1]. Check-before-insert same index दो बार use होने से रोकता है.
Rolling hash match होने पर compare क्यों?+
अलग strings का same hash हो सकता है. Hash को filter की तरह use करो; correctness के लिए exact verification करो. Double hashing collision probability घटाती है, mathematical impossibility नहीं बनाती.
LRU में सिर्फ HashMap क्यों नहीं?+
Lookup fast है, पर least recent key ढूँढने और update करने के लिए recency order चाहिए. Doubly linked list known node को O(1) में unlink / front पर attach करती है.
Built-in map ही use करूँ या custom?+
Production और अधिकांश interviews में built-in map. Custom implementation सीखने से collision, resizing और complexity explain कर पाओगे. Educational polynomial hash passwords या cryptography के लिए नहीं है.
HashMap कोई magic O(1) box नहीं. Distribution, equality और load factor उसका पूरा खेल हैं. अब Two Sum को खुद explain करके solve करो.