A Time-Bounded Interview Problem-Solving Playbook
آمادگی مصاحبهٔ الگوریتمی با Python
- In 75 minutes, learn a concrete decision workflow for allocating time in a coding interview rather than conducting a separate mock interview or review.
- Allocate minutes 0-5 to contract clarification and examples, 5-12 to a correct baseline and bottleneck, 12-18 to pattern choice and justification, 18-35 to Python implementation, and 35-45 to tests and complexity defense.
- Build a pattern-selection decision record using the input structure, required output, maintained state, safe progress rule, and a reason to reject the closest competing pattern.
- Teach recovery checkpoints: draw a smaller example, solve it manually, expose repeated work, isolate a helper, or preserve a correct baseline when optimization stalls.
- Apply the workflow to finding the longest contiguous substring with at most k distinct characters: independently choose the representation and pattern before the worked brute-force-to-window derivation.
- Explain decisions, assumptions, invariants, and trade-offs concisely while coding; adapt a familiar template to the actual contract instead of narrating every mental step.
- Derive tests from contract boundaries and invariant failure points, manually trace state changes, localize a defect, and verify the repair against a small brute-force oracle.
- Close with an explicit correctness argument, expected time and auxiliary-space bounds, and any remaining limitations; do not claim completion from sample tests alone.
اول قرارداد، بعد هزینهٔ کدنویسی
**دو بودجهٔ متفاوت**
یادگیری با مکث و تمرین: \(75\) دقیقه
حل مسئله در مصاحبه: \(45\) دقیقه
**هر بازه، یک خروجی روشن**
\(0–5\): قرارداد و مثال
\(5–12\): راه درست اولیه و گلوگاه
\(12–18\): انتخاب الگو با دلیل
\(18–35\): پیادهسازی Python
\(35–45\): تست و دفاع از درستی و پیچیدگی
**قبل از حل، سؤال بپرس**
فقط طول یا خود substring؟
رشتهٔ خالی و \(k=0\) مجازند؟
اندازهٔ ورودی و مجموعهٔ کاراکترها چیست؟
**قرارداد ثابت تمرین**
بلندترین substring پیوسته با حداکثر \(k\) کاراکتر متمایز؛ خروجی فقط طول.
رشتهٔ خالی مجاز؛ \(k\geq 0\)؛ بدون محدودیتِ فقط حروف کوچک.
**مرزهای قرارداد**
کاراکتر: هر عضو رشتهٔ Python؛ نه تشخیص شکلهای ترکیبی نوشتاری.
رشتهٔ خالی یا \(k=0\): جواب \(0\).
\(k<0\): خارج از قرارداد.
**مثال: طول، نه خود بخش**
رشته: «الف، ب، الف، ج»؛ \(k=2\)
بخش «الف، ب، الف»: \(2\) نوع کاراکتر، طول \(3\) ✓
کل رشته: \(3\) نوع کاراکتر؛ غیرمجاز.
خروجی: \(3\)؛ انتخاب میان بخشهای همطول لازم نیست.
انتخاب الگو با دلیل
```svg
<svg viewBox="0 0 800 540" xmlns="http://www.w3.org/2000/svg"><text x="400" y="32" text-anchor="middle" class="tm-text" font-size="22" direction="rtl">اسم الگو کافی نیست</text><rect x="60" y="55" width="680" height="66" rx="12" class="tm-soft"/><text x="400" y="83" text-anchor="middle" class="tm-text" font-size="18" direction="rtl">ساختار ورودی ← خروجی ← اطلاعات لازم ← حرکت امن</text><text x="400" y="108" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">یک الگوی رقیب؛ دلیل کنار گذاشتن آن</text><text x="690" y="153" text-anchor="end" class="tm-text-accent" font-size="19" direction="rtl">Brute Force: شروع تازه، set تازه</text><rect x="160" y="173" width="400" height="27" rx="5" class="tm-soft"/><rect x="250" y="173" width="310" height="27" rx="5" class="tm-gold"/><rect x="250" y="216" width="400" height="27" rx="5" class="tm-soft"/><rect x="250" y="216" width="310" height="27" rx="5" class="tm-gold"/><text x="140" y="193" text-anchor="end" class="tm-text2" font-size="15">left</text><text x="230" y="237" text-anchor="end" class="tm-text2" font-size="15">left</text><text x="400" y="270" text-anchor="middle" class="tm-text-gold" font-size="16" direction="rtl">بخش مشترک: جمعآوری دوبارهٔ اطلاعات</text><text x="400" y="296" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">توقف با عبور از حد نوعها؛ بدترین زمان درجهٔ دوم</text><text x="400" y="331" text-anchor="middle" class="tm-text-accent" font-size="19" direction="rtl">sliding window: دو مرز + Hash Map فراوانیها</text><rect x="160" y="350" width="490" height="38" rx="6" class="tm-surface"/><rect x="250" y="350" width="310" height="38" rx="6" class="tm-accent"/><text x="250" y="411" text-anchor="middle" class="tm-text" font-size="16" direction="rtl">left → حذف تا معتبر شدن</text><text x="560" y="411" text-anchor="middle" class="tm-text" font-size="16" direction="rtl">right → افزودن</text><text x="400" y="442" text-anchor="middle" class="tm-text-green" font-size="16" direction="rtl">افزودن، شروع نامعتبر قبلی را نجات نمیدهد</text><rect x="60" y="463" width="680" height="62" rx="10" class="tm-soft"/><text x="400" y="487" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">Binary Search روی طول: ممکن، اما با گذرهای تکراری</text><text x="400" y="512" text-anchor="middle" class="tm-text-green" font-size="17" direction="rtl">انتخاب اینجا: sliding window با یک گذر</text></svg>
```
از invariant تا اجرای درست
| حرکت؛ \(k=2\) | بخش فعلی | counts؛ فقط فراوانی مثبت | \(\mathrm{left}\) | \(\operatorname{len}(\mathrm{counts})\) | \(\mathrm{best}\) |
| --- | --- | --- | --- | --- | --- |
| مقداردهی اولیه | خالی | \(\{\}\) | \(0\) | \(0\) | \(0\) |
| افزودن الف | الف | الف: \(1\) | \(0\) | \(1\) | \(1\) |
| افزودن ب | الف، ب | الف: \(1\)؛ ب: \(1\) | \(0\) | \(2\) | \(2\) |
| افزودن الف دوم | الف، ب، الف | الف: \(2\)؛ ب: \(1\) | \(0\) | \(2\) | \(3\) |
| افزودن ج؛ نامعتبر | الف، ب، الف، ج | الف: \(2\)؛ ب: \(1\)؛ ج: \(1\) | \(0\) | \(3>2\) | \(3\) |
| حذف الف اول؛ هنوز نامعتبر | ب، الف، ج | الف: \(1\)؛ ب: \(1\)؛ ج: \(1\) | \(1\) | \(3>2\) | \(3\) |
| حذف ب و پاککردن کلید؛ معتبر | الف، ج | الف: \(1\)؛ ج: \(1\) | \(2\) | \(2\) | \(\max(3,3-2+1)=3\) |
تست قرارداد، ترمیم invariant و oracle
```svg
<svg viewBox="0 0 800 700" xmlns="http://www.w3.org/2000/svg"><text x="400" y="28" text-anchor="middle" class="tm-muted" font-size="16" direction="rtl">a: الف • b: ب • c: ج</text><rect x="15" y="48" width="240" height="350" rx="12" class="tm-soft"/><text x="135" y="80" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">مرزهای قرارداد</text><text x="35" y="118" class="tm-text" font-size="17" font-family="monospace">s k → best</text><text x="35" y="155" class="tm-text" font-size="17" font-family="monospace">"" 2 → 0</text><text x="35" y="195" class="tm-text" font-size="17" font-family="monospace">"a" 0 → 0</text><text x="35" y="235" class="tm-text" font-size="17" font-family="monospace">"a" 1 → 1</text><text x="35" y="275" class="tm-text" font-size="17" font-family="monospace">"aaaa" 1 → 4</text><text x="35" y="315" class="tm-text" font-size="17" font-family="monospace">"abc" 5 → 3</text><text x="35" y="355" class="tm-text" font-size="17" font-family="monospace">"abac" 2 → 3</text><rect x="270" y="48" width="515" height="220" rx="12" class="tm-surface"/><text x="527" y="80" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">خطای if در ترمیم پنجره</text><text x="290" y="112" class="tm-text" font-size="17" font-family="monospace">s = "aabc", k = 2, best = 3</text><text x="290" y="148" class="tm-text" font-size="17" font-family="monospace">aab → {a:2, b:1}</text><text x="290" y="184" class="tm-text" font-size="17" font-family="monospace">aabc → {a:2, b:1, c:1}</text><text x="290" y="220" class="tm-text-accent" font-size="17" font-family="monospace">if → {a:1, b:1, c:1}</text><text x="527" y="251" text-anchor="middle" class="tm-text-accent" font-size="17" direction="rtl">هنوز سه نوع؛ جواب درست، state نادرست!</text><rect x="270" y="278" width="515" height="120" rx="12" class="tm-green"/><text x="290" y="310" class="tm-text" font-size="17" font-family="monospace">while → {b:1, c:1} → "bc"</text><text x="290" y="344" class="tm-text" font-size="17" font-family="monospace">{a:0, b:1, c:1} ✗</text><text x="527" y="379" text-anchor="middle" class="tm-text" font-size="17" direction="rtl">قرارداد counts: فقط کلیدهای با فراوانی مثبت</text><rect x="15" y="415" width="770" height="270" rx="12" class="tm-soft"/><text x="400" y="445" text-anchor="middle" class="tm-text" font-size="20" direction="rtl">مقایسهٔ اجرایی با oracle روی ورودی کوچک</text><text x="40" y="478" class="tm-text" font-size="16" font-family="monospace" xml:space="preserve"><tspan x="40" dy="0">from itertools import product</tspan><tspan x="40" dy="25">for n in range(6):</tspan><tspan x="40" dy="25"> for chars in product("abc", repeat=n):</tspan><tspan x="40" dy="25"> s = "".join(chars)</tspan><tspan x="40" dy="25"> for k in range(5):</tspan><tspan x="40" dy="25"> assert solve(s, k) == brute(s, k), (s, k)</tspan></text><text x="400" y="662" text-anchor="middle" class="tm-text-accent" font-size="18" direction="rtl">واقعاً اجرا کن؛ عبور از تست محدود، اثبات درستی نیست.</text></svg>
```
دفاع نهایی و مسیر نجات زماندار
**درستی از invariant**
شروع: counts خالی و درست.
حفظ: افزودن راست، کاستن چپ و حذف کلید صفر؛ فراوانیها و تعداد نوعها دقیق میمانند.
توقف while: بخش خالی معتبر است.
**چرا بهترین جواب حذف نمیشود؟**
شروع حذفشده اکنون نامعتبر است؛ افزودن کاراکتر آن را معتبر نمیکند.
پس left کوچکترین شروع معتبرِ باقیمانده است؛ طول فعلی، بلندترین بخش معتبر با همین انتهاست.
best بیشینهٔ طولهاست؛ مقدار \(0\) حالت خالی را پوشش میدهد.
**هزینهٔ کل، نه ظاهر حلقهها**
\(n\): طول رشته؛ پیشروی right برابر \(n\)، پیشروی کل left حداکثر \(n\).
با هزینهٔ مورد انتظار ثابت عملیات dict: زمان مورد انتظار \(O(n)\).
حافظهٔ کمکی: \(O(\min(n,k)+1)\)؛ نوع تازه پیش از ترمیم. برای \(k=0\): خروج زودهنگام و \(O(1)\).
baseline: بدترین حالت \(O(n^2)\)، با فرض هزینهٔ مورد انتظار ثابت عملیات set.
**مسیر نجات؛ بدون قرض از تست**
دقیقهٔ \(12\): گلوگاه مبهم؟ مثال کوچکتر و شناسایی کار تکراری.
دقیقهٔ \(18\): بهینهسازی بیتوجیه؟ baseline درست و بیان محدودیت.
گیر در حذف چپ؟ helper برای کاستن فراوانی و پاک کردن صفر.
**جمعبندی قابل دفاع**
چرا درست است؟ تستها کدام مرزها را پوشش دادند؟ چه محدودیتی مانده؟
واحد شمارش: عضو رشتهٔ Python.
**معیار تمرین مستقل**
یک Medium ندیده، با همان بودجه:
دستکم \(2\) سؤال مرتبط؛ baseline؛ انتخاب مستدل؛ Python اجرایی؛ دستکم \(4\) تست قراردادی؛ دفاع نهایی.
پاس شدن مثالهای صورت مسئله کافی نیست.
Back to course