# ============================================================ # Python Interview Patterns — Common Solutions # ============================================================ from collections import Counter, defaultdict, deque from functools import lru_cache import bisect # --- Pattern 1: Two Pointers --- def two_sum_sorted(nums, target): """Find two numbers in a SORTED array that sum to target. O(n) time.""" left, right = 0, len(nums) - 1 while left < right: current_sum = nums[left] + nums[right] if current_sum == target: return [left, right] elif current_sum < target: left += 1 else: right -= 1 return [] def is_palindrome(s): """Check if string is a palindrome (ignoring non-alphanumeric). O(n).""" cleaned = [c.lower() for c in s if c.isalnum()] return cleaned == cleaned[::-1] # --- Pattern 2: Sliding Window --- def max_sum_subarray(nums, k): """Maximum sum of any contiguous subarray of size k. O(n).""" if len(nums) < k: return 0 window_sum = sum(nums[:k]) max_sum = window_sum for i in range(k, len(nums)): window_sum += nums[i] - nums[i - k] # slide the window max_sum = max(max_sum, window_sum) return max_sum def longest_unique_substring(s): """Length of longest substring without repeating chars. O(n).""" char_index = {} max_len = 0 start = 0 for end, char in enumerate(s): if char in char_index and char_index[char] >= start: start = char_index[char] + 1 char_index[char] = end max_len = max(max_len, end - start + 1) return max_len # --- Pattern 3: Hash Map / Counter --- def group_anagrams(strs): """Group anagrams together using sorted-key hashing. O(n * k log k).""" groups = defaultdict(list) for word in strs: key = tuple(sorted(word)) groups[key].append(word) return list(groups.values()) def top_k_frequent(nums, k): """Return k most frequent elements. O(n) with bucket sort.""" count = Counter(nums) # Bucket sort: index = frequency, value = list of nums with that freq buckets = [[] for _ in range(len(nums) + 1)] for num, freq in count.items(): buckets[freq].append(num) result = [] for freq in range(len(buckets) - 1, 0, -1): for num in buckets[freq]: result.append(num) if len(result) == k: return result return result # --- Pattern 4: Stack --- def valid_parentheses(s): """Check if parentheses are balanced. O(n) time, O(n) space.""" stack = [] pairs = {")": "(", "}": "{", "]": "["} for char in s: if char in "({[": stack.append(char) elif char in pairs: if not stack or stack[-1] != pairs[char]: return False stack.pop() return len(stack) == 0 # --- Pattern 5: Dynamic Programming with lru_cache --- @lru_cache(maxsize=None) def climb_stairs(n): """Number of ways to climb n stairs (1 or 2 steps). O(n) with memo.""" if n <= 2: return n return climb_stairs(n - 1) + climb_stairs(n - 2) @lru_cache(maxsize=None) def longest_common_subsequence(text1, text2, i=0, j=0): """LCS length using top-down DP with memoization.""" if i >= len(text1) or j >= len(text2): return 0 if text1[i] == text2[j]: return 1 + longest_common_subsequence(text1, text2, i + 1, j + 1) return max( longest_common_subsequence(text1, text2, i + 1, j), longest_common_subsequence(text1, text2, i, j + 1), ) # --- Pattern 6: BFS / Graph Traversal --- def num_islands(grid): """Count islands in a 2D grid using BFS. O(m*n).""" if not grid: return 0 rows, cols = len(grid), len(grid[0]) visited = set() islands = 0 def bfs(r, c): queue = deque([(r, c)]) visited.add((r, c)) while queue: row, col = queue.popleft() for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: nr, nc = row + dr, col + dc if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and grid[nr][nc] == "1"): visited.add((nr, nc)) queue.append((nr, nc)) for r in range(rows): for c in range(cols): if grid[r][c] == "1" and (r, c) not in visited: bfs(r, c) islands += 1 return islands # --- Pattern 7: Binary Search --- def search_insert_position(nums, target): """Find insert position for target in sorted array. O(log n).""" return bisect.bisect_left(nums, target) def find_first_and_last(nums, target): """Find first and last index of target in sorted array. O(log n).""" left = bisect.bisect_left(nums, target) right = bisect.bisect_right(nums, target) - 1 if left <= right and left < len(nums) and nums[left] == target: return [left, right] return [-1, -1] # --- Quick demo --- if __name__ == "__main__": print(two_sum_sorted([1, 3, 5, 7, 11], 12)) # [1, 4] print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])) print(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) # [1, 2] print(valid_parentheses("({[]})")) # True print(climb_stairs(10)) # 89 print(longest_unique_substring("abcabcbb")) # 3

Phase 14: Interview Preparation & Career Growth

0 of 3 topics completed

Python Interview Patterns

System Design with Python

Career Growth & Specializations

🎤 Mock Interview