Hash Maps for Lookup, Counting, and Grouping
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, recognize repeated lookup, frequency counting, and grouping by a shared signature; reject hashing when ordering or adjacency is the essential requirement.
- Introduce Python dict, set, get, and immutable tuple keys; explain expected constant-time operations and why hashing long keys has a cost.
- Use a short Two Sum example to replace repeated searches with stored information, maintaining the rule that only earlier indices are available.
- Before the worked solution, independently choose a key for Group Anagrams over a fixed lowercase alphabet.
- Develop Group Anagrams from pairwise frequency comparisons to dictionary grouping using frequency-tuple signatures; implement the Python solution.
- Prove that signatures match exactly for anagrams; analyze total character processing, signature creation, group storage, and output references.
- Test empty strings, repeated words, different lengths, and empty input; diagnose mutable keys and unsupported constant-space claims for unrestricted alphabets.
Hash Map چه اطلاعاتی نگه میدارد؟
**کلید ← مقدار**
در Python: `dict`
پیدا کردن، شمردن، گروهبندی؛ با مصرف حافظهٔ بیشتر
**نگهداشتن تعداد با dict**
`counts[ch] = counts.get(ch, 0) + 1`
اولین مشاهدهٔ حرف: \(0 \to 1\)
**فقط دیدهشدن؟ set کافی است**
مقدارهای یکتا؛ افزودن با `add` و بررسی عضویت با `in`
تعداد تکرار حفظ نمیشود.
**کلید باید hashable باشد**
`list`: نامناسب برای کلید
`tuple` شامل عددها: مناسب
اعضای `tuple` هم باید hashable باشند.
**زمان ثابت، اما مورد انتظار**
عملیات معمول `dict` و `set`: \(O(1)\) مورد انتظار، نه تضمین بدترین حالت
برخورد hash و ساختن و hash کردن کلید بلند هزینه دارند.
**شمارش، ترتیب را حفظ نمیکند**
`aba` و `aab`: تعداد حرفهای یکسان
فقط `aba` از دو طرف یکسان خوانده میشود.
اول بپرس: چه اطلاعاتی باید حفظ شود؟
در Two Sum، اول بررسی بعد ثبت
دو عضو متفاوت، حتی با مقدار برابر: \(nums=[3,3],\quad target=6\). اندیسها: \(0,1\).
**Brute Force**
\[ i<j,\qquad nums[i]+nums[j]=target\qquad T(n)=O(n^2),\quad S(n)=O(1) \]
**قانون seen**
\[ seen=\{\}\quad\longrightarrow\quad \forall v\in seen:\;seen[v]<i \]
پیش از بررسی عضو فعلی، فقط اندیسهای قبلی در seen هستند.
**بررسی اندیس اول**
\[ i=0,\quad x=3,\quad need=6-3=3,\quad 3\notin seen \]
هنوز جفتی پیدا نشده است.
**ثبت پس از بررسی**
\[ seen[3]\gets 0\qquad\Rightarrow\qquad seen=\{3:0\} \]
**بررسی اندیس بعدی و پاسخ**
\[ \begin{aligned}i&=1,\quad x=3,\quad need=6-3=3\\3&\in seen,\quad seen[3]=0\[seen[3],i]&=[0,1],\quad 0\ne1\end{aligned} \]
دو عضو متفاوت؛ مقدار برابر اشکالی ندارد.
**پیادهسازی twosum**
\[ \begin{array}{l}\texttt{def twosum(nums, target):}\\\quad\texttt{seen = \{\}}\\\quad\texttt{for i, x in enumerate(nums):}\\\qquad\texttt{need = target - x}\\\qquad\texttt{if need in seen:}\\\qquad\quad\texttt{return [seen[need], i]}\\\qquad\texttt{seen[x] = i}\\\quad\texttt{return None}\end{array} \]
بررسی عضویت کلید، پیش از ثبت مقدار فعلی.
**دو دام مهم**
\[ \begin{aligned}seen[3]=0\;\text{before lookup}&\;\Rightarrow\;[0,0]\quad\times\\0&\text{ is a valid index}\end{aligned} \]
ثبت زودهنگام ممکن است عضو را با خودش جفت کند. بهجای درست یا غلط بودن اندیس، عضویت کلید را بررسی کن.
**هزینه و پرسش بعدی**
\[ T_{\mathrm{expected}}(n)=O(n),\qquad S_{\mathrm{worst}}(n)=O(n) \]
با فرض عددهای با اندازهی معمول؛ \(n\) تعداد اعضای آرایه است.
مکث کن: برای کلمههای با حروف کوچک انگلیسی، چه کلیدی با جابهجایی حروف ثابت میماند، اما با تغییر تعداد یک حرف عوض میشود؟ کلید و دلیلش را بنویس؛ هنوز کد ننویس.
امضای شمارشی برای گروهبندی anagram
```svg
<svg viewBox="0 0 800 550" xmlns="http://www.w3.org/2000/svg"><rect class="tm-soft" x="30" y="15" width="740" height="65" rx="12"/><text class="tm-text" x="400" y="41" text-anchor="middle" font-size="19" direction="rtl">فقط حروف کوچک انگلیسی؛ از a تا z</text><text class="tm-text2" x="400" y="66" text-anchor="middle" font-size="17" direction="rtl">ترتیب گروهها مهم نیست؛ تکرارها حفظ میشوند</text><rect class="tm-surface" x="30" y="95" width="740" height="170" rx="12"/><text class="tm-text" x="90" y="125" font-size="22">ab</text><text class="tm-muted" x="430" y="120" font-size="17" text-anchor="middle">a b c … z</text><text class="tm-text2" x="215" y="151" text-anchor="middle" font-size="16" direction="rtl">شروع</text><text class="tm-text" x="430" y="151" text-anchor="middle" font-size="20">0 0 0 … 0</text><text class="tm-text2" x="215" y="182" text-anchor="middle" font-size="16" direction="rtl">پس از a</text><text class="tm-text" x="430" y="182" text-anchor="middle" font-size="20">1 0 0 … 0</text><rect class="tm-accent" x="310" y="194" width="240" height="35" rx="6"/><text class="tm-text2" x="215" y="218" text-anchor="middle" font-size="16" direction="rtl">پس از b</text><text class="tm-text" x="430" y="218" text-anchor="middle" font-size="20">1 1 0 … 0</text><text class="tm-text-accent" x="400" y="251" text-anchor="middle" font-size="18">signature = tuple: (1, 1, 0, …, 0)</text><rect class="tm-green" x="30" y="280" width="360" height="74" rx="10"/><text class="tm-text" x="210" y="307" text-anchor="middle" font-size="19">ab, ba: (1, 1, 0, …, 0)</text><text class="tm-text" x="210" y="338" text-anchor="middle" font-size="17" direction="rtl">یک گروه؛ امضای یکسان</text><rect class="tm-gold" x="410" y="280" width="360" height="74" rx="10"/><text class="tm-text" x="590" y="307" text-anchor="middle" font-size="19">aa: (2, 0, 0, …, 0)</text><text class="tm-text" x="590" y="338" text-anchor="middle" font-size="17" direction="rtl">همطول؛ اما امضای متفاوت</text><text class="tm-muted" x="400" y="380" text-anchor="middle" font-size="16" direction="rtl">طول کافی نیست؛ set تعداد تکرارها را نگه نمیدارد</text><rect class="tm-soft" x="30" y="397" width="740" height="83" rx="10"/><text class="tm-text" x="170" y="432" text-anchor="middle" font-size="20">anagram</text><text class="tm-text" x="630" y="432" text-anchor="middle" font-size="20" direction="rtl">امضاهای برابر</text><text class="tm-text-accent" x="400" y="427" text-anchor="middle" font-size="24">→</text><text class="tm-text-accent" x="400" y="454" text-anchor="middle" font-size="24">←</text><text class="tm-muted" x="170" y="460" text-anchor="middle" font-size="14" direction="rtl">چیدن دوبارهٔ همان حرفها</text><text class="tm-muted" x="630" y="460" text-anchor="middle" font-size="14" direction="rtl">تعداد یکسان از هر حرف</text><rect class="tm-accent" x="30" y="495" width="740" height="43" rx="10"/><text class="tm-text" x="400" y="522" text-anchor="middle" font-size="17" direction="rtl">کلید: خود tuple، نه فقط hash؛ بررسی برابری کلیدها با dict</text></svg>
```
پیادهسازی کامل Group Anagrams
**از شمارش حروف تا گروهها**
```python
def groupanagrams(words):
groups = {}
for word in words:
counts = [0] * 26
for char in word:
index = ord(char) - ord('a')
counts[index] += 1
signature = tuple(counts)
if signature not in groups:
groups[signature] = []
groups[signature].append(word)
return list(groups.values())
```
**جای دستورها مهم است:** `counts` داخل حلقهی کلمهها از نو ساخته میشود؛ `append` بیرون شرط است؛ `return` بیرون حلقهی کلمههاست.
| کلمه | امضای فراوانی | گروه پس از افزودن کلمه |
| --- | --- | --- |
| `ab` | \((1,1,0,\ldots,0)\) | `['ab']` |
| `ba` | \((1,1,0,\ldots,0)\) | `['ab', 'ba']` |
| `aa` | \((2,0,0,\ldots,0)\) | `['aa']` |
**خروجی:** `[['ab', 'ba'], ['aa']]`
**ناوردای حلقه:** پس از هر دور، هر کلمهی پردازششده دقیقاً یک بار در گروه امضای خودش است.
**کلید:** `tuple(counts)`؛ خودِ `counts` یک `list` است و استفاده از آن بهعنوان کلید، `TypeError` میدهد.
تحلیل هزینه و حالتهای مرزی
\(n\): تعداد کلمهها؛ \(C\): مجموع کاراکترها؛ \(A\): اندازهی الفبا؛ \(g\): تعداد گروهها
**خواندن حرفها**
\[ T_{\mathrm{chars}}=O(C) \]
**هزینهی کلیدها برای همهی کلمهها**
\[ T_{\mathrm{keys}}=n\cdot O(A)=O(nA) \]
ساخت شمارنده، تبدیل به tuple، hash و مقایسهی کلیدهای برابر
**جمع هزینههای زمان**
\[ \mathbb{E}[T]=O(C)+O(nA)=O(C+nA) \]
با فرض رفتار مورد انتظار dict؛ نه تضمین بدترین حالت
**الفبای ثابت**
\[ A=26\quad\Longrightarrow\quad\mathbb{E}[T]=O(C+n) \]
**کران برحسب بیشترین طول کلمه**
\[ C\leq nk\quad\Longrightarrow\quad\mathbb{E}[T]=O(nk+n) \]
\(k\): بیشترین طول کلمه؛ حتی اگر \(C=0\)، پردازش \(n\) کلمه باقی است.
**اجزای حافظه**
\[ \underbrace{gA}_{\mathrm{keys}}+\underbrace{n}_{\mathrm{word\ refs}}+\underbrace{A}_{\mathrm{temporary}}+\underbrace{g}_{\mathrm{group\ refs}} \]
کلیدهای گروهها + ارجاعهای کلمهها + فضای موقت + list نهایی؛ رشتهها کپی نمیشوند.
**حافظه با احتساب خروجی**
\[ S=O(n+gA+A)\quad\xrightarrow{A=26,\;g\leq n}\quad O(n) \]
نسبت به تعداد کلمهها خطی است، نه ثابت.
**تست ورودی و رشتهی خالی**
\[ \begin{aligned} []&\longrightarrow []\\ [\texttt{""},\texttt{""}]&\longrightarrow [[\texttt{""},\texttt{""}]]\end{aligned} \]
ورودی خالی: بدون اجرای حلقه؛ دو رشتهی خالی: یک امضای تمامصفر و یک گروه.
**تکرار کلمه حذف نمیشود**
\[ \begin{aligned}[\texttt{"a"},\texttt{"a"},\texttt{"aa"}]&\longrightarrow [[\texttt{"a"},\texttt{"a"}],[\texttt{"aa"}]]\\ \sum_j f_j(\texttt{"a"})&=1\ne 2=\sum_j f_j(\texttt{"aa"})\end{aligned} \]
طول متفاوت، مجموع شمارندههای متفاوت و در نتیجه امضاهای متفاوت میدهد.
**شرط ثابت بودن حافظهی شمارنده**
\[ S_{\mathrm{counter}}=O(A)\quad\xrightarrow{A=26}\quad O(1) \]
برای الفبای نامحدود، ادعای حافظهی ثابت و همین اندیسگذاری بدون تغییر معتبر نیستند.
Back to course