آمادگی مصاحبهٔ الگوریتمی با Python
این دوره مسیر حل یک مسئلهٔ الگوریتمی در سطح Medium را تمرین میدهد: از روشنکردن صورت مسئله و ساختن راهحل Brute Force تا انتخاب الگو، پیادهسازی خوانا با Python و بررسی Edge Caseها. تمرکز فقط بر رسیدن به جواب نیست؛ باید بتوانید دلیل انتخاب روش، درستی الگوریتم و هزینهٔ زمانی و حافظهٔ آن را با Big-O توضیح دهید.
مسیر دوره شامل 15 درس کوتاه با پیشنیازهای روشن است. مدرس هوش مصنوعی هر مفهوم را جداگانه آموزش میدهد و با پرسشهای انتخاب الگو، تحلیل پیچیدگی و تشخیص خطا آن را میسنجد. در درسهای الگویی، نشانههای کاربرد و موارد نامناسب استفاده، گذار از راهحل ساده به روش کارآمدتر و خطاهای رایج بررسی میشوند؛ پیش از نمایش پاسخ نیز فرصت تصمیمگیری مستقل دارید.
از Hash Map، Two Pointers و sliding window به جستوجو، پیمایش گراف، Heap و backtracking میرسید. بخش Dynamic Programming به تعریف state، transition و base case در مسائل یکبعدی محدود میماند. درس پایانی یک برنامهٔ اجرایی برای تقسیم زمان مصاحبه ارائه میکند، نه یک آزمون یا مصاحبهٔ آزمایشی جداگانه. دوره برای افراد آشنا با برنامهنویسی پایه طراحی شده و تحقق هدف زمانی به تمرین مستقل نیز نیاز دارد.
زمان تقریبی یادگیری: 10 ساعت
آنچه یاد میگیرید
- مشخص کنید ورودی، خروجی، محدودیت اندازه، رفتار با دادههای تکراری و اجازهٔ تغییر ورودی چه اثری بر راهحل دارند.
- تبدیل کنید یک راهحل Brute Force درست را به راهحلی کارآمدتر و پیچیدگی زمانی و حافظهٔ هر دو را با Big-O تحلیل کنید.
- انتخاب کنید میان Hash Map، Two Pointers، sliding window، Binary Search، Monotonic Stack و Heap و دلیل کاربرد یا رد هر الگو را توضیح دهید.
- پیادهسازی کنید تشخیص نقطهٔ ورود چرخه با Fast/Slow Pointers، مؤلفههای همبند با DFS، کوتاهترین مسیر بدون وزن با BFS و ترتیب وابستگیها با Topological Sort.
- تعریف کنید حالت، انتخابها و شرط توقف در backtracking و رابطهٔ بازگشتی مسئلهٔ بیشینهکردن مجموع عناصر غیرمجاور در Dynamic Programming یکبعدی.
- اجرا کنید برنامهٔ زمانی مصاحبه را از پرسشهای روشنکننده تا کدنویسی Python، تست Edge Caseها و دفاع از درستی راهحل.
سرفصلهای دوره
- معرفی دوره: حل مسئله در مصاحبهٔ فنی
- A 10-15 minute orientation to independently solving a moderately challenging programming problem.
- Why understanding the request, choosing an approach, writing readable Python, and checking the result all matter.
- How recognizing familiar problem shapes helps turn a slow first idea into a faster solution.
- The roadmap: compare solution costs, learn reusable approaches for sequences and connected objects, explore choices and reuse earlier results, then organize the complete interview workflow.
- How lessons provide opportunities to choose an approach independently before a worked explanation.
- Big-O و بهینهسازی راهحل Brute Force
- In 90 minutes, turn an input-output contract into a correct brute-force algorithm, clarifying size limits, duplicates, empty inputs, and permission to modify input.
- Use Python lists, strings, indexing, iteration, and half-open ranges; distinguish contiguous subarrays from subsequences.
- Analyze constant, logarithmic, linear, sorting, quadratic, and exponential growth; distinguish worst-case, expected, and amortized costs.
- Account for Python slicing, list membership, append, pop, sorting, and constant-time len on built-in lists; separate auxiliary space from output space.
- Develop Product of Array Except Self from repeated multiplication to prefix and suffix reuse, first choosing what work can be reused independently and then implementing the linear-time solution.
- Introduce loop invariants through initialization, preservation, and termination; justify the prefix and suffix products and explain why a full output generally requires inspecting every input value.
- Test empty inputs under the agreed contract, single elements, negative values, and zero counts; diagnose hidden copying and unsupported optimality claims.
- Hash Map برای جستوجو، شمارش و گروهبندی
- 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.
- دو اشارهگر و حذف گزینهها
- In 60 minutes, recognize problems where two positions delimit candidates and a comparison safely eliminates some of them.
- Clarify whether order must be preserved and whether sorting is permitted; distinguish moving inward from scanning both positions forward.
- Independently propose which pointer to move for Container With Most Water before seeing the elimination argument.
- Develop the problem from enumerating every pair to an inward two-pointer Python solution.
- Prove that discarding the shorter boundary cannot discard a better pair involving that boundary; explain termination and O(n) time with O(1) auxiliary space.
- Test two elements, equal heights, repeated heights, and zero heights; diagnose moving the taller pointer and confusing the pattern with arbitrary pair search.
- Identify unsuitable uses when no ordering or dominance argument supports discarding candidates.
- پنجرهٔ لغزان و حفظ شرط اعتبار
- In 75 minutes, recognize contiguous-range problems with incrementally maintainable state; contrast fixed-size and variable-size windows.
- Define the window boundaries and validity rule before coding; explain when shrinking can restore validity.
- Independently choose the stored state and shrinking rule for Longest Substring Without Repeating Characters.
- Develop the problem from enumerating substrings and checking uniqueness to a Python sliding-window solution using counts.
- Prove that the maintained window is valid after shrinking and that the best valid length is recorded.
- Count total pointer movements to justify expected O(n) time despite a nested shrinking loop; express space using the number of distinct characters.
- Test empty input, all equal characters, all distinct characters, and repeated characters separated by gaps; reject simple sum-based shrinking rules when negative values invalidate monotonicity.
- جستوجوی دودویی برای پیدا کردن مرز
- In 75 minutes, recognize sorted inputs or a false-then-true predicate; reject binary search when this monotone structure cannot be justified.
- Introduce logarithmic halving and a half-open lower-bound template that never indexes outside the array.
- Independently choose the comparisons needed to locate the first and last occurrence of a target.
- Develop Find First and Last Position of Element in Sorted Array from a linear scan to two Python boundary searches.
- Maintain excluded-region invariants, prove strict interval shrinkage, and explain why the final index is the requested boundary.
- Derive O(log n) time and O(1) auxiliary space without slicing or sorting the input.
- Test empty input, absent targets, duplicate-only arrays, and matches at either boundary; diagnose mixed interval conventions and non-progressing updates.
- پشتهٔ یکنواخت برای عنصر بزرگتر بعدی
- In 60 minutes, introduce last-in-first-out behavior using Python list append and pop, then recognize unresolved next-greater queries.
- Independently decide whether Daily Temperatures needs stored values or indices and whether equality should resolve a query.
- Develop Daily Temperatures from repeated forward scans to a decreasing stack of unresolved indices in Python.
- Prove that a popped index receives its first strictly warmer day and that remaining entries still await an answer.
- Use the push-once, pop-at-most-once argument to derive O(n) time and O(n) auxiliary space.
- Test empty input, increasing and decreasing temperatures, equal temperatures, and unanswered positions.
- Distinguish a monotonic stack from an ordinary stack and reject it for arbitrary range queries without a suitable dominance rule.
- اشارهگر سریع و کند برای پیدا کردن ابتدای چرخه
- In 75 minutes, introduce a singly linked node through val and next references, None termination, and object identity rather than value equality.
- Recognize a single-successor sequence that may revisit an earlier node; reject direct use on general branching graphs.
- Compare repeated rescanning and a visited-node set with a constant-space fast/slow approach for Linked List Cycle II.
- Independently predict a meeting on a small drawn list, then implement safe one-step and two-step movement in Python.
- Explain why relative movement guarantees a meeting inside a cycle; derive the reset-and-walk rule using distances modulo cycle length.
- Implement cycle-entry detection with O(n) time and O(1) auxiliary space without modifying the list.
- Test an empty list, a terminating singleton, a self-loop, entry at the head, and equal values in distinct nodes; diagnose comparing values and dereferencing None.
- جستوجوی عمقی برای مؤلفههای همبند
- In 90 minutes, introduce vertices, edges, paths, cycles, disconnected components, and adjacency lists; model four-neighbor grid cells as a graph.
- Introduce recursive calls through a stopping case, progress to a smaller unexplored region, and call-stack storage; relate recursion to an explicit LIFO stack.
- Recognize reachability and component questions; distinguish them from shortest-path questions.
- For Number of Islands, independently choose discovery marking and component-count updates before the worked Python implementation.
- Replace repeated reachability scans with one traversal per unseen component; implement iterative DFS and trace the corresponding recursive formulation.
- Prove that one traversal discovers exactly one component; derive O(V + E) time and O(V) auxiliary space, or O(rows * columns) for a grid.
- Test empty grids, one row, isolated cells, and a fully connected region; diagnose missing bounds checks, late marking, mutation without permission, and Python recursion-depth limits.
- جستوجوی سطحی برای کوتاهترین مسیر بدون وزن
- In 75 minutes, introduce first-in-first-out processing with collections.deque and constant-time popleft.
- Recognize minimum edge counts and simultaneous spread as BFS signals; explain why unequal edge costs invalidate ordinary BFS shortest-path guarantees.
- Independently select initial queue contents for computing each binary-grid cell's distance to its nearest zero.
- Develop 01 Matrix from separate searches for each cell to a multi-source Python BFS starting from all zero cells.
- Mark cells when enqueued and prove that queue layers assign shortest distances in nondecreasing order.
- Derive O(rows * columns) time and space while distinguishing distance output storage from the queue.
- Test one-cell grids, all-zero grids, one distant zero, and the agreed no-zero contract; diagnose list pop(0), repeated enqueues, and incorrect distance increments.
- مرتبسازی توپولوژیک برای ترتیب وابستگیها
- In 75 minutes, recognize directed prerequisite constraints and distinguish a valid dependency order from numerical sorting or shortest paths.
- Define indegree and the directed acyclic graph requirement; explain that multiple valid orders may exist.
- Independently choose edge direction and initial available tasks for a dependency-ordering problem.
- Develop the solution from testing candidate permutations to repeated full scans, then to a Python queue-based indegree algorithm.
- Prove that every queued vertex has no remaining unmet prerequisite and that processing fewer than all vertices detects a directed cycle.
- Derive O(V + E) time and O(V + E) total auxiliary storage including the adjacency representation.
- Test disconnected tasks, isolated vertices, self-loops, multiple valid orders, and repeated edges; keep adjacency and indegree duplicate handling consistent.
- هیپ برای انتخاب Top-K
- In 75 minutes, recognize repeated access to an extreme value and bounded top-k selection; compare a heap with sorting when complete order is required.
- Introduce the min-heap property and Python heapq operations without teaching heap implementation from scratch.
- Independently choose which candidate must remain at the root when retaining the k closest points to the origin.
- Develop K Closest Points to Origin from repeatedly selecting minima and full sorting to a size-k heap of negated squared distances.
- Use comparable tuple entries and avoid unnecessary square roots; implement the Python solution under an arbitrary-output-order contract.
- Prove that the heap retains the best k candidates seen so far; derive O(n log(k + 1)) time, O(k) auxiliary space, and the O(n) heapify construction bound.
- Test ties, repeated points, k equal to zero or n when permitted, and invalid k under the agreed contract; diagnose reversed priority signs and claims that heap iteration is sorted.
- بکترکینگ با انتخاب، محدودیت و بازگشت
- In 75 minutes, recognize requests to enumerate valid constructions and distinguish path-specific state from globally visited graph vertices.
- Define a recursive state, available choices, stopping condition, and choose-explore-undo sequence.
- Independently identify which partial parenthesis strings can never become valid before seeing a pruning rule.
- Develop Generate Parentheses from generating every length-2n candidate and filtering to a Python backtracking solution that extends only valid prefixes.
- Prove soundness through prefix balance and completeness through considering every legal next choice; explain why pruning cannot remove a valid completion.
- Analyze the search tree, O(n) working depth, and output-sensitive construction cost; distinguish a safe exponential bound from the number of valid outputs.
- Test n equal to zero, one, and two; diagnose mutable-path aliasing, missing undo, and claims that pruning makes all enumeration polynomial.
- Reject enumeration when input size and output requirements call for counting or optimization through reusable subproblems instead.
- برنامهنویسی پویا در یک بعد
- In 90 minutes, recognize repeated subproblems in a choice tree; distinguish saving subproblem answers from enumerating every construction.
- Use the neutral problem of maximizing the sum of non-adjacent nonnegative array values, allowing the empty selection.
- Before the worked solution, independently specify what one indexed state means, its take-or-skip transition, and its base cases.
- Develop exponential recursion into Python memoization, then bottom-up evaluation and two-value rolling storage.
- Prove the transition by partitioning valid selections into taking or skipping the current value; justify evaluation order by induction.
- Count distinct states and work per state to derive O(n) time, O(n) memoized storage including the call stack, and O(1) auxiliary space for rolling evaluation.
- Test empty input, one element, two elements, equal values, and zeros; diagnose wrong base cases, premature overwriting, and caching a state that omits necessary information.
- Limit scope to one-dimensional states; reject this simple state when additional constraints require retaining more information.
- راهنمای حل مسئله در مصاحبه
- 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.
شروع این دوره در تیچمی