Python Interview Patterns

1# ============================================================
2# Python Interview Patterns — Common Solutions
3# ============================================================
4from collections import Counter, defaultdict, deque
5from functools import lru_cache
6import bisect
7
8
9# --- Pattern 1: Two Pointers ---
10def two_sum_sorted(nums, target):
11    """Find two numbers in a SORTED array that sum to target. O(n) time."""
12    left, right = 0, len(nums) - 1
13    while left < right:
14        current_sum = nums[left] + nums[right]
15        if current_sum == target:
16            return [left, right]
17        elif current_sum < target:
18            left += 1
19        else:
20            right -= 1
21    return []
22
23
24def is_palindrome(s):
25    """Check if string is a palindrome (ignoring non-alphanumeric). O(n)."""
26    cleaned = [c.lower() for c in s if c.isalnum()]
27    return cleaned == cleaned[::-1]
28
29
30# --- Pattern 2: Sliding Window ---
31def max_sum_subarray(nums, k):
32    """Maximum sum of any contiguous subarray of size k. O(n)."""
33    if len(nums) < k:
34        return 0
35    window_sum = sum(nums[:k])
36    max_sum = window_sum
37    for i in range(k, len(nums)):
38        window_sum += nums[i] - nums[i - k]  # slide the window
39        max_sum = max(max_sum, window_sum)
40    return max_sum
41
42
43def longest_unique_substring(s):
44    """Length of longest substring without repeating chars. O(n)."""
45    char_index = {}
46    max_len = 0
47    start = 0
48    for end, char in enumerate(s):
49        if char in char_index and char_index[char] >= start:
50            start = char_index[char] + 1
51        char_index[char] = end
52        max_len = max(max_len, end - start + 1)
53    return max_len
54
55
56# --- Pattern 3: Hash Map / Counter ---
57def group_anagrams(strs):
58    """Group anagrams together using sorted-key hashing. O(n * k log k)."""
59    groups = defaultdict(list)
60    for word in strs:
61        key = tuple(sorted(word))
62        groups[key].append(word)
63    return list(groups.values())
64
65
66def top_k_frequent(nums, k):
67    """Return k most frequent elements. O(n) with bucket sort."""
68    count = Counter(nums)
69    # Bucket sort: index = frequency, value = list of nums with that freq
70    buckets = [[] for _ in range(len(nums) + 1)]
71    for num, freq in count.items():
72        buckets[freq].append(num)
73    result = []
74    for freq in range(len(buckets) - 1, 0, -1):
75        for num in buckets[freq]:
76            result.append(num)
77            if len(result) == k:
78                return result
79    return result
80
81
82# --- Pattern 4: Stack ---
83def valid_parentheses(s):
84    """Check if parentheses are balanced. O(n) time, O(n) space."""
85    stack = []
86    pairs = {")": "(", "}": "{", "]": "["}
87    for char in s:
88        if char in "({[":
89            stack.append(char)
90        elif char in pairs:
91            if not stack or stack[-1] != pairs[char]:
92                return False
93            stack.pop()
94    return len(stack) == 0
95
96
97# --- Pattern 5: Dynamic Programming with lru_cache ---
98@lru_cache(maxsize=None)
99def climb_stairs(n):
100    """Number of ways to climb n stairs (1 or 2 steps). O(n) with memo."""
101    if n <= 2:
102        return n
103    return climb_stairs(n - 1) + climb_stairs(n - 2)
104
105
106@lru_cache(maxsize=None)
107def longest_common_subsequence(text1, text2, i=0, j=0):
108    """LCS length using top-down DP with memoization."""
109    if i >= len(text1) or j >= len(text2):
110        return 0
111    if text1[i] == text2[j]:
112        return 1 + longest_common_subsequence(text1, text2, i + 1, j + 1)
113    return max(
114        longest_common_subsequence(text1, text2, i + 1, j),
115        longest_common_subsequence(text1, text2, i, j + 1),
116    )
117
118
119# --- Pattern 6: BFS / Graph Traversal ---
120def num_islands(grid):
121    """Count islands in a 2D grid using BFS. O(m*n)."""
122    if not grid:
123        return 0
124    rows, cols = len(grid), len(grid[0])
125    visited = set()
126    islands = 0
127
128    def bfs(r, c):
129        queue = deque([(r, c)])
130        visited.add((r, c))
131        while queue:
132            row, col = queue.popleft()
133            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
134                nr, nc = row + dr, col + dc
135                if (0 <= nr < rows and 0 <= nc < cols
136                        and (nr, nc) not in visited
137                        and grid[nr][nc] == "1"):
138                    visited.add((nr, nc))
139                    queue.append((nr, nc))
140
141    for r in range(rows):
142        for c in range(cols):
143            if grid[r][c] == "1" and (r, c) not in visited:
144                bfs(r, c)
145                islands += 1
146    return islands
147
148
149# --- Pattern 7: Binary Search ---
150def search_insert_position(nums, target):
151    """Find insert position for target in sorted array. O(log n)."""
152    return bisect.bisect_left(nums, target)
153
154
155def find_first_and_last(nums, target):
156    """Find first and last index of target in sorted array. O(log n)."""
157    left = bisect.bisect_left(nums, target)
158    right = bisect.bisect_right(nums, target) - 1
159    if left <= right and left < len(nums) and nums[left] == target:
160        return [left, right]
161    return [-1, -1]
162
163
164# --- Quick demo ---
165if __name__ == "__main__":
166    print(two_sum_sorted([1, 3, 5, 7, 11], 12))  # [1, 4]
167    print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
168    print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))  # [1, 2]
169    print(valid_parentheses("({[]})"))  # True
170    print(climb_stairs(10))  # 89
171    print(longest_unique_substring("abcabcbb"))  # 3