Comprehensive guide covering While Loops, For Loops, Recursion, Generators, and Data Structures & Algorithms
Table of Contents
Part 1: Foundation
Part 2: Loop Techniques
Part 3: Comparisons
Part 4: Data Structures & Algorithms
Part 5: Advanced Topics
- Common Patterns & Techniques
- Best Practices
- Real-World Examples
- Performance Optimization
- Interview Problem Patterns
Problem Dissection Framework
The 5-Step Problem Analysis Method
Step 1: IDENTIFY – What is the core problem?
"""
Problem: Find all pairs in an array that sum to a target value.
Input: [2, 7, 11, 15], target = 9
Output: [(0, 1)] # indices where arr[0] + arr[1] = 9
"""
# Questions to ask:
# 1. What am I searching for? → Pairs that sum to target
# 2. What's the input type? → List of integers
# 3. What's the output type? → List of tuples (indices)
# 4. Any constraints? → May have duplicates, negatives?
# 5. Edge cases? → Empty array, no pairs, multiple pairsStep 2: CATEGORIZE – What type of problem is this?
Problem Categories:
├── Search/Find
│ ├── Linear Search → while with counter
│ ├── Binary Search → while with two pointers
│ └── Pattern Matching → while with conditions
│
├── Transform/Process
│ ├── Mapping → for loop or map()
│ ├── Filtering → for loop or filter()
│ └── Reduction → for loop or reduce()
│
├── Generate/Create
│ ├── Sequence → for with range() or generator
│ ├── Combinations → itertools.combinations()
│ └── Permutations → itertools.permutations()
│
├── Count/Aggregate
│ ├── Sum/Product → for or built-in sum()
│ ├── Frequency → Counter() or dict
│ └── Statistics → statistics module
│
├── Sort/Order
│ ├── Simple Sort → sorted() or list.sort()
│ ├── Custom Sort → sorted(key=...)
│ └── Partial Sort → heapq.nsmallest()
│
└── Validate/Check
├── Condition Check → all(), any()
├── Type Check → isinstance()
└── Pattern Match → re moduleStep 3: DECOMPOSE – Break down into sub-problems
# Problem: Find longest substring without repeating characters
# Input: "abcabcbb"
# Output: 3 (substring "abc")
# Decomposition:
"""
1. TRACKING: Need to track characters in current window
→ Use: set() or dict for O(1) lookup
2. EXPANSION: Need to grow window when valid
→ Use: while loop with right pointer
3. CONTRACTION: Need to shrink when invalid
→ Use: while loop with left pointer
4. OPTIMIZATION: Need to remember max length
→ Use: max_length variable
5. ITERATION: Need to process each character
→ Use: for loop over string
"""
# Solution Architecture:
def length_of_longest_substring(s):
# 1. Choose data structure (set for tracking)
char_set = set()
# 2. Initialize pointers
left = 0
max_length = 0
# 3. Outer iteration (for loop - known range)
for right in range(len(s)):
# 4. Inner condition (while loop - unknown iterations)
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# 5. Update state
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_lengthStep 4: MATCH – Map to appropriate tools
# Decision Matrix: Problem → Tool Selection
# Example Problem: "Remove duplicates from sorted array in-place"
# Analysis:
"""
1. Data Structure: Array/List → Can use indices
2. Operation: Remove/Modify → In-place modification needed
3. Pattern: Sequential processing → Need index control
4. Constraint: In-place → Can't use set() or new list
Decision Path:
- Can't use: set() → would lose order and create new structure
- Can't use: for loop → can't modify list during iteration safely
- Can't use: list comprehension → creates new list
- ✅ Use: while loop with manual index control
OR: Two pointer technique with for loop
"""
# Solution 1: While loop (when you need complete control)
def remove_duplicates_while(nums):
if not nums:
return 0
i = 0
while i < len(nums) - 1:
if nums[i] == nums[i + 1]:
nums.pop(i + 1) # Modify in-place
else:
i += 1
return len(nums)
# Solution 2: Two pointer with for (more pythonic)
def remove_duplicates_two_pointer(nums):
if not nums:
return 0
write_idx = 1
for read_idx in range(1, len(nums)):
if nums[read_idx] != nums[read_idx - 1]:
nums[write_idx] = nums[read_idx]
write_idx += 1
return write_idxStep 5: OPTIMIZE – Refine with Python tools
# Problem: Count frequency of each character in string
# ❌ Basic Solution (Manual while loop)
def count_chars_basic(s):
freq = {}
i = 0
while i < len(s):
char = s[i]
if char in freq:
freq[char] += 1
else:
freq[char] = 1
i += 1
return freq
# ⚠️ Better (For loop)
def count_chars_better(s):
freq = {}
for char in s:
freq[char] = freq.get(char, 0) + 1
return freq
# ✅ Optimized (Built-in Counter)
from collections import Counter
def count_chars_optimized(s):
return Counter(s)
# 🚀 One-liner
count_chars = lambda s: Counter(s)
# Performance Comparison:
# Basic: ~10.5 μs
# Better: ~8.2 μs (22% faster)
# Optimized: ~3.1 μs (70% faster!)Python Built-in Tools Arsenal
1. Iteration Tools (itertools module)
When to Use Instead of While Loop:
from itertools import *
# 1.1 CYCLE - Infinite repetition
# ❌ While loop approach
def cycle_while(items, n):
result = []
i = 0
while len(result) < n:
result.append(items[i % len(items)])
i += 1
return result
# ✅ itertools approach
def cycle_itertools(items, n):
return list(islice(cycle(items), n))
# Usage: cycle(['A', 'B', 'C'], 7) → ['A', 'B', 'C', 'A', 'B', 'C', 'A']
# 1.2 REPEAT - Repeat single value
# ❌ While loop
def repeat_while(value, times):
result = []
count = 0
while count < times:
result.append(value)
count += 1
return result
# ✅ Built-in
def repeat_builtin(value, times):
return list(repeat(value, times))
# 1.3 ACCUMULATE - Running totals
# ❌ While loop
def running_sum_while(nums):
result = []
total = 0
i = 0
while i < len(nums):
total += nums[i]
result.append(total)
i += 1
return result
# ✅ itertools
from itertools import accumulate
running_sum = lambda nums: list(accumulate(nums))
# [1, 2, 3, 4] → [1, 3, 6, 10]
# 1.4 CHAIN - Flatten iterables
# ❌ While loop
def flatten_while(lists):
result = []
i = 0
while i < len(lists):
j = 0
while j < len(lists[i]):
result.append(lists[i][j])
j += 1
i += 1
return result
# ✅ itertools
from itertools import chain
flatten = lambda lists: list(chain.from_iterable(lists))
# [[1,2], [3,4], [5]] → [1, 2, 3, 4, 5]
# 1.5 COMBINATIONS & PERMUTATIONS
from itertools import combinations, permutations
# All pairs from list
pairs = list(combinations([1, 2, 3, 4], 2))
# [(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)]
# All orderings
perms = list(permutations([1, 2, 3], 2))
# [(1,2), (1,3), (2,1), (2,3), (3,1), (3,2)]
# 1.6 GROUPBY - Group consecutive elements
from itertools import groupby
data = [1, 1, 2, 2, 2, 3, 1, 1]
groups = [(k, len(list(g))) for k, g in groupby(data)]
# [(1, 2), (2, 3), (3, 1), (1, 2)]
# 1.7 TAKEWHILE & DROPWHILE - Conditional iteration
from itertools import takewhile, dropwhile
numbers = [1, 3, 5, 7, 2, 4, 6]
# Take while condition is true
less_than_5 = list(takewhile(lambda x: x < 5, numbers))
# [1, 3] (stops at 5)
# Drop while condition is true
after_5 = list(dropwhile(lambda x: x < 5, numbers))
# [5, 7, 2, 4, 6]2. Collection Tools (collections module)
from collections import *
# 2.1 COUNTER - Frequency counting
# ❌ While loop
def count_frequency_while(items):
freq = {}
i = 0
while i < len(items):
freq[items[i]] = freq.get(items[i], 0) + 1
i += 1
return freq
# ✅ Counter
count_frequency = Counter
# Usage:
c = Counter(['a', 'b', 'c', 'a', 'b', 'a'])
# Counter({'a': 3, 'b': 2, 'c': 1})
c.most_common(2) # [('a', 3), ('b', 2)]
c.elements() # Iterator: 'a', 'a', 'a', 'b', 'b', 'c'
# 2.2 DEFAULTDICT - Auto-initialization
from collections import defaultdict
# ❌ Manual checking
groups = {}
for item in data:
if item.category not in groups:
groups[item.category] = []
groups[item.category].append(item)
# ✅ defaultdict
groups = defaultdict(list)
for item in data:
groups[item.category].append(item)
# 2.3 DEQUE - Efficient queue/stack
from collections import deque
# Better than list for queue operations
queue = deque([1, 2, 3])
queue.append(4) # Add right: O(1)
queue.appendleft(0) # Add left: O(1)
queue.pop() # Remove right: O(1)
queue.popleft() # Remove left: O(1)
# Rotating
queue.rotate(1) # Rotate right
queue.rotate(-1) # Rotate left
# 2.4 NAMEDTUPLE - Readable data structures
from collections import namedtuple
Point = namedtuple('Point', ['x', 'y'])
p = Point(10, 20)
print(p.x, p.y) # More readable than p[0], p[1]
# 2.5 ORDEREDDICT - Maintain insertion order (Python 3.7+ dict does this)
# Useful for: move_to_end(), popitem(last=True/False)
from collections import OrderedDict
cache = OrderedDict()
cache['a'] = 1
cache['b'] = 2
cache.move_to_end('a') # Move to end (LRU cache pattern)3. Functional Tools (Built-ins and functools)
from functools import *
# 3.1 MAP - Transform each element
# ❌ While loop
def square_while(nums):
result = []
i = 0
while i < len(nums):
result.append(nums[i] ** 2)
i += 1
return result
# ✅ Map
square = lambda nums: list(map(lambda x: x ** 2, nums))
# Even better: List comprehension
square_lc = lambda nums: [x ** 2 for x in nums]
# 3.2 FILTER - Select elements by condition
# ❌ While loop
def filter_evens_while(nums):
result = []
i = 0
while i < len(nums):
if nums[i] % 2 == 0:
result.append(nums[i])
i += 1
return result
# ✅ Filter
filter_evens = lambda nums: list(filter(lambda x: x % 2 == 0, nums))
# Better: List comprehension
filter_evens_lc = lambda nums: [x for x in nums if x % 2 == 0]
# 3.3 REDUCE - Accumulate to single value
from functools import reduce
# ❌ While loop
def product_while(nums):
result = 1
i = 0
while i < len(nums):
result *= nums[i]
i += 1
return result
# ✅ Reduce
product = lambda nums: reduce(lambda x, y: x * y, nums, 1)
# Example: reduce(lambda x, y: x + y, [1, 2, 3, 4], 0) → 10
# 3.4 ALL & ANY - Logical checks
numbers = [2, 4, 6, 8]
# ❌ While loop
def all_even_while(nums):
i = 0
while i < len(nums):
if nums[i] % 2 != 0:
return False
i += 1
return True
# ✅ Built-in all()
all_even = lambda nums: all(x % 2 == 0 for x in nums)
# any() - at least one is True
has_even = lambda nums: any(x % 2 == 0 for x in nums)
# 3.5 ZIP - Parallel iteration
# ❌ While loop
def pair_lists_while(list1, list2):
result = []
i = 0
while i < min(len(list1), len(list2)):
result.append((list1[i], list2[i]))
i += 1
return result
# ✅ Zip
pair_lists = lambda l1, l2: list(zip(l1, l2))
# Advanced: zip_longest for different lengths
from itertools import zip_longest
pairs = list(zip_longest([1, 2], ['a', 'b', 'c'], fillvalue=0))
# [(1, 'a'), (2, 'b'), (0, 'c')]
# 3.6 ENUMERATE - Index and value
# ❌ While loop
i = 0
while i < len(items):
print(f"Index {i}: {items[i]}")
i += 1
# ✅ Enumerate
for i, item in enumerate(items):
print(f"Index {i}: {item}")
# Start from different index
for i, item in enumerate(items, start=1):
print(f"Position {i}: {item}")
# 3.7 SORTED with KEY - Custom sorting
data = ['apple', 'pie', 'a', 'cherry']
# Sort by length
sorted(data, key=len) # ['a', 'pie', 'apple', 'cherry']
# Sort by last character
sorted(data, key=lambda x: x[-1])
# Sort with multiple criteria
students = [('Alice', 25), ('Bob', 20), ('Charlie', 25)]
sorted(students, key=lambda x: (x[1], x[0])) # Age, then name
# 3.8 LRU_CACHE - Memoization
from functools import lru_cache
# ❌ Manual caching with while loop
cache = {}
def fibonacci_manual(n):
if n in cache:
return cache[n]
if n <= 1:
return n
result = fibonacci_manual(n-1) + fibonacci_manual(n-2)
cache[n] = result
return result
# ✅ Automatic caching
@lru_cache(maxsize=128)
def fibonacci_cached(n):
if n <= 1:
return n
return fibonacci_cached(n-1) + fibonacci_cached(n-2)
# Performance: fibonacci_cached(100) is instant!4. Search & Sort Tools (bisect and heapq)
import bisect
import heapq
# 4.1 BISECT - Binary search in sorted list
# ❌ While loop binary search
def binary_search_while(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# ✅ Bisect (for insertion point)
sorted_list = [1, 3, 5, 7, 9]
pos = bisect.bisect_left(sorted_list, 6) # 3 (position to insert 6)
pos = bisect.bisect_right(sorted_list, 5) # 3 (after existing 5)
# Insert and maintain sort
bisect.insort(sorted_list, 6) # [1, 3, 5, 6, 7, 9]
# 4.2 HEAPQ - Priority queue / Top K elements
# ❌ Sorting entire list
def top_k_sort(nums, k):
return sorted(nums, reverse=True)[:k] # O(n log n)
# ✅ Heapq (more efficient for small k)
def top_k_heap(nums, k):
return heapq.nlargest(k, nums) # O(n log k)
# Min heap operations
heap = [5, 2, 8, 1, 9]
heapq.heapify(heap) # Convert to min heap in-place
smallest = heapq.heappop(heap) # Remove and return smallest
heapq.heappush(heap, 3) # Add element maintaining heap
# Top K frequent elements
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)5. String & Pattern Tools (re and string)
import re
# 5.1 REGEX - Pattern matching
# ❌ While loop for pattern finding
def find_emails_while(text):
emails = []
i = 0
current = ""
while i < len(text):
# Complex logic to identify email pattern...
i += 1
return emails
# ✅ Regex
def find_emails_regex(text):
pattern = r'\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Z|a-z]{2,}\b'
return re.findall(pattern, text)
# 5.2 STRING methods
text = " Hello World "
text.strip() # Remove whitespace
text.split() # Split by whitespace → ['Hello', 'World']
text.lower() # Lowercase
text.upper() # Uppercase
text.replace('o', '0') # Replace characters
text.startswith('He') # Check prefix
text.endswith('ld') # Check suffix
text.count('o') # Count occurrences
# String formatting
name, age = "Alice", 30
f"{name} is {age} years old" # f-strings (fastest)
"{} is {} years old".format(name, age) # .format()6. Mathematical Tools (math and statistics)
import math
import statistics
# 6.1 MATH module
math.ceil(4.2) # 5 (round up)
math.floor(4.8) # 4 (round down)
math.gcd(48, 18) # 6 (greatest common divisor)
math.factorial(5) # 120
math.sqrt(16) # 4.0
math.pow(2, 10) # 1024.0
math.log(100, 10) # 2.0 (log base 10)
# Constants
math.pi # 3.141592653589793
math.e # 2.718281828459045
math.inf # Infinity
math.nan # Not a Number
# 6.2 STATISTICS module
data = [1, 2, 3, 4, 5, 5, 5, 6, 7, 8]
statistics.mean(data) # 4.6 (average)
statistics.median(data) # 5 (middle value)
statistics.mode(data) # 5 (most common)
statistics.stdev(data) # 2.27 (standard deviation)
statistics.variance(data) # 5.16Tool Selection Decision Tree
Problem Type Analysis:
│
├─ SEARCHING for element(s)?
│ ├─ In sorted data? → bisect module
│ ├─ Pattern in string? → re module
│ ├─ Top K elements? → heapq.nlargest/nsmallest
│ ├─ First/any match? → any() with generator
│ └─ All matches? → list comprehension or filter()
│
├─ TRANSFORMING data?
│ ├─ One-to-one mapping? → map() or list comprehension
│ ├─ Filtering? → filter() or list comprehension
│ ├─ Flattening? → itertools.chain()
│ ├─ Grouping? → itertools.groupby() or defaultdict
│ └─ Accumulating? → reduce() or itertools.accumulate()
│
├─ COUNTING/FREQUENCY?
│ ├─ Element frequency? → Counter
│ ├─ Occurrences? → str.count() or list.count()
│ ├─ Unique elements? → set() or Counter
│ └─ Statistics? → statistics module
│
├─ GENERATING sequences?
│ ├─ Fixed range? → range()
│ ├─ Infinite sequence? → itertools.count/cycle/repeat
│ ├─ Combinations? → itertools.combinations
│ ├─ Permutations? → itertools.permutations
│ └─ Cartesian product? → itertools.product
│
├─ SORTING/ORDERING?
│ ├─ Simple sort? → sorted() or list.sort()
│ ├─ Custom order? → sorted(key=...)
│ ├─ Partial sort? → heapq module
│ └─ Maintain sorted? → bisect.insort()
│
├─ VALIDATION/CHECKING?
│ ├─ All elements? → all()
│ ├─ Any element? → any()
│ ├─ Type checking? → isinstance()
│ ├─ Pattern match? → re.match()
│ └─ Membership? → in operator
│
└─ COMPLEX ITERATION?
├─ Parallel iteration? → zip()
├─ With indices? → enumerate()
├─ Pairwise? → zip(lst, lst[1:])
├─ Window sliding? → Custom while or generator
├─ Unknown iterations? → while loop
└─ State-dependent? → while loop with conditionsFor Loop Mastery
For Loop Fundamentals
Basic Syntax & Variants
# 1. BASIC FOR LOOP - Iterate over sequence
for item in sequence:
process(item)
# 2. RANGE-BASED - Numeric iteration
for i in range(10): # 0 to 9
print(i)
for i in range(5, 10): # 5 to 9
print(i)
for i in range(0, 10, 2): # 0, 2, 4, 6, 8 (step=2)
print(i)
# 3. ENUMERATE - Index + value
for index, value in enumerate(items):
print(f"Index {index}: {value}")
for index, value in enumerate(items, start=1): # Start from 1
print(f"Position {index}: {value}")
# 4. ZIP - Parallel iteration
names = ['Alice', 'Bob', 'Charlie']
ages = [25, 30, 35]
for name, age in zip(names, ages):
print(f"{name} is {age} years old")
# 5. REVERSED - Backward iteration
for item in reversed(items):
print(item)
# 6. SORTED - Iterate in sorted order
for item in sorted(items):
print(item)
# 7. ITEMS/KEYS/VALUES - Dictionary iteration
data = {'a': 1, 'b': 2, 'c': 3}
for key in data: # Iterate keys (default)
print(key)
for key in data.keys(): # Explicit keys
print(key)
for value in data.values(): # Values only
print(value)
for key, value in data.items(): # Key-value pairs
print(f"{key}: {value}")
# 8. UNPACKING - Multiple assignment
pairs = [(1, 2), (3, 4), (5, 6)]
for x, y in pairs:
print(f"x={x}, y={y}")
# 9. NESTED LOOPS
for i in range(3):
for j in range(3):
print(f"({i}, {j})")
# 10. FOR-ELSE - Execute if no break
for item in items:
if condition(item):
break
else:
print("No item matched condition")Advanced For Loop Techniques
1. Multiple Sequences with zip()
# Parallel iteration
names = ['Alice', 'Bob', 'Charlie']
ages = [25, 30, 35]
cities = ['NYC', 'LA', 'Chicago']
for name, age, city in zip(names, ages, cities):
print(f"{name}, {age}, lives in {city}")
# Unequal lengths - stops at shortest
list1 = [1, 2, 3, 4, 5]
list2 = ['a', 'b', 'c']
for num, letter in zip(list1, list2):
print(num, letter) # Only 3 iterations
# zip_longest - continues to longest
from itertools import zip_longest
for num, letter in zip_longest(list1, list2, fillvalue='?'):
print(num, letter) # 5 iterations, fills with '?'2. Enumerate with Custom Start
# Start counting from different number
items = ['apple', 'banana', 'cherry']
for position, item in enumerate(items, start=1):
print(f"#{position}: {item}")
# Output: #1: apple, #2: banana, #3: cherry
# Useful for 1-indexed problems
for i, value in enumerate(array, start=1):
if i == target_position:
return value3. Dictionary Iteration Patterns
data = {'name': 'Alice', 'age': 30, 'city': 'NYC'}
# Pattern 1: Conditional key access
for key in data:
if key.startswith('a'):
print(f"{key}: {data[key]}")
# Pattern 2: Transform keys or values
uppercase_data = {k.upper(): v for k, v in data.items()}
# Pattern 3: Filter items
filtered = {k: v for k, v in data.items() if isinstance(v, int)}
# Pattern 4: Swap keys and values
swapped = {v: k for k, v in data.items()}
# Pattern 5: Merge dictionaries
dict1 = {'a': 1, 'b': 2}
dict2 = {'c': 3, 'd': 4}
merged = {k: v for d in [dict1, dict2] for k, v in d.items()}4. Nested Iteration Patterns
# Pattern 1: Matrix traversal
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
for row in matrix:
for element in row:
print(element, end=' ')
print()
# Pattern 2: With indices
for i in range(len(matrix)):
for j in range(len(matrix[i])):
print(f"matrix[{i}][{j}] = {matrix[i][j]}")
# Pattern 3: Enumerate both dimensions
for i, row in enumerate(matrix):
for j, element in enumerate(row):
print(f"[{i}][{j}] = {element}")
# Pattern 4: Flatten nested structure
flattened = [element for row in matrix for element in row]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Pattern 5: Conditional nested iteration
result = [
element
for row in matrix
for element in row
if element % 2 == 0
]
# [2, 4, 6, 8]5. Break and Continue
# BREAK - Exit loop early
for num in range(100):
if num > 10:
break # Stop at 11
print(num)
# CONTINUE - Skip current iteration
for num in range(10):
if num % 2 == 0:
continue # Skip even numbers
print(num) # Only prints odd numbers
# Combined usage
for i in range(10):
if i == 3:
continue # Skip 3
if i == 7:
break # Stop at 7
print(i) # Prints: 0, 1, 2, 4, 5, 66. For-Else Pattern
# Execute else block if loop completes without break
# Example 1: Search
def find_value(items, target):
for item in items:
if item == target:
print(f"Found {target}")
break
else:
print(f"{target} not found")
# Example 2: Prime number check
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
else:
return True # No divisor found
# Example 3: Validation
def validate_all(items):
for item in items:
if not is_valid(item):
print(f"Invalid item: {item}")
break
else:
print("All items valid")List Comprehensions & Generator Expressions
List Comprehension Syntax
# BASIC: [expression for item in iterable]
squares = [x**2 for x in range(10)]
# [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# WITH CONDITION: [expression for item in iterable if condition]
even_squares = [x**2 for x in range(10) if x % 2 == 0]
# [0, 4, 16, 36, 64]
# WITH IF-ELSE: [expr1 if condition else expr2 for item in iterable]
labels = ['even' if x % 2 == 0 else 'odd' for x in range(10)]
# NESTED: [expression for item1 in iter1 for item2 in iter2]
pairs = [(x, y) for x in range(3) for y in range(3)]
# [(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)]
# NESTED WITH CONDITION
pairs = [(x, y) for x in range(5) for y in range(5) if x < y]
# All pairs where x < yAdvanced List Comprehensions
# 1. FLATTEN nested lists
nested = [[1, 2, 3], [4, 5], [6, 7, 8, 9]]
flat = [item for sublist in nested for item in sublist]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 2. MATRIX operations
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
# Transpose
transpose = [[row[i] for row in matrix] for i in range(len(matrix[0]))]
# [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
# Diagonal
diagonal = [matrix[i][i] for i in range(len(matrix))]
# [1, 5, 9]
# 3. STRING manipulation
text = "Hello World"
vowels = [char for char in text if char.lower() in 'aeiou']
# ['e', 'o', 'o']
uppercase = [char.upper() for char in text]
# 4. DICTIONARY to list
data = {'a': 1, 'b': 2, 'c': 3}
pairs = [(k, v) for k, v in data.items()]
# [('a', 1), ('b', 2), ('c', 3)]
# 5. FUNCTION application
def square(x):
return x ** 2
numbers = [1, 2, 3, 4, 5]
squared = [square(x) for x in numbers]
# 6. MULTIPLE conditions
result = [
x
for x in range(100)
if x % 2 == 0
if x % 3 == 0
if x % 5 == 0
]
# Divisible by 2, 3, AND 5Dictionary & Set Comprehensions
# DICTIONARY COMPREHENSION
# Syntax: {key_expr: value_expr for item in iterable}
# Example 1: Square mapping
squares = {x: x**2 for x in range(6)}
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
# Example 2: Invert dictionary
original = {'a': 1, 'b': 2, 'c': 3}
inverted = {v: k for k, v in original.items()}
# {1: 'a', 2: 'b', 3: 'c'}
# Example 3: Filter dictionary
data = {'apple': 5, 'banana': 2, 'cherry': 8, 'date': 3}
filtered = {k: v for k, v in data.items() if v > 3}
# {'apple': 5, 'cherry': 8}
# Example 4: From two lists
keys = ['name', 'age', 'city']
values = ['Alice', 30, 'NYC']
person = {k: v for k, v in zip(keys, values)}
# SET COMPREHENSION
# Syntax: {expression for item in iterable}
# Example 1: Unique squares
squares = {x**2 for x in range(-5, 6)}
# {0, 1, 4, 9, 16, 25} - duplicates removed
# Example 2: Character set
text = "hello world"
unique_chars = {char for char in text if char.isalpha()}
# {'h', 'e', 'l', 'o', 'w', 'r', 'd'}
# Example 3: Filtered set
numbers = [1, 2, 2, 3, 3, 3, 4, 4, 5]
evens = {x for x in numbers if x % 2 == 0}
# {2, 4}Generator Expressions vs List Comprehensions
# LIST COMPREHENSION - Creates list immediately
list_comp = [x**2 for x in range(1000000)] # ~8 MB memory
print(type(list_comp)) # <class 'list'>
# GENERATOR EXPRESSION - Lazy evaluation
gen_expr = (x**2 for x in range(1000000)) # ~200 bytes
print(type(gen_expr)) # <class 'generator'>
# Usage differences:
# List: Can iterate multiple times
for num in list_comp:
print(num)
for num in list_comp: # Can iterate again
print(num)
# Generator: One-time use
for num in gen_expr:
print(num)
for num in gen_expr: # Empty! Already exhausted
print(num)
# When to use generators:
# 1. Large datasets
# 2. One-time iteration
# 3. Pipeline processing
# 4. Memory constraints
# Examples:
# ✅ GOOD: Generator for large file
lines = (line.strip() for line in open('huge_file.txt'))
long_lines = (line for line in lines if len(line) > 80)
for line in long_lines:
process(line)
# ❌ BAD: List comprehension for large file
lines = [line.strip() for line in open('huge_file.txt')] # Loads all!When to Use For Loops
✅ Perfect Use Cases
# 1. KNOWN ITERATION COUNT
for i in range(10):
print(i)
# 2. ITERATING COLLECTIONS
items = [1, 2, 3, 4, 5]
for item in items:
process(item)
# 3. DICTIONARY ITERATION
data = {'a': 1, 'b': 2}
for key, value in data.items():
print(f"{key}: {value}")
# 4. PARALLEL ITERATION
for name, age in zip(names, ages):
print(f"{name} is {age}")
# 5. ENUMERATE - Need index and value
for i, item in enumerate(items):
print(f"Index {i}: {item}")
# 6. FILE PROCESSING
with open('file.txt') as f:
for line in f: # Memory efficient!
process(line)
# 7. RANGE-BASED OPERATIONS
for i in range(len(array)):
array[i] *= 2 # Modify in place
# 8. MATRIX/2D ARRAY
for row in matrix:
for element in row:
process(element)When NOT to Use For Loops
# ❌ 1. CONDITION-BASED TERMINATION (use while)
# Bad: for with break
for i in range(999999):
if condition_met():
break
process()
# Good: while
while not condition_met():
process()
# ❌ 2. SIMPLE TRANSFORMATIONS (use comprehension)
# Bad: for loop building list
result = []
for x in numbers:
result.append(x * 2)
# Good: list comprehension
result = [x * 2 for x in numbers]
# ❌ 3. INFINITE LOOPS (use while True)
# Bad: Hacky infinite for
for _ in iter(int, 1): # Obscure
process()
# Good: Clear while
while True:
if should_stop():
break
process()
# ❌ 4. COMPLEX POINTER LOGIC (use while)
# Bad: for with complex index manipulation
for i in range(len(arr)):
# Complex pointer movements
# Hard to track
# Good: while with manual control
left, right = 0, len(arr) - 1
while left < right:
# Clear pointer controlRecursion Mastery
Recursion Fundamentals
Basic Structure
def recursive_function(parameter):
# 1. BASE CASE - Stop condition
if base_condition:
return base_value
# 2. RECURSIVE CASE - Break down problem
# Modify parameter to approach base case
return recursive_function(modified_parameter)Essential Components
# 1. BASE CASE - Prevents infinite recursion
def factorial(n):
if n <= 1: # BASE CASE
return 1
return n * factorial(n - 1)
# 2. PROGRESS TOWARD BASE - Must get closer each call
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1) # Getting closer to 0
# 3. RECURSIVE CALL - Function calls itself
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2) # Two recursive calls
# 4. RETURN VALUE - Combine results
def sum_list(lst):
if not lst:
return 0
return lst[0] + sum_list(lst[1:]) # Combine head + restTypes of Recursion
1. Linear Recursion – Single recursive call
# Example: Sum of numbers 1 to n
def sum_n(n):
if n == 0:
return 0
return n + sum_n(n - 1)
# Call stack for sum_n(5):
# sum_n(5) = 5 + sum_n(4)
# sum_n(4) = 4 + sum_n(3)
# sum_n(3) = 3 + sum_n(2)
# sum_n(2) = 2 + sum_n(1)
# sum_n(1) = 1 + sum_n(0)
# sum_n(0) = 0
# Result: 0 + 1 + 2 + 3 + 4 + 5 = 152. Binary Recursion – Two recursive calls
# Example: Fibonacci
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# Call tree for fibonacci(5):
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# / \ / \ / \
# fib(2) fib(1) ...
# Many duplicate calculations!3. Tail Recursion – Recursive call is last operation
# Non-tail recursive
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1) # Multiplication after recursive call
# Tail recursive version
def factorial_tail(n, accumulator=1):
if n <= 1:
return accumulator
return factorial_tail(n - 1, n * accumulator) # Last operation
# Tail recursion can be optimized by compiler (not Python though)4. Multiple Recursion – More than two recursive calls
# Example: Tower of Hanoi
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
# Three recursive calls for complex problems5. Indirect Recursion – Mutual recursion
# Functions call each other
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
# is_even(4) -> is_odd(3) -> is_even(2) -> is_odd(1) -> is_even(0) -> TrueRecursion vs Iteration
Comparison Table
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often clearer for tree/recursive problems | Better for sequential processing |
| Memory | Uses call stack (O(depth)) | O(1) typically |
| Performance | Slower (function call overhead) | Faster |
| Code Size | Usually shorter | Often longer |
| Use Case | Trees, graphs, divide & conquer | Simple loops, known iterations |
| Risk | Stack overflow | Infinite loop |
Side-by-Side Examples
# EXAMPLE 1: Factorial
# Recursive
def factorial_rec(n):
if n <= 1:
return 1
return n * factorial_rec(n - 1)
# Time: O(n), Space: O(n) - call stack
# Iterative
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
# Time: O(n), Space: O(1)
# EXAMPLE 2: Fibonacci
# Recursive (inefficient)
def fib_rec(n):
if n <= 1:
return n
return fib_rec(n - 1) + fib_rec(n - 2)
# Time: O(2^n), Space: O(n)
# Iterative (efficient)
def fib_iter(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Time: O(n), Space: O(1)
# EXAMPLE 3: Binary Search
# Recursive
def binary_search_rec(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_rec(arr, target, mid + 1, right)
else:
return binary_search_rec(arr, target, left, mid - 1)
# Iterative
def binary_search_iter(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# EXAMPLE 4: Tree Traversal
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Recursive (natural and clean)
def inorder_rec(root):
if not root:
return []
return (inorder_rec(root.left) +
[root.val] +
inorder_rec(root.right))
# Iterative (more complex)
def inorder_iter(root):
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return resultWhen to Use Recursion
✅ Perfect Use Cases
# 1. TREE STRUCTURES
def tree_height(root):
if not root:
return 0
return 1 + max(tree_height(root.left), tree_height(root.right))
# 2. GRAPH TRAVERSAL (DFS)
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
if node in visited:
return
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# 3. DIVIDE AND CONQUER
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
# 4. BACKTRACKING
def permutations(nums):
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:])
return
for i in range(len(remaining)):
path.append(remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop()
backtrack([], nums)
return result
# 5. MATHEMATICAL SEQUENCES
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# 6. NESTED DATA STRUCTURES
def flatten(nested_list):
result = []
for item in nested_list:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return resultMemoization & Dynamic Programming
Memoization with Manual Cache
# Without memoization - O(2^n)
def fib_slow(n):
if n <= 1:
return n
return fib_slow(n - 1) + fib_slow(n - 2)
# With manual memoization - O(n)
def fib_memo(n, cache={}):
if n in cache:
return cache[n]
if n <= 1:
return n
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
# Performance comparison:
# fib_slow(35) = ~5 seconds
# fib_memo(35) = ~0.0001 secondsMemoization with @lru_cache
from functools import lru_cache
# Automatic memoization
@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n - 1) + fib_cached(n - 2)
# Works with any recursive function
@lru_cache(maxsize=128)
def expensive_recursive_function(n, m):
# Complex recursive logic
pass
# View cache stats
print(fib_cached.cache_info())
# CacheInfo(hits=33, misses=35, maxsize=None, currsize=35)
# Clear cache if needed
fib_cached.cache_clear()Dynamic Programming Patterns
# PATTERN 1: Top-Down (Memoization)
def climb_stairs_topdown(n, memo={}):
"""How many ways to climb n stairs (1 or 2 steps at a time)"""
if n in memo:
return memo[n]
if n <= 2:
return n
memo[n] = climb_stairs_topdown(n-1, memo) + climb_stairs_topdown(n-2, memo)
return memo[n]
# PATTERN 2: Bottom-Up (Tabulation)
def climb_stairs_bottomup(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# PATTERN 3: Space Optimized
def climb_stairs_optimized(n):
if n <= 2:
return n
prev, curr = 1, 2
for i in range(3, n + 1):
prev, curr = curr, prev + curr
return currGenerator Techniques
Generator Basics
What is a Generator?
# REGULAR FUNCTION - Returns all values at once
def get_squares_list(n):
result = []
for i in range(n):
result.append(i ** 2)
return result # Returns complete list
squares = get_squares_list(1000000) # ~8 MB memory
print(type(squares)) # <class 'list'>
# GENERATOR FUNCTION - Yields values one at a time
def get_squares_gen(n):
for i in range(n):
yield i ** 2 # Yield instead of return
squares = get_squares_gen(1000000) # ~200 bytes
print(type(squares)) # <class 'generator'>
# Generator doesn't execute until iterated
for square in squares:
print(square) # Values generated on demandYield Keyword
def simple_generator():
print("First")
yield 1
print("Second")
yield 2
print("Third")
yield 3
gen = simple_generator() # No output yet
print(next(gen)) # Prints "First", returns 1
print(next(gen)) # Prints "Second", returns 2
print(next(gen)) # Prints "Third", returns 3
print(next(gen)) # Raises StopIteration
# Or use in for loop
for value in simple_generator():
print(value)
# Automatically handles StopIterationGenerator Expressions vs List Comprehensions
# LIST COMPREHENSION - Eager evaluation
list_comp = [x**2 for x in range(10)]
print(list_comp) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
print(type(list_comp)) # <class 'list'>
# GENERATOR EXPRESSION - Lazy evaluation
gen_expr = (x**2 for x in range(10)) # Note: parentheses, not brackets
print(gen_expr) # <generator object>
print(type(gen_expr)) # <class 'generator'>
# Convert to list to see values
print(list(gen_expr)) # [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
# Memory comparison
import sys
big_list = [x for x in range(1000000)]
big_gen = (x for x in range(1000000))
print(sys.getsizeof(big_list)) # ~8000000 bytes
print(sys.getsizeof(big_gen)) # ~200 bytesAdvanced Generator Patterns
1. Infinite Generators
# Infinite sequence
def infinite_sequence():
num = 0
while True:
yield num
num += 1
gen = infinite_sequence()
print(next(gen)) # 0
print(next(gen)) # 1
print(next(gen)) # 2
# Can continue forever
# Fibonacci generator
def fibonacci():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
# Use with islice to limit
from itertools import islice
fib_gen = fibonacci()
first_10 = list(islice(fib_gen, 10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]2. Generator Pipelines
# Process data in stages without loading all into memory
def read_large_file(filename):
"""Stage 1: Read file line by line"""
with open(filename) as f:
for line in f:
yield line.strip()
def filter_comments(lines):
"""Stage 2: Remove comments"""
for line in lines:
if not line.startswith('#'):
yield line
def to_uppercase(lines):
"""Stage 3: Convert to uppercase"""
for line in lines:
yield line.upper()
# Chain generators together
lines = read_large_file('data.txt')
no_comments = filter_comments(lines)
uppercase = to_uppercase(no_comments)
for line in uppercase:
process(line) # Only one line in memory at a time
# Or as one-liner
pipeline = to_uppercase(filter_comments(read_large_file('data.txt')))3. Generator with Send
def accumulator():
total = 0
while True:
value = yield total # Yield current total, receive new value
if value is not None:
total += value
acc = accumulator()
next(acc) # Prime the generator (start it)
print(acc.send(5)) # 5
print(acc.send(10)) # 15
print(acc.send(3)) # 184. Generator Delegation (yield from)
# Delegate to another generator
def generator1():
yield 1
yield 2
def generator2():
yield 3
yield 4
def combined():
yield from generator1() # Delegate to generator1
yield from generator2() # Delegate to generator2
for value in combined():
print(value) # 1, 2, 3, 4
# Flatten nested structures
def flatten(nested):
for item in nested:
if isinstance(item, list):
yield from flatten(item) # Recursive flattening
else:
yield item
nested_list = [1, [2, 3, [4, 5]], 6, [7, [8, 9]]]
print(list(flatten(nested_list)))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]5. Stateful Generators
def moving_average(window_size):
"""Calculate moving average with given window"""
window = []
while True:
value = yield (sum(window) / len(window) if window else 0)
window.append(value)
if len(window) > window_size:
window.pop(0)
ma = moving_average(3)
next(ma) # Prime
print(ma.send(10)) # 10.0
print(ma.send(20)) # 15.0
print(ma.send(30)) # 20.0
print(ma.send(40)) # 30.0 (average of 20, 30, 40)When to Use Generators
✅ Perfect Use Cases
# 1. LARGE FILES
def read_large_file(filename):
with open(filename) as f:
for line in f:
yield line.strip()
# 2. INFINITE SEQUENCES
def primes():
"""Generate prime numbers infinitely"""
yield 2
primes_list = [2]
candidate = 3
while True:
is_prime = all(candidate % p != 0 for p in primes_list)
if is_prime:
yield candidate
primes_list.append(candidate)
candidate += 2
# 3. PIPELINE PROCESSING
def process_logs(filename):
lines = read_file(filename)
parsed = (parse_line(line) for line in lines)
filtered = (item for item in parsed if item.level == 'ERROR')
return filtered
# 4. MEMORY-CONSTRAINED OPERATIONS
def batch_processor(items, batch_size):
"""Process items in batches"""
for i in range(0, len(items), batch_size):
yield items[i:i + batch_size]
# 5. ON-DEMAND COMPUTATION
def lazy_range(start, stop, step=1):
"""Like range() but truly lazy"""
current = start
while current < stop:
yield current
current += stepLoop Comparison Matrix
Complete Comparison Table
| Feature | While Loop | For Loop | Recursion | Generator |
|---|---|---|---|---|
| Syntax | while condition: | for item in seq: | Function calls itself | yield keyword |
| Use Case | Unknown iterations | Known iterations | Tree/recursive problems | Lazy evaluation |
| Memory | O(1) typically | O(1) typically | O(depth) stack | O(1) per item |
| Speed | Fast | Fastest | Slower (overhead) | Fast (lazy) |
| Readability | Good for conditions | Best for collections | Natural for trees | Good for pipelines |
| Termination | Manual control | Automatic | Base case | Yield exhaustion |
| Infinite Loop Risk | High | Low | Medium (stack overflow) | Controlled |
| Index Access | Manual | With enumerate() | Via parameters | Not typical |
| Early Exit | break | break | return | StopIteration |
| Best For | Condition loops | Collection iteration | Divide & conquer | Large data streams |
Performance Benchmarks
import time
# Test data
data = list(range(100000))
# 1. WHILE LOOP
start = time.perf_counter()
i = 0
total = 0
while i < len(data):
total += data[i]
i += 1
while_time = time.perf_counter() - start
print(f"While loop: {while_time:.6f}s")
# 2. FOR LOOP
start = time.perf_counter()
total = 0
for num in data:
total += num
for_time = time.perf_counter() - start
print(f"For loop: {for_time:.6f}s")
# 3. BUILT-IN SUM
start = time.perf_counter()
total = sum(data)
builtin_time = time.perf_counter() - start
print(f"Built-in sum: {builtin_time:.6f}s")
# 4. COMPREHENSION
start = time.perf_counter()
total = sum([num for num in data])
comp_time = time.perf_counter() - start
print(f"Comprehension: {comp_time:.6f}s")
# 5. GENERATOR
start = time.perf_counter()
total = sum((num for num in data))
gen_time = time.perf_counter() - start
print(f"Generator: {gen_time:.6f}s")
"""
Typical Results:
While loop: 0.005234s (baseline)
For loop: 0.003891s (25% faster)
Built-in sum: 0.001456s (72% faster)
Comprehension: 0.004123s (21% faster)
Generator: 0.003967s (24% faster)
Conclusion: Use built-ins when available!
"""Decision Matrix by Problem Type
"""
PROBLEM TYPE → BEST TOOL
1. SEARCH/FIND
- Linear search → for with break
- Binary search → while with pointers
- Find all matches → list comprehension
- Find first match → next(gen, default)
2. TRANSFORM
- One-to-one → list comprehension
- Complex transform → for loop
- Pipeline → generator chain
- In-place modify → while with index
3. AGGREGATE/REDUCE
- Sum/product → built-in sum()/math.prod()
- Custom reduction → reduce() or for loop
- Running total → itertools.accumulate()
- Frequency count → Counter()
4. FILTER
- Simple condition → list comp with if
- Complex condition → filter() or for loop
- Multiple criteria → for loop with if-elif
- Lazy filtering → generator expression
5. GENERATE
- Fixed range → range()
- Infinite sequence → generator with while True
- Combinations → itertools.combinations()
- Recursive generation → recursion
6. TREE/GRAPH
- DFS → recursion or stack with while
- BFS → queue with while
- Tree traversal → recursion (natural)
- Path finding → recursion with backtracking
7. SORTING/ORDERING
- Simple sort → sorted()
- Custom comparator → sorted(key=...)
- Partial sort (top K) → heapq
- Maintain sorted → bisect.insort()
8. ITERATION PATTERNS
- Two pointers → while
- Sliding window → for with queue/deque
- Fast & slow pointers → while
- Parallel iteration → zip() with for
"""Core Data Structures
Arrays & Lists
Core Operations & Complexity
# LIST OPERATIONS
arr = [1, 2, 3, 4, 5]
# Access
arr[0] # O(1) - by index
arr[-1] # O(1) - last element
# Search
arr.index(3) # O(n) - find first occurrence
3 in arr # O(n) - membership test
# Insert
arr.append(6) # O(1) - at end
arr.insert(0, 0) # O(n) - at beginning/middle
arr.extend([7, 8]) # O(k) - k elements
# Delete
arr.pop() # O(1) - from end
arr.pop(0) # O(n) - from beginning
arr.remove(3) # O(n) - by value
del arr[2] # O(n) - by index
# Modify
arr[0] = 10 # O(1) - by index
arr.reverse() # O(n) - in-place
arr.sort() # O(n log n) - in-place
# Copy
arr[:] # O(n) - shallow copy
arr.copy() # O(n) - shallow copyCommon Array Patterns
# 1. SLIDING WINDOW
def max_sum_subarray(arr, k):
"""Find maximum sum of subarray of size k"""
max_sum = window_sum = sum(arr[:k])
for i in range(k, len(arr)):
window_sum = window_sum - arr[i-k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
# 2. TWO POINTERS
def two_sum_sorted(arr, target):
"""Find two numbers that sum to target in sorted array"""
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return None
# 3. PREFIX SUM
def range_sum_query(arr):
"""Precompute prefix sums for fast range queries"""
prefix = [0]
for num in arr:
prefix.append(prefix[-1] + num)
def query(left, right):
return prefix[right + 1] - prefix[left]
return query
# 4. KADANE'S ALGORITHM (Max subarray)
def max_subarray(arr):
"""Find maximum sum contiguous subarray"""
max_sum = current_sum = arr[0]
for num in arr[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# 5. DUTCH NATIONAL FLAG (3-way partition)
def sort_colors(nums):
"""Sort array of 0s, 1s, 2s in one pass"""
low = mid = 0
high = len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1Linked Lists
Implementation
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, val):
"""Add node at end - O(n)"""
if not self.head:
self.head = ListNode(val)
return
current = self.head
while current.next:
current = current.next
current.next = ListNode(val)
def prepend(self, val):
"""Add node at beginning - O(1)"""
new_node = ListNode(val)
new_node.next = self.head
self.head = new_node
def delete(self, val):
"""Delete first occurrence - O(n)"""
if not self.head:
return
if self.head.val == val:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.val == val:
current.next = current.next.next
return
current = current.next
def find(self, val):
"""Search for value - O(n)"""
current = self.head
while current:
if current.val == val:
return current
current = current.next
return NoneCommon Linked List Patterns
# 1. REVERSE LINKED LIST
def reverse_list(head):
"""Reverse singly linked list"""
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prev
# 2. DETECT CYCLE (Floyd's Algorithm)
def has_cycle(head):
"""Detect if linked list has cycle"""
if not head:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# 3. FIND MIDDLE
def find_middle(head):
"""Find middle node of linked list"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 4. MERGE TWO SORTED LISTS
def merge_two_lists(l1, l2):
"""Merge two sorted linked lists"""
dummy = ListNode(0)
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.next
# 5. REMOVE NTH FROM END
def remove_nth_from_end(head, n):
"""Remove nth node from end of list"""
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Move fast n steps ahead
for _ in range(n):
fast = fast.next
# Move both until fast reaches end
while fast.next:
fast = fast.next
slow = slow.next
# Remove node
slow.next = slow.next.next
return dummy.nextStacks & Queues
Stack Implementation
# Using list (simplest)
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""Add item to top - O(1)"""
self.items.append(item)
def pop(self):
"""Remove and return top item - O(1)"""
if not self.is_empty():
return self.items.pop()
raise IndexError("Stack is empty")
def peek(self):
"""Return top item without removing - O(1)"""
if not self.is_empty():
return self.items[-1]
raise IndexError("Stack is empty")
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Stack patterns
# 1. VALID PARENTHESES
def is_valid_parentheses(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
else:
stack.append(char)
return not stack
# 2. EVALUATE REVERSE POLISH NOTATION
def eval_rpn(tokens):
stack = []
operators = {'+', '-', '*', '/'}
for token in tokens:
if token in operators:
b, a = stack.pop(), stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
else:
stack.append(int(token))
return stack[0]
# 3. MIN STACK (O(1) min operation)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def get_min(self):
return self.min_stack[-1]Queue Implementation
from collections import deque
# Using deque (efficient)
class Queue:
def __init__(self):
self.items = deque()
def enqueue(self, item):
"""Add item to rear - O(1)"""
self.items.append(item)
def dequeue(self):
"""Remove and return front item - O(1)"""
if not self.is_empty():
return self.items.popleft()
raise IndexError("Queue is empty")
def front(self):
"""Return front item without removing - O(1)"""
if not self.is_empty():
return self.items[0]
raise IndexError("Queue is empty")
def is_empty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# Queue patterns
# 1. SLIDING WINDOW MAXIMUM
from collections import deque
def max_sliding_window(nums, k):
"""Find maximum in each window of size k"""
dq = deque() # Store indices
result = []
for i, num in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements (won't be max)
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# Add to result once window is full
if i >= k - 1:
result.append(nums[dq[0]])
return result
# 2. IMPLEMENT STACK USING QUEUES
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate all other elements
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]Trees & Graphs
Binary Tree Implementation
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# TREE TRAVERSALS
# 1. INORDER (Left, Root, Right)
def inorder_recursive(root):
if not root:
return []
return (inorder_recursive(root.left) +
[root.val] +
inorder_recursive(root.right))
def inorder_iterative(root):
result, stack = [], []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
# 2. PREORDER (Root, Left, Right)
def preorder_recursive(root):
if not root:
return []
return ([root.val] +
preorder_recursive(root.left) +
preorder_recursive(root.right))
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
# 3. POSTORDER (Left, Right, Root)
def postorder_recursive(root):
if not root:
return []
return (postorder_recursive(root.left) +
postorder_recursive(root.right) +
[root.val])
# 4. LEVEL ORDER (BFS)
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultCommon Tree Patterns
# 1. MAXIMUM DEPTH
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# 2. VALIDATE BST
def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if not root:
return True
if root.val <= min_val or root.val >= max_val:
return False
return (is_valid_bst(root.left, min_val, root.val) and
is_valid_bst(root.right, root.val, max_val))
# 3. LOWEST COMMON ANCESTOR
def lowest_common_ancestor(root, p, q):
if not root or root == p or root == q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right:
return root
return left or right
# 4. SERIALIZE/DESERIALIZE
def serialize(root):
"""Convert tree to string"""
if not root:
return "null"
return f"{root.val},{serialize(root.left)},{serialize(root.right)}"
def deserialize(data):
"""Convert string to tree"""
def helper(values):
val = next(values)
if val == "null":
return None
node = TreeNode(int(val))
node.left = helper(values)
node.right = helper(values)
return node
return helper(iter(data.split(',')))
# 5. PATH SUM
def has_path_sum(root, target_sum):
if not root:
return False
if not root.left and not root.right:
return root.val == target_sum
return (has_path_sum(root.left, target_sum - root.val) or
has_path_sum(root.right, target_sum - root.val))Graph Representation & Traversal
# GRAPH REPRESENTATIONS
# 1. Adjacency List (most common)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 2. Adjacency Matrix
# graph[i][j] = 1 if edge exists from i to j
graph_matrix = [
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 1],
[0, 0, 1, 0, 1, 0]
]
# DFS - Depth First Search
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
if node in visited:
return
visited.add(node)
print(node)
for neighbor in graph[node]:
dfs_recursive(graph, neighbor, visited)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
# BFS - Breadth First Search
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Hash Tables
Python Dictionaries (Hash Tables)
# BASIC OPERATIONS - All O(1) average case
# Create
hash_map = {}
hash_map = dict()
hash_map = {'key1': 'value1', 'key2': 'value2'}
# Insert/Update
hash_map['new_key'] = 'new_value'
hash_map.setdefault('key', 'default_value') # Only if key doesn't exist
# Access
value = hash_map['key'] # KeyError if not exists
value = hash_map.get('key', 'default') # Returns default if not exists
# Delete
del hash_map['key']
value = hash_map.pop('key', None)
hash_map.clear() # Remove all
# Check existence
if 'key' in hash_map:
pass
# Iterate
for key in hash_map:
print(key, hash_map[key])
for key, value in hash_map.items():
print(key, value)Hash Table Patterns
# 1. TWO SUM (using hash map)
def two_sum(nums, target):
"""Find indices of two numbers that sum to target"""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return None
# 2. FIRST NON-REPEATING CHARACTER
def first_uniq_char(s):
"""Find first character that appears only once"""
from collections import Counter
count = Counter(s)
for i, char in enumerate(s):
if count[char] == 1:
return i
return -1
# 3. GROUP ANAGRAMS
from collections import defaultdict
def group_anagrams(strs):
"""Group strings that are anagrams"""
anagrams = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
# 4. SUBARRAY SUM EQUALS K
def subarray_sum(nums, k):
"""Count subarrays with sum = k"""
count = 0
current_sum = 0
sum_freq = {0: 1} # sum: frequency
for num in nums:
current_sum += num
if current_sum - k in sum_freq:
count += sum_freq[current_sum - k]
sum_freq[current_sum] = sum_freq.get(current_sum, 0) + 1
return count
# 5. LRU CACHE
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key):
if key not in self.cache:
return -1
self.cache.move_to_end(key) # Mark as recently used
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove least recently usedHeaps
Heap Operations with heapq
import heapq
# CREATE MIN HEAP
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
# heap is now [1, 3, 7, 5]
# Or from existing list
nums = [5, 3, 7, 1]
heapq.heapify(nums) # Convert to min heap in-place - O(n)
# POP minimum - O(log n)
min_val = heapq.heappop(heap)
# PEEK minimum - O(1)
min_val = heap[0]
# PUSH and POP in one operation
val = heapq.heappushpop(heap, 4) # Push 4, then pop minimum
# REPLACE top element
val = heapq.heapreplace(heap, 10) # Pop minimum, then push 10
# N LARGEST/SMALLEST - O(n log k)
largest_3 = heapq.nlargest(3, [1, 5, 2, 8, 3]) # [8, 5, 3]
smallest_3 = heapq.nsmallest(3, [1, 5, 2, 8, 3]) # [1, 2, 3]
# With custom key
people = [('Alice', 30), ('Bob', 25), ('Charlie', 35)]
oldest_2 = heapq.nlargest(2, people, key=lambda x: x[1])
# [('Charlie', 35), ('Alice', 30)]
# MAX HEAP (negate values)
max_heap = []
for num in [5, 3, 7, 1]:
heapq.heappush(max_heap, -num)
max_val = -heapq.heappop(max_heap) # Get maximumHeap Patterns
# 1. KTH LARGEST ELEMENT
def find_kth_largest(nums, k):
"""Find kth largest element"""
# Method 1: Using nlargest
return heapq.nlargest(k, nums)[-1]
# Method 2: Min heap of size k
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
# 2. MERGE K SORTED LISTS
def merge_k_sorted(lists):
"""Merge k sorted lists"""
heap = []
result = []
# Initialize heap with first element from each list
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0)) # (value, list_idx, elem_idx)
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
# Add next element from same list
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
return result
# 3. TOP K FREQUENT ELEMENTS
from collections import Counter
def top_k_frequent(nums, k):
"""Find k most frequent elements"""
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
# 4. MEDIAN FINDER (two heaps)
class MedianFinder:
def __init__(self):
self.small = [] # Max heap (negated)
self.large = [] # Min heap
def add_num(self, num):
# Add to max heap (small)
heapq.heappush(self.small, -num)
# Balance: move largest from small to large
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
# Maintain size property
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small):
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def find_median(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2.0Algorithm Patterns
Two Pointers Pattern
When to Use
- Sorted array problems
- Finding pairs/triplets
- Palindrome checking
- Removing duplicates
- Container with most water
Template
def two_pointers_template(arr):
left, right = 0, len(arr) - 1
while left < right:
# Process current pair
if condition(arr[left], arr[right]):
# Found solution
return result
elif need_larger_sum:
left += 1 # Move left pointer right
else:
right -= 1 # Move right pointer left
return default_resultExamples
# 1. TWO SUM (sorted array)
def two_sum_sorted(nums, target):
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 []
# 2. THREE SUM
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # Skip duplicates
left, right = i + 1, len(nums) - 1
target = -nums[i]
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1
return resultSliding Window Pattern
Examples
# LONGEST SUBSTRING WITHOUT REPEATING
def length_of_longest_substring(s):
char_index = {}
max_length = 0
left = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_length = max(max_length, right - left + 1)
return max_lengthBinary Search, BFS, DFS, DP, Backtracking Patterns
See detailed patterns in Algorithm Patterns section above
Comprehensive Problem-Solving Examples
# Problem: Find missing number in array [0, n]
# Input: [3, 0, 1] Output: 2
# ❌ APPROACH 1: While loop (Inefficient)
def find_missing_while(nums):
n = len(nums)
i = 0
while i <= n:
if i not in nums:
return i
i += 1
# Time: O(n²), Space: O(1)
# ⚠️ APPROACH 2: For loop with set (Better)
def find_missing_for(nums):
num_set = set(nums)
for i in range(len(nums) + 1):
if i not in num_set:
return i
# Time: O(n), Space: O(n)
# ✅ APPROACH 3: Mathematical (Optimal)
def find_missing_math(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum
# Time: O(n), Space: O(1)
# 🚀 APPROACH 4: XOR (Bit manipulation - Most elegant)
def find_missing_xor(nums):
result = len(nums)
for i, num in enumerate(nums):
result ^= i ^ num
return result
# Time: O(n), Space: O(1)
# Reasoning: a ^ a = 0, a ^ 0 = aExample 2: Group Anagrams
# Problem: Group anagrams together
# Input: ["eat","tea","tan","ate","nat","bat"]
# Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
# ❌ APPROACH 1: Nested while loops (Very inefficient)
def group_anagrams_while(strs):
result = []
used = [False] * len(strs)
i = 0
while i < len(strs):
if used[i]:
i += 1
continue
group = [strs[i]]
used[i] = True
j = i + 1
while j < len(strs):
if not used[j] and sorted(strs[i]) == sorted(strs[j]):
group.append(strs[j])
used[j] = True
j += 1
result.append(group)
i += 1
return result
# Time: O(n² * k log k), Space: O(n)
# ✅ APPROACH 2: Hash map with sorted keys (Optimal)
from collections import defaultdict
def group_anagrams_dict(strs):
anagrams = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
anagrams[key].append(s)
return list(anagrams.values())
# Time: O(n * k log k), Space: O(n*k)
# 🚀 APPROACH 3: Hash map with character count (Most efficient)
def group_anagrams_count(strs):
anagrams = defaultdict(list)
for s in strs:
count = [0] * 26
for char in s:
count[ord(char) - ord('a')] += 1
anagrams[tuple(count)].append(s)
return list(anagrams.values())
# Time: O(n*k), Space: O(n*k)Example 3: Valid Parentheses
# Problem: Check if parentheses are balanced
# Input: "({[]})" → True, "([)]" → False
# ⚠️ APPROACH 1: While with manual tracking (Overcomplex)
def is_valid_while(s):
i = 0
stack = []
pairs = {')': '(', '}': '{', ']': '['}
while i < len(s):
if s[i] in '({[':
stack.append(s[i])
elif s[i] in ')}]':
if not stack or stack[-1] != pairs[s[i]]:
return False
stack.pop()
i += 1
return len(stack) == 0
# ✅ APPROACH 2: For loop with stack (Clear and efficient)
def is_valid_for(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs: # Closing bracket
if not stack or stack.pop() != pairs[char]:
return False
else: # Opening bracket
stack.append(char)
return not stack
# Time: O(n), Space: O(n)
# 🚀 APPROACH 3: Using deque (Slightly faster for large inputs)
from collections import deque
def is_valid_deque(s):
stack = deque()
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs:
if not stack or stack.pop() != pairs[char]:
return False
else:
stack.append(char)
return not stackExample 4: Longest Consecutive Sequence
# Problem: Find longest consecutive sequence in unsorted array
# Input: [100, 4, 200, 1, 3, 2] → 4 (sequence: 1,2,3,4)
# ❌ APPROACH 1: Nested while loops (O(n³))
def longest_consecutive_while(nums):
if not nums:
return 0
max_length = 0
i = 0
while i < len(nums):
current = nums[i]
length = 1
# Check consecutive up
j = current + 1
while j in nums:
length += 1
j += 1
# Check consecutive down
j = current - 1
while j in nums:
length += 1
j -= 1
max_length = max(max_length, length)
i += 1
return max_length
# ⚠️ APPROACH 2: Sort then iterate (O(n log n))
def longest_consecutive_sort(nums):
if not nums:
return 0
nums = sorted(set(nums))
max_length = current_length = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1] + 1:
current_length += 1
else:
max_length = max(max_length, current_length)
current_length = 1
return max(max_length, current_length)
# ✅ APPROACH 3: Set with smart iteration (O(n))
def longest_consecutive_set(nums):
if not nums:
return 0
num_set = set(nums)
max_length = 0
for num in num_set:
# Only start counting if it's the beginning of a sequence
if num - 1 not in num_set:
current_num = num
current_length = 1
while current_num + 1 in num_set:
current_num += 1
current_length += 1
max_length = max(max_length, current_length)
return max_length
# Time: O(n), Space: O(n)
# Key insight: Only count from sequence startsExample 5: Merge Intervals
# Problem: Merge overlapping intervals
# Input: [[1,3],[2,6],[8,10],[15,18]]
# Output: [[1,6],[8,10],[15,18]]
# ⚠️ APPROACH 1: While loop with manual merge (Complex)
def merge_while(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
i = 1
while i < len(intervals):
if intervals[i][0] <= merged[-1][1]:
# Merge
merged[-1][1] = max(merged[-1][1], intervals[i][1])
else:
merged.append(intervals[i])
i += 1
return merged
# ✅ APPROACH 2: For loop (Cleaner)
def merge_for(intervals):
if not intervals:
return []
intervals.sort()
merged = [intervals[0]]
for current in intervals[1:]:
if current[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], current[1])
else:
merged.append(current)
return merged
# Time: O(n log n), Space: O(n)Performance Optimization
1. Time Complexity Comparison
import time
def benchmark(func, *args, iterations=10000):
start = time.perf_counter()
for _ in range(iterations):
func(*args)
return time.perf_counter() - start
# Example: Sum of squares
data = list(range(1000))
# Method 1: While loop
def sum_squares_while(nums):
result = 0
i = 0
while i < len(nums):
result += nums[i] ** 2
i += 1
return result
# Method 2: For loop
def sum_squares_for(nums):
result = 0
for num in nums:
result += num ** 2
return result
# Method 3: List comprehension + sum
def sum_squares_comp(nums):
return sum(x ** 2 for x in nums)
# Method 4: Map + sum
def sum_squares_map(nums):
return sum(map(lambda x: x ** 2, nums))
# Results:
# While loop: ~0.15 ms
# For loop: ~0.13 ms (13% faster)
# Comprehension: ~0.11 ms (27% faster)
# Map: ~0.12 ms (20% faster)2. Space Optimization
# Problem: Process large file
# ❌ BAD: Load all into memory
def process_file_all(filename):
with open(filename) as f:
lines = f.readlines() # Loads entire file!
for line in lines:
process(line)
# Space: O(file_size)
# ✅ GOOD: Line-by-line iteration
def process_file_iter(filename):
with open(filename) as f:
for line in f: # File object is iterable
process(line)
# Space: O(1)
# 🚀 BEST: Generator for transformation
def process_file_gen(filename):
def read_lines():
with open(filename) as f:
for line in f:
yield line.strip()
for line in read_lines():
process(line)
# Space: O(1), Composable3. When to Use While vs For – Performance
# Scenario 1: Known iterations
# Winner: FOR loop (slightly faster, more readable)
for i in range(1000000):
pass # ~30ms
i = 0
while i < 1000000:
i += 1 # ~35ms
# Scenario 2: Early exit with unknown iterations
# Winner: WHILE loop (same performance, clearer intent)
def find_first_while(nums, condition):
i = 0
while i < len(nums):
if condition(nums[i]):
return i
i += 1
return -1
def find_first_for(nums, condition):
for i, num in enumerate(nums):
if condition(num):
return i
return -1
# Performance: Identical
# Readability: FOR wins
# Scenario 3: Two pointers
# Winner: WHILE loop (natural fit)
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right: # Clear termination
current = arr[left] + arr[right]
if current == target:
return [left, right]
elif current < target:
left += 1
else:
right -= 1
return None4. Memory Profiling
import sys
# Compare memory usage
# List (eager evaluation)
numbers_list = [x ** 2 for x in range(1000000)]
print(sys.getsizeof(numbers_list)) # ~8 MB
# Generator (lazy evaluation)
numbers_gen = (x ** 2 for x in range(1000000))
print(sys.getsizeof(numbers_gen)) # ~200 bytes
# Rule: Use generators when:
# 1. Processing large datasets
# 2. Only need one pass
# 3. Don't need random access
# 4. Building pipelinesFinal Decision Framework
Quick Reference Table
| Situation | Tool Choice | Reasoning |
|---|---|---|
| Iterate fixed range | for i in range(n) | Pythonic, safe, fast |
| Iterate collection | for item in collection | Direct, readable |
| Unknown iterations | while condition | Flexible termination |
| Two pointers | while left < right | Natural pattern |
| Find first match | next((x for x in ... if cond), None) | Short-circuit eval |
| Transform all | List comprehension | Fastest, readable |
| Filter items | List comp with if | Clear intent |
| Count frequencies | Counter | Purpose-built |
| Sort items | sorted() or .sort() | Optimized algorithm |
| Top K items | heapq.nlargest/nsmallest | O(n log k) |
| Group items | defaultdict or groupby | Automatic handling |
| Accumulate values | reduce or accumulate | Functional style |
| Infinite sequence | Generator with while True | Memory efficient |
| Large file | Generator/iterator | Stream processing |
| Need indices | enumerate() | Clean, Pythonic |
| Parallel iteration | zip() | Simultaneous access |
| Recursive with memo | @lru_cache | Auto-optimization |
Basic Syntax
# Standard while loop
while condition:
# Code block
# Update condition variablesKey Components
- Condition: Boolean expression evaluated before each iteration
- Body: Code block executed when condition is True
- Update: Mechanism to eventually make condition False (prevent infinite loop)
- Break: Optional early exit
- Continue: Optional skip to next iteration
Step-by-Step Approach
Recommended Initiation Process
Step 1: Define the Problem
- Identify what needs to be repeated
- Determine when repetition should stop
- Identify what changes each iteration
Step 2: Initialize Variables
# Example: Count to 10
counter = 1 # Start value
limit = 10 # End conditionStep 3: Write the Condition
while counter <= limit:
# Loop bodyStep 4: Implement Loop Body
while counter <= limit:
print(f"Count: {counter}")
# Process logic hereStep 5: Update Loop Variables
while counter <= limit:
print(f"Count: {counter}")
counter += 1 # CRITICAL: Ensure condition will eventually be FalseStep 6: Add Safety Mechanisms
counter = 1
limit = 10
max_iterations = 100 # Safety limit
while counter <= limit and max_iterations > 0:
print(f"Count: {counter}")
counter += 1
max_iterations -= 1When to Use While Loops
✅ Ideal Use Cases
1. Unknown Number of Iterations
# User input validation
user_input = ""
while user_input.lower() != "quit":
user_input = input("Enter command (or 'quit' to exit): ")
process_command(user_input)2. Condition-Based Termination
# Processing until a condition is met
import random
target = 50
current = 0
while current < target:
current += random.randint(1, 10)
print(f"Current value: {current}")3. Infinite Loops with Break
# Server/Game loops
while True:
event = get_next_event()
if event == "SHUTDOWN":
break
handle_event(event)4. Complex Exit Conditions
# Multiple conditions
attempts = 0
success = False
max_attempts = 3
while attempts < max_attempts and not success:
success = try_operation()
attempts += 15. Pointer/Index-Based Problems
# Two pointers technique
left, right = 0, len(arr) - 1
while left < right:
if arr[left] + arr[right] == target:
return [left, right]
elif arr[left] + arr[right] < target:
left += 1
else:
right -= 16. Stream Processing
# Reading from files/streams
with open('large_file.txt', 'r') as f:
line = f.readline()
while line:
process_line(line)
line = f.readline()7. Mathematical Convergence
# Newton's method, gradient descent
epsilon = 0.0001
difference = float('inf')
while difference > epsilon:
new_value = calculate_next_iteration()
difference = abs(new_value - old_value)
old_value = new_valueWhen NOT to Use While Loops
❌ Avoid While Loops For:
1. Known Iteration Count
# ❌ BAD: Using while for fixed iterations
i = 0
while i < 10:
print(i)
i += 1
# ✅ GOOD: Use for loop instead
for i in range(10):
print(i)2. Iterating Over Collections
# ❌ BAD: Manual index management
items = ['a', 'b', 'c', 'd']
i = 0
while i < len(items):
print(items[i])
i += 1
# ✅ GOOD: Direct iteration
for item in items:
print(item)3. Range-Based Loops
# ❌ BAD: Manually tracking range
start = 5
end = 15
current = start
while current < end:
print(current)
current += 1
# ✅ GOOD: Use range
for num in range(5, 15):
print(num)4. Dictionary/Set Iteration
# ❌ BAD: Converting to list for while loop
data = {'a': 1, 'b': 2, 'c': 3}
keys = list(data.keys())
i = 0
while i < len(keys):
print(f"{keys[i]}: {data[keys[i]]}")
i += 1
# ✅ GOOD: Direct iteration
for key, value in data.items():
print(f"{key}: {value}")While vs For Loop Comparison
Comparison Table
| Aspect | While Loop | For Loop |
|---|---|---|
| Iteration Count | Unknown or variable | Known or determinable |
| Syntax Complexity | More verbose | More concise |
| Loop Variable | Manual management | Automatic management |
| Risk of Infinite Loop | Higher (manual control) | Lower (automatic termination) |
| Use Cases | Condition-based, complex logic | Iteration over sequences |
| Performance | Same (negligible difference) | Same (negligible difference) |
| Readability | Good for conditions | Better for collections |
| Memory | Same | Same (unless generator) |
Side-by-Side Examples
Example 1: Counting
# WHILE: When count depends on condition
count = 0
total = 0
while total < 100:
count += 1
total += random.randint(1, 20)
# FOR: When count is predetermined
for count in range(10):
process(count)Example 2: List Processing
# WHILE: When processing with complex conditions
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
index = 0
sum_val = 0
while index < len(numbers) and sum_val < 20:
sum_val += numbers[index]
index += 1
# FOR: Standard iteration
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for num in numbers:
print(num * 2)Example 3: Nested Loops
# WHILE: Complex nested conditions
i = 0
while i < rows:
j = 0
while j < cols and matrix[i][j] != target:
process(matrix[i][j])
j += 1
i += 1
# FOR: Regular matrix iteration
for i in range(rows):
for j in range(cols):
process(matrix[i][j])While vs Generators Comparison
Comparison Table
| Aspect | While Loop | Generator |
|---|---|---|
| Memory Efficiency | Stores all values | Lazy evaluation (one at a time) |
| Computation | All upfront | On-demand |
| State Management | Manual | Automatic (yield) |
| Reusability | Must re-run | Exhaustible (one-time use) |
| Complexity | Simple logic | Function-based |
| Best For | Active processing | Data streaming/pipelines |
Side-by-Side Examples
Example 1: Infinite Sequences
# WHILE: Active loop with break
def process_with_while(limit):
count = 0
while True:
if count >= limit:
break
yield count ** 2
count += 1
# GENERATOR: More elegant
def process_with_generator(limit):
count = 0
while count < limit:
yield count ** 2
count += 1
# Usage
for val in process_with_generator(5):
print(val) # 0, 1, 4, 9, 16Example 2: Fibonacci Sequence
# WHILE: Store all values in list
def fibonacci_while(n):
result = []
a, b = 0, 1
count = 0
while count < n:
result.append(a)
a, b = b, a + b
count += 1
return result
# GENERATOR: Memory efficient
def fibonacci_generator(n):
a, b = 0, 1
count = 0
while count < n:
yield a
a, b = b, a + b
count += 1
# Comparison
fib_list = fibonacci_while(10) # Stores all 10 numbers in memory
fib_gen = fibonacci_generator(10) # Generates on-demand
for num in fib_gen:
print(num) # Only one number in memory at a timeExample 3: File Processing
# WHILE: Load all into memory
def read_all_lines(filename):
lines = []
with open(filename, 'r') as f:
line = f.readline()
while line:
lines.append(line.strip())
line = f.readline()
return lines
# GENERATOR: Process line by line
def read_lines_generator(filename):
with open(filename, 'r') as f:
line = f.readline()
while line:
yield line.strip()
line = f.readline()
# Even better: Built-in iteration
def read_lines_pythonic(filename):
with open(filename, 'r') as f:
for line in f: # File objects are already generators!
yield line.strip()Data Type Selection Guide
Choosing Loop Type Based on Data Structure
1. Lists / Arrays
Use FOR when:
# Simple iteration
numbers = [1, 2, 3, 4, 5]
for num in numbers:
print(num * 2)
# With index
for i, num in enumerate(numbers):
print(f"Index {i}: {num}")Use WHILE when:
# Two pointers (sorted array)
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return None
# Processing with modification
numbers = [1, 2, 3, 4, 5]
i = 0
while i < len(numbers):
if numbers[i] % 2 == 0:
numbers.pop(i) # Modifying list
else:
i += 12. Strings
Use FOR when:
# Character iteration
text = "Hello World"
for char in text:
print(char)
# Pattern matching
for i in range(len(text) - 2):
substring = text[i:i+3]
if substring == "llo":
print(f"Found at index {i}")Use WHILE when:
# Parsing with variable advancement
def parse_number(s):
i = 0
result = ""
while i < len(s) and s[i].isdigit():
result += s[i]
i += 1
return int(result) if result else None
# Sliding window
def has_duplicate_in_window(s, k):
i = 0
while i < len(s) - k + 1:
window = s[i:i+k]
if len(set(window)) < k:
return True
i += 1
return False3. Dictionaries
Use FOR when:
# Simple iteration
data = {'name': 'John', 'age': 30, 'city': 'NYC'}
for key in data:
print(key, data[key])
for key, value in data.items():
print(f"{key}: {value}")Use WHILE when:
# Processing with dynamic changes
cache = {'a': 1, 'b': 2, 'c': 3}
keys_to_process = list(cache.keys())
i = 0
while i < len(keys_to_process):
key = keys_to_process[i]
if cache[key] > 1:
# Add new key during processing
cache[f"{key}_new"] = cache[key] * 2
i += 14. Sets
Use FOR when:
# Simple iteration
unique_items = {1, 2, 3, 4, 5}
for item in unique_items:
print(item)Use WHILE when:
# Processing with removal
numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
while numbers:
item = numbers.pop()
if item % 2 == 0:
process_even(item)
else:
process_odd(item)5. Queues / Stacks
Use WHILE for:
from collections import deque
# BFS with queue
def bfs(graph, start):
queue = deque([start])
visited = set([start])
while queue:
node = queue.popleft()
process(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Stack processing
stack = [1, 2, 3, 4, 5]
while stack:
item = stack.pop()
process(item)6. Linked Lists
Use WHILE for:
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Traversal
def traverse(head):
current = head
while current:
print(current.val)
current = current.next
# Two pointers (fast/slow)
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow7. Trees
Use WHILE for:
# Iterative traversal
def level_order(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
level = []
while level_size > 0:
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
level_size -= 1
result.append(level)
return resultCommon Patterns & Techniques
1. Counter Pattern
# Count until condition
count = 0
while count < 10:
print(f"Iteration {count}")
count += 12. Accumulator Pattern
# Sum until threshold
total = 0
num = 1
while total < 100:
total += num
num += 1
print(f"Sum: {total}, Last number: {num}")3. Sentinel Pattern
# Read until sentinel value
value = input("Enter a number (0 to stop): ")
while value != "0":
process(value)
value = input("Enter a number (0 to stop): ")4. Flag Pattern
# Continue until flag is set
found = False
index = 0
while index < len(data) and not found:
if data[index] == target:
found = True
else:
index += 15. Two Pointers Pattern
# Process from both ends
left, right = 0, len(arr) - 1
while left < right:
# Process
if condition:
left += 1
else:
right -= 16. Sliding Window Pattern
# Fixed-size window
window_start = 0
window_sum = 0
max_sum = float('-inf')
for window_end in range(len(arr)):
window_sum += arr[window_end]
if window_end >= k - 1:
max_sum = max(max_sum, window_sum)
window_sum -= arr[window_start]
window_start += 17. Nested While Pattern
# Complex 2D processing
row = 0
while row < len(matrix):
col = 0
while col < len(matrix[0]):
process(matrix[row][col])
col += 1
row += 18. While-Else Pattern
# Execute else if loop completes normally
attempts = 0
max_attempts = 3
while attempts < max_attempts:
if try_operation():
break
attempts += 1
else:
# Executed if no break occurred
print("All attempts failed")Best Practices
1. Always Ensure Termination
# ❌ BAD: Potential infinite loop
count = 0
while count >= 0:
print(count)
# count never becomes negative!
# ✅ GOOD: Clear termination
count = 0
while count < 10:
print(count)
count += 12. Initialize Before Loop
# ✅ GOOD: All variables initialized
total = 0
count = 0
threshold = 100
while total < threshold:
total += count
count += 13. Use Meaningful Conditions
# ❌ BAD: Unclear condition
while x:
# What does x represent?
process()
# ✅ GOOD: Clear intention
while not_finished:
process()
not_finished = check_status()4. Avoid Complex Conditions
# ❌ BAD: Hard to read
while i < len(arr) and (arr[i] > 0 or flag) and count < max_count and not done:
process()
# ✅ GOOD: Use helper function or break it down
def should_continue(i, arr, flag, count, max_count, done):
return (i < len(arr) and
(arr[i] > 0 or flag) and
count < max_count and
not done)
while should_continue(i, arr, flag, count, max_count, done):
process()5. Use Break for Early Exit
# ✅ GOOD: Clean early exit
while True:
user_input = get_input()
if user_input == "quit":
break
process(user_input)6. Add Safety Limits for Debugging
# ✅ GOOD: Prevent infinite loops during development
max_iterations = 1000
iteration_count = 0
while condition and iteration_count < max_iterations:
process()
iteration_count += 1
if iteration_count >= max_iterations:
print("WARNING: Maximum iterations reached")Real-World Examples
Example 1: Binary Search
def binary_search(arr, target):
"""Use while for unknown iteration count"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Example 2: Input Validation
def get_valid_age():
"""Use while for retry logic"""
while True:
try:
age = int(input("Enter your age (0-120): "))
if 0 <= age <= 120:
return age
else:
print("Age must be between 0 and 120")
except ValueError:
print("Please enter a valid number")Example 3: Game Loop
def game_loop():
"""Use while for continuous game state"""
running = True
player_health = 100
while running and player_health > 0:
# Get player action
action = get_player_action()
if action == "quit":
running = False
continue
# Process action
result = process_action(action)
player_health -= result.damage
# Update game state
update_game_state()
render_screen()
print("Game Over")Example 4: Data Processing Pipeline
def process_stream(data_source):
"""Process data until source is exhausted"""
batch_size = 100
while True:
batch = data_source.get_batch(batch_size)
if not batch: # No more data
break
# Process batch
processed = transform(batch)
validate(processed)
save(processed)
print(f"Processed {len(batch)} items")Example 5: Retry with Backoff
import time
def api_call_with_retry(url, max_retries=3):
"""Use while for retry logic with exponential backoff"""
retries = 0
backoff = 1
while retries < max_retries:
try:
response = make_request(url)
if response.status_code == 200:
return response.data
else:
raise Exception(f"HTTP {response.status_code}")
except Exception as e:
retries += 1
if retries >= max_retries:
raise Exception(f"Failed after {max_retries} retries")
print(f"Retry {retries}/{max_retries} after {backoff}s")
time.sleep(backoff)
backoff *= 2 # Exponential backoffExample 6: Linked List Reversal
def reverse_linked_list(head):
"""Use while for pointer manipulation"""
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prevExample 7: Finding Square Root (Newton’s Method)
def sqrt(n, precision=0.00001):
"""Use while for convergence"""
if n < 0:
raise ValueError("Cannot compute square root of negative number")
guess = n / 2
while abs(guess * guess - n) > precision:
guess = (guess + n / guess) / 2
return guess
# Example: sqrt(25) -> 5.0Example 8: Merge Two Sorted Lists
def merge_sorted_lists(list1, list2):
"""Use while with multiple conditions"""
result = []
i, j = 0, 0
while i < len(list1) and j < len(list2):
if list1[i] <= list2[j]:
result.append(list1[i])
i += 1
else:
result.append(list2[j])
j += 1
# Append remaining elements
while i < len(list1):
result.append(list1[i])
i += 1
while j < len(list2):
result.append(list2[j])
j += 1
return resultQuick Decision Guide
START: Need to repeat something?
│
├─ Do you know exactly how many times?
│ ├─ YES → Use FOR loop
│ └─ NO → Continue
│
├─ Are you iterating over a collection?
│ ├─ YES → Use FOR loop (unless complex pointer logic needed)
│ └─ NO → Continue
│
├─ Is it based on a condition that might change unpredictably?
│ ├─ YES → Use WHILE loop
│ └─ NO → Continue
│
├─ Need lazy evaluation for large datasets?
│ ├─ YES → Use Generator
│ └─ NO → Continue
│
├─ Complex exit conditions or multiple pointers?
│ ├─ YES → Use WHILE loop
│ └─ NO → Use FOR loopSummary Cheat Sheet
| Scenario | Recommended Loop |
|---|---|
| Known iterations | for i in range(n) |
| Collection iteration | for item in collection |
| Unknown iterations | while condition |
| User input validation | while True with break |
| Two pointers | while left < right |
| Tree/Graph traversal (iterative) | while queue/stack |
| Convergence algorithms | while abs(diff) > epsilon |
| Infinite game/server loop | while True with exit conditions |
| Stream processing | Generator or while |
| Large dataset iteration | Generator |
| List modification during iteration | while with manual index |
| Simple counting | for loop |
Remember: When in doubt, prefer for loops for clarity and safety. Use while loops when the iteration count is truly unknown or when complex condition-based logic is required.
Practical Tips & Gotchas
Common Mistakes to Avoid
1. Off-by-One Errors
# ❌ BAD: Misses last element
i = 0
while i < len(arr) - 1: # Should be: i < len(arr)
process(arr[i])
i += 1
# ✅ GOOD: Correct boundary
i = 0
while i < len(arr):
process(arr[i])
i += 12. Infinite Loops
# ❌ BAD: Never updates condition
count = 0
while count < 10:
print("Hello")
# Forgot: count += 1
# ✅ GOOD: Always update loop variable
count = 0
while count < 10:
print("Hello")
count += 13. Modifying Collection During Iteration
# ❌ BAD: Undefined behavior
numbers = [1, 2, 3, 4, 5]
for num in numbers:
if num % 2 == 0:
numbers.remove(num) # DON'T DO THIS
# ✅ GOOD: Create new list
numbers = [1, 2, 3, 4, 5]
numbers = [num for num in numbers if num % 2 != 0]
# ✅ ALTERNATIVE: While with manual index
i = 0
while i < len(numbers):
if numbers[i] % 2 == 0:
numbers.pop(i)
else:
i += 14. Unnecessary While Loops
# ❌ BAD: Using while for simple iteration
i = 0
while i < len(items):
print(items[i])
i += 1
# ✅ GOOD: Use for loop
for item in items:
print(item)Performance Tips
1. Use Built-in Functions
# Slow: Manual loop
total = 0
for num in numbers:
total += num
# Fast: Built-in (implemented in C)
total = sum(numbers) # Up to 10x faster2. List Comprehensions vs Loops
# Slower: Append in loop
result = []
for x in range(1000):
result.append(x ** 2)
# Faster: List comprehension (optimized)
result = [x ** 2 for x in range(1000)] # ~30% faster3. Avoid Repeated Function Calls in Condition
# ❌ BAD: Calls len() every iteration
i = 0
while i < len(expensive_list): # len() called repeatedly
process(expensive_list[i])
i += 1
# ✅ GOOD: Cache the length
length = len(expensive_list)
i = 0
while i < length:
process(expensive_list[i])
i += 1
# ✅ BEST: Use for loop (automatically optimized)
for item in expensive_list:
process(item)Debugging Techniques
# 1. Add iteration counter to prevent infinite loops
MAX_ITER = 10000
iter_count = 0
while condition and iter_count < MAX_ITER:
# Your code
iter_count += 1
if iter_count >= MAX_ITER:
print(f"WARNING: Hit max iterations!")
# 2. Print loop state for debugging
while condition:
print(f"DEBUG: i={i}, value={value}, condition={condition}")
# Your code
# 3. Use assertions
while i < len(arr):
assert 0 <= i < len(arr), f"Index out of bounds: {i}"
process(arr[i])
i += 1Interview Problem Patterns
Pattern Recognition Guide
# PATTERN 1: Sliding Window
"""
Keywords: substring, subarray, consecutive, window
Use: Two pointers with while loop
"""
def sliding_window_template(s, k):
window_start = 0
max_sum = 0
window_sum = 0
for window_end in range(len(s)):
window_sum += s[window_end]
if window_end >= k - 1:
max_sum = max(max_sum, window_sum)
window_sum -= s[window_start]
window_start += 1
return max_sum
# PATTERN 2: Two Pointers
"""
Keywords: sorted array, pairs, palindrome
Use: While loop with left/right pointers
"""
def two_pointer_template(arr):
left, right = 0, len(arr) - 1
while left < right:
# Process current pair
if condition_met(arr[left], arr[right]):
return process()
elif need_larger:
left += 1
else:
right -= 1
return result
# PATTERN 3: Fast & Slow Pointers
"""
Keywords: cycle detection, linked list, middle element
Use: While loop with two speeds
"""
def fast_slow_template(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # Cycle detected
return True
return False
# PATTERN 4: Binary Search
"""
Keywords: sorted, search, find, log(n)
Use: While loop with mid calculation
"""
def binary_search_template(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# PATTERN 5: BFS (Level Order)
"""
Keywords: level, shortest path, tree level
Use: While loop with queue
"""
from collections import deque
def bfs_template(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
level = []
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
# PATTERN 6: Backtracking with State
"""
Keywords: combinations, permutations, subsets
Use: While or recursion with state tracking
"""
def backtrack_template(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i])
path.pop()
backtrack(0, [], target)
return resultStudy Checklist
Master These Concepts:
- While Loop Basics
- Understand condition evaluation
- Know when to increment loop variable
- Practice with break and continue
- For Loop Mastery
- Use
range()effectively - Understand
enumerate()andzip() - Master list comprehensions
- Use
- Built-in Functions
- Memorize
map(),filter(),reduce() - Know
all(),any(),sum() - Use
sorted()with custom keys
- Memorize
- Collections Module
- Master
Counterfor frequency - Use
defaultdictfor grouping - Know
dequefor queues
- Master
- Itertools Module
- Use
combinations()andpermutations() - Know
chain(),groupby(),accumulate() - Understand generators
- Use
- Common Patterns
- Two pointers technique
- Sliding window
- Fast & slow pointers
- Binary search variations
- Optimization
- Choose right data structure
- Avoid nested loops when possible
- Use sets for O(1) lookup
- Consider space-time tradeoffs
Additional Resources
Practice Problems by Pattern:
While Loop Focus:
- Linked List Cycle (Floyd’s Algorithm)
- Binary Search variations
- Two Sum on sorted array
- Container With Most Water
- Trapping Rain Water
- Palindrome verification
- String parsing problems
- Game simulations
Built-in Tools Focus:
- Group Anagrams (Counter, defaultdict)
- Top K Frequent Elements (heapq)
- Valid Anagram (Counter)
- Intersection of Arrays (set)
- Merge Intervals (sorted)
Optimization Focus:
- Two Sum (dict vs two loops)
- Longest Substring Without Repeating (sliding window)
- Find All Anagrams (Counter with window)
- Subarray Sum Equals K (prefix sum)
Summary: The Decision Flowchart
CODING PROBLEM
↓
1. UNDERSTAND
- Input/Output types?
- Constraints?
- Edge cases?
↓
2. CATEGORIZE
- Search? Count? Transform?
- Sort? Generate? Validate?
↓
3. CHECK BUILT-INS
- Counter for frequency?
- sorted() for ordering?
- set() for uniqueness?
- heapq for top K?
↓
4. CHOOSE ITERATION
├─ Known count → FOR LOOP
├─ Unknown count → WHILE LOOP
├─ Large data → GENERATOR
└─ Collection → FOR LOOP
↓
5. OPTIMIZE
- Time complexity acceptable?
- Space usage reasonable?
- Can use better data structure?
↓
6. TEST
- Normal cases
- Edge cases
- Large inputs
↓
7. REFACTOR
- More Pythonic?
- Better variable names?
- Remove duplication?Final Wisdom:
“Simple is better than complex. Complex is better than complicated.” — The Zen of Python
Key Takeaways:
- Prefer built-ins – They’re faster and battle-tested
- For > While – Use for loops unless you need while
- Comprehensions – More Pythonic than manual loops
- Right tool – Counter > dict, set > list for lookup
- Read others’ code – Learn idiomatic patterns
- Profile first – Optimize what matters
- Readability counts – Code is read more than written
Top Coding Problems for Python SDE Interviews
Problem Categories & Essential Questions
1. Array & String Manipulation
Essential problems that form the foundation of coding interviews:
- Two Sum / Three Sum – Hash map technique
- Maximum Subarray (Kadane’s Algorithm) – Dynamic programming
- Merge Intervals – Sorting + greedy approach
- Rotate Array – Array manipulation
- Longest Substring Without Repeating Characters – Sliding window
- Valid Parentheses – Stack-based validation
- Group Anagrams – Hash table with sorted keys
2. Linked Lists
Core linked list operations:
- Reverse Linked List – Iterative & recursive approaches
- Detect Cycle in Linked List – Fast & slow pointers
- Merge Two Sorted Lists – Two-pointer technique
- Remove Nth Node From End – Two-pass or one-pass approach
- Add Two Numbers – Digit-by-digit addition with carry
3. Trees & Graphs
Tree and graph traversal problems:
- Binary Tree Traversal – Inorder, Preorder, Postorder (iterative & recursive)
- Validate Binary Search Tree – In-order traversal property
- Lowest Common Ancestor – Tree navigation
- Number of Islands – DFS/BFS on grid
- Course Schedule – Graph cycle detection (topological sort)
- Binary Tree Level Order Traversal – BFS with queue
4. Dynamic Programming
Optimization problems with overlapping subproblems:
- Climbing Stairs – Basic DP introduction
- Coin Change – Unbounded knapsack variant
- Longest Increasing Subsequence – Classic DP
- House Robber – DP with constraint
- Edit Distance – String DP
- 0/1 Knapsack – Classic optimization
5. Searching & Sorting
Search and sort algorithm mastery:
- Binary Search & Variants – Search space reduction
- Merge Sort / Quick Sort – Divide and conquer
- Find First and Last Position – Modified binary search
- Search in Rotated Sorted Array – Binary search variant
- Kth Largest Element – QuickSelect or heap
6. Stack & Queue
Stack and queue-based problems:
- Implement Queue using Stacks – Data structure design
- Min Stack – Stack with O(1) minimum
- Valid Parentheses – Stack matching
- Sliding Window Maximum – Deque optimization
7. Hash Tables & Sets
Hash-based efficient solutions:
- Two Sum – Hash map for O(n) solution
- Subarray Sum Equals K – Prefix sum + hash map
- Longest Consecutive Sequence – Union-find or hash set
- First Non-Repeating Character – Frequency counting
8. Backtracking
Combinatorial search problems:
- Permutations & Combinations – Complete enumeration
- Subsets – Power set generation
- N-Queens – Constraint satisfaction
- Word Search – Grid backtracking
- Generate Parentheses – Valid sequence generation
9. Heap/Priority Queue
Heap-based efficient solutions:
- Kth Largest Element – Min heap approach
- Merge K Sorted Lists – Min heap merging
- Top K Frequent Elements – Heap or bucket sort
- Find Median from Data Stream – Two heaps
10. Two Pointers & Sliding Window
Efficient linear algorithms:
- Container With Most Water – Two pointers from ends
- Trapping Rain Water – Two pointers or stack
- Minimum Window Substring – Sliding window with hash map
- Longest Substring Without Repeating Characters – Sliding window
Problem-Solving Strategy: REACTO Framework
R – Repeat
Restate the problem to ensure understanding:
# Example conversation:
# Interviewer: "Find two numbers that add up to target"
# You: "So I need to find indices of two numbers in the array
# that sum to the target value, and I can assume there's
# exactly one solution?"Key Actions:
- Paraphrase the problem in your own words
- Clarify ambiguities (Can I modify input? Multiple solutions?)
- Confirm input/output format
E – Examples
Create and walk through examples:
# Problem: Two Sum
# Input: nums = [2, 7, 11, 15], target = 9
# Example 1 (Simple):
nums = [2, 7, 11, 15], target = 9
# Output: [0, 1] because nums[0] + nums[1] = 9
# Example 2 (Edge case):
nums = [3, 3], target = 6
# Output: [0, 1] - can use same value twice?
# Example 3 (No solution):
nums = [1, 2, 3], target = 10
# Output: [] or None?Key Actions:
- Simple case (happy path)
- Complex case (larger input)
- Edge cases (empty, single element, duplicates, negatives)
A – Approach
Discuss approaches from brute force to optimal:
# Problem: Two Sum
# Approach 1: Brute Force - O(n²)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# Approach 2: Hash Map - O(n)
def two_sum_optimal(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = iKey Actions:
- Start with brute force (shows you can solve it)
- Analyze time/space complexity
- Optimize using appropriate data structures
- Explain trade-offs
C – Code
Write clean, production-quality code:
def two_sum(nums: list[int], target: int) -> list[int]:
"""
Find indices of two numbers that add up to target.
Args:
nums: List of integers
target: Target sum value
Returns:
List of two indices [i, j] where nums[i] + nums[j] == target
Time: O(n), Space: O(n)
"""
# Edge case: less than 2 numbers
if len(nums) < 2:
return []
# Hash map to store value -> index mapping
seen = {}
# Single pass through array
for i, num in enumerate(nums):
complement = target - num
# Check if complement exists
if complement in seen:
return [seen[complement], i]
# Store current number
seen[num] = i
# No solution found
return []Key Actions:
- Use meaningful variable names
- Add type hints (Python 3.5+)
- Include docstrings
- Handle edge cases
- Add helpful comments for complex logic
T – Test
Test thoroughly with various inputs:
# Test cases for two_sum
def test_two_sum():
# Normal case
assert two_sum([2, 7, 11, 15], 9) == [0, 1]
# Duplicates
assert two_sum([3, 3], 6) == [0, 1]
# Negative numbers
assert two_sum([-1, -2, -3, -4], -5) == [1, 2]
# No solution
assert two_sum([1, 2, 3], 10) == []
# Edge: empty array
assert two_sum([], 5) == []
# Edge: single element
assert two_sum([5], 5) == []
# Large numbers
assert two_sum([1000000, 2000000, 3000000], 5000000) == [1, 2]
print("All tests passed!")
test_two_sum()Key Actions:
- Test with your examples
- Test edge cases
- Test boundary conditions
- Consider performance with large inputs
O – Optimize
Discuss further optimizations and trade-offs:
# Original: O(n) time, O(n) space
def two_sum_hash(nums, target):
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = i
# Alternative: Two pointers (requires sorted array)
# O(n log n) time, O(1) space
def two_sum_sorted(nums, target):
# Would need to track original indices
indexed_nums = [(num, i) for i, num in enumerate(nums)]
indexed_nums.sort() # O(n log n)
left, right = 0, len(nums) - 1
while left < right:
current_sum = indexed_nums[left][0] + indexed_nums[right][0]
if current_sum == target:
return [indexed_nums[left][1], indexed_nums[right][1]]
elif current_sum < target:
left += 1
else:
right -= 1
return []Discussion Points:
- Can we reduce space complexity?
- Can we reduce time complexity?
- What if input is sorted?
- What if we need all pairs?
- Trade-offs between approaches
Step-by-Step Interview Approach
Phase 1: Understanding (5 minutes)
# Checklist before coding:
"""
□ What are the input constraints?
- Size: n ≤ 10^5 or 10^6?
- Values: negative numbers allowed?
- Type: integers only or floats too?
□ What's the expected output?
- Single value or collection?
- Indices or values?
- Sorted or any order?
□ What are the edge cases?
- Empty input?
- Single element?
- All duplicates?
- Very large/small numbers?
□ Can I modify the input?
- Sorting allowed?
- In-place modification?
□ Time/space constraints?
- Expected complexity?
- Memory limitations?
"""Phase 2: Pattern Recognition
Identify which algorithmic pattern applies:
| Pattern | Use Case | Example Problems |
|---|---|---|
| Two Pointers | Sorted array, palindrome, pair problems | Two Sum (sorted), Container with Water |
| Sliding Window | Substring, subarray, contiguous elements | Longest Substring, Max Sum Subarray |
| Fast & Slow Pointers | Cycle detection, middle element | Linked List Cycle, Happy Number |
| Binary Search | Sorted array, search space reduction | Search Insert Position, First Bad Version |
| BFS | Shortest path, level-order traversal | Binary Tree Level Order, Word Ladder |
| DFS | All paths, backtracking, connectivity | Number of Islands, Word Search |
| Dynamic Programming | Overlapping subproblems, optimization | Fibonacci, Coin Change, Longest Subsequence |
| Greedy | Local optimal → global optimal | Jump Game, Activity Selection |
| Backtracking | Combinations, permutations, constraints | N-Queens, Sudoku Solver |
| Union-Find | Connected components, disjoint sets | Number of Islands (alternative), Friend Circles |
Phase 3: Complexity Analysis
Always discuss Big-O before and after optimization:
# Example progression:
"""
Brute Force:
- Time: O(n²) - nested loops
- Space: O(1) - no extra space
- ❌ Too slow for n > 10,000
Optimized (Hash Map):
- Time: O(n) - single pass
- Space: O(n) - hash map storage
- ✅ Acceptable for most cases
Optimized (Two Pointers on sorted):
- Time: O(n log n) - sorting dominates
- Space: O(1) or O(n) - depends on sort algorithm
- ✅ Better space, worse time
"""Phase 4: Code Template
Use consistent structure:
def solution(input_data):
"""Clear docstring explaining the problem."""
# 1. HANDLE EDGE CASES
if not input_data:
return default_value
if len(input_data) == 1:
return special_case_value
# 2. INITIALIZE VARIABLES
result = []
# Helper data structures
hash_map = {}
visited = set()
# 3. MAIN LOGIC
# Choose appropriate pattern:
# - Iteration (for/while)
# - Recursion
# - Two pointers
# - Sliding window
# etc.
for i, item in enumerate(input_data):
# Process each item
pass
# 4. RETURN RESULT
return resultCommon Algorithmic Patterns (Code Templates)
Two Pointers Pattern
Basic Two Pointers (opposite ends)
def two_pointer_opposite(arr):
"""Start from both ends, move towards center."""
left, right = 0, len(arr) - 1
while left < right:
# Process current pair
if meets_condition(arr[left], arr[right]):
return [left, right]
# Move pointers based on condition
if arr[left] + arr[right] < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return NoneFast & Slow Pointers
def fast_slow_pointers(head):
"""Detect cycle or find middle element."""
slow = fast = head
while fast and fast.next:
slow = slow.next # move 1 step
fast = fast.next.next # move 2 steps
if slow == fast: # cycle detected
return True
# slow is now at middle (if no cycle)
return FalseSliding Window Pattern
Fixed-size window
def sliding_window_fixed(arr, k):
"""Find max sum of k consecutive elements."""
if len(arr) < k:
return 0
# Calculate first window
window_sum = sum(arr[:k])
max_sum = window_sum
# Slide the window
for i in range(k, len(arr)):
window_sum = window_sum - arr[i - k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sumVariable-size window
def sliding_window_variable(s):
"""Longest substring without repeating characters."""
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
# Shrink window while duplicate exists
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# Add current character
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_lengthBinary Search Pattern
Basic binary search
def binary_search(arr, target):
"""Find target in sorted array."""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2 # avoid overflow
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # not foundBinary search on answer space
def binary_search_answer(arr, condition):
"""Find minimum/maximum value that satisfies condition."""
left, right = min_possible, max_possible
result = -1
while left <= right:
mid = left + (right - left) // 2
if is_valid(mid):
result = mid # potential answer
right = mid - 1 # try to find better
else:
left = mid + 1
return resultDFS Pattern
Recursive DFS
def dfs_recursive(node, visited):
"""Standard recursive DFS."""
if not node or node in visited:
return
visited.add(node)
# Process current node
process(node)
# Recurse on neighbors
for neighbor in node.neighbors:
dfs_recursive(neighbor, visited)Iterative DFS (with stack)
def dfs_iterative(start):
"""Iterative DFS using stack."""
if not start:
return
stack = [start]
visited = set([start])
while stack:
node = stack.pop()
process(node)
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
stack.append(neighbor)DFS for grid problems
def dfs_grid(grid, row, col, visited):
"""DFS on 2D grid (for islands, etc.)."""
rows, cols = len(grid), len(grid[0])
# Base cases
if (row < 0 or row >= rows or
col < 0 or col >= cols or
(row, col) in visited or
grid[row][col] == 0):
return
visited.add((row, col))
# Explore 4 directions
directions = [(0,1), (1,0), (0,-1), (-1,0)]
for dr, dc in directions:
dfs_grid(grid, row + dr, col + dc, visited)BFS Pattern
Standard BFS
from collections import deque
def bfs(start):
"""Standard BFS using queue."""
if not start:
return
queue = deque([start])
visited = set([start])
while queue:
node = queue.popleft()
process(node)
for neighbor in node.neighbors:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Level-order BFS
def bfs_level_order(root):
"""BFS with level tracking."""
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return resultBFS for shortest path
def bfs_shortest_path(grid, start, end):
"""Find shortest path in grid."""
from collections import deque
queue = deque([(start, 0)]) # (position, distance)
visited = {start}
while queue:
pos, dist = queue.popleft()
if pos == end:
return dist
for neighbor in get_neighbors(grid, pos):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1 # no path foundDynamic Programming Pattern
1D DP
def dp_1d(n):
"""Classic 1D DP (e.g., Fibonacci, Climbing Stairs)."""
# 1. Define dp array
dp = [0] * (n + 1)
# 2. Initialize base cases
dp[0] = 1
dp[1] = 1
# 3. Fill dp array using recurrence relation
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2] # example: Fibonacci
# 4. Return answer
return dp[n]2D DP
def dp_2d(s1, s2):
"""2D DP for string problems (e.g., Edit Distance, LCS)."""
m, n = len(s1), len(s2)
# 1. Create 2D dp table
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 2. Initialize base cases
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
# 3. Fill table
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
# 4. Return answer
return dp[m][n]DP with memoization (top-down)
def dp_memoization(n, memo=None):
"""Top-down DP with memoization."""
if memo is None:
memo = {}
# Base case
if n <= 1:
return n
# Check cache
if n in memo:
return memo[n]
# Compute and cache
memo[n] = dp_memoization(n-1, memo) + dp_memoization(n-2, memo)
return memo[n]Backtracking Pattern
Basic backtracking template
def backtrack(path, choices):
"""Standard backtracking template."""
# Base case: found valid solution
if is_valid_solution(path):
result.append(path[:]) # make a copy
return
# Try each choice
for choice in choices:
# Make choice
path.append(choice)
# Recurse
backtrack(path, get_next_choices(choice))
# Undo choice (backtrack)
path.pop()Backtracking with pruning
def backtrack_with_pruning(path, start, target):
"""Backtracking with early termination."""
# Base case
if sum(path) == target:
result.append(path[:])
return
# Pruning: stop if sum exceeds target
if sum(path) > target:
return
for i in range(start, len(candidates)):
# Skip duplicates
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack_with_pruning(path, i + 1, target)
path.pop()Interview Tips & Best Practices
Time Management (45-minute interview)
0-5 min: Understanding & Clarification
- Restate problem
- Ask questions
- Discuss examples
5-15 min: Approach & Design
- Discuss brute force
- Optimize approach
- Analyze complexity
- Get approval to code
15-35 min: Implementation
- Write clean code
- Think out loud
- Handle edge cases
35-40 min: Testing
- Walk through examples
- Test edge cases
- Fix bugs
40-45 min: Discussion & Optimization
- Discuss trade-offs
- Further optimizations
- Related problemsCommunication Best Practices
✅ DO:
# Think out loud
"I'm thinking of using a hash map here because we need O(1) lookup..."
"Let me first handle the edge case where the array is empty..."
"This gives us O(n) time but uses O(n) space. Let me see if we can optimize..."
# Ask clarifying questions
"Can I assume the input is sorted?"
"Should I optimize for time or space?"
"What should I return if there's no solution?"
# Explain your approach
"I'll use two pointers starting from both ends because the array is sorted..."
"This is a classic sliding window problem, so I'll maintain a window and expand/shrink it..."❌ DON’T:
# Silent coding
# [Just writing code without explanation]
# Immediate coding
"I know this one!" [starts coding immediately]
# Giving up too quickly
"I don't know how to solve this..."
# Ignoring hints
[Interviewer gives hint, you ignore it]Common Mistakes to Avoid
1. Not asking clarifying questions
# ❌ Bad: Assume too much
def solve(arr):
# Assumes arr is not empty, has no duplicates, etc.
return arr[0] + arr[-1]
# ✅ Good: Clarify first
"""
Questions to ask:
- Can arr be empty?
- Can arr have duplicates?
- What's the expected return for edge cases?
"""
def solve(arr):
if not arr:
return 0
# ... handle all cases2. Jumping straight to code
# ❌ Bad: Code immediately without plan
def some_problem(input):
# starts coding complex logic without explaining
pass
# ✅ Good: Explain approach first
"""
Approach:
1. Use hash map to track frequencies - O(n) time
2. Iterate and find max frequency - O(n) time
3. Return the element with max frequency
Total: O(n) time, O(n) space
"""
def some_problem(input):
# Now code with clear plan
pass3. Not considering edge cases
# ❌ Bad: Only handles normal cases
def divide(a, b):
return a / b
# ✅ Good: Handle edge cases
def divide(a, b):
# Edge case: division by zero
if b == 0:
raise ValueError("Cannot divide by zero")
# Edge case: overflow for very large numbers
if abs(a) > sys.maxsize or abs(b) > sys.maxsize:
raise ValueError("Number too large")
return a / b4. Poor variable naming
# ❌ Bad: Unclear names
def f(a, t):
d = {}
for i, x in enumerate(a):
if t - x in d:
return [d[t-x], i]
d[x] = i
# ✅ Good: Clear, descriptive names
def two_sum(nums, target):
value_to_index = {}
for current_index, current_value in enumerate(nums):
complement = target - current_value
if complement in value_to_index:
return [value_to_index[complement], current_index]
value_to_index[current_value] = current_index5. Not testing the solution
# ❌ Bad: "I think it works"
def solution(input):
# ... code ...
return result
# [Doesn't test]
# ✅ Good: Walk through test cases
def solution(input):
# ... code ...
return result
# "Let me test with [2, 7, 11, 15], target=9"
# "Step 1: i=0, num=2, seen={}, complement=7..."
# "Step 2: i=1, num=7, seen={2:0}, complement=2, found! Return [0,1]"Python-Specific Interview Tips
Essential imports to know
# Collections module
from collections import (
Counter, # Frequency counting
defaultdict, # Dict with default values
deque, # Double-ended queue (O(1) append/pop from both ends)
OrderedDict, # Dict that remembers insertion order (Python 3.7+ dicts are ordered)
namedtuple, # Lightweight object
)
# Heap operations
from heapq import (
heappush, # Push onto heap
heappop, # Pop smallest
heapify, # Convert list to heap
nlargest, # N largest elements
nsmallest, # N smallest elements
)
# Binary search
import bisect
bisect_left() # Find insertion point (left)
bisect_right() # Find insertion point (right)
# Itertools for combinations/permutations
from itertools import (
combinations, # C(n,k) - order doesn't matter
permutations, # P(n,k) - order matters
product, # Cartesian product
accumulate, # Cumulative sums
)Pythonic idioms interviewers love
# 1. List comprehensions over loops
# ❌ Bad
result = []
for x in arr:
if x > 0:
result.append(x * 2)
# ✅ Good
result = [x * 2 for x in arr if x > 0]
# 2. enumerate() for index + value
# ❌ Bad
for i in range(len(arr)):
print(i, arr[i])
# ✅ Good
for i, val in enumerate(arr):
print(i, val)
# 3. zip() for parallel iteration
# ❌ Bad
for i in range(min(len(a), len(b))):
print(a[i], b[i])
# ✅ Good
for x, y in zip(a, b):
print(x, y)
# 4. Counter for frequency
# ❌ Bad
freq = {}
for item in arr:
freq[item] = freq.get(item, 0) + 1
# ✅ Good
from collections import Counter
freq = Counter(arr)
# 5. any() / all() for boolean checks
# ❌ Bad
has_positive = False
for x in arr:
if x > 0:
has_positive = True
break
# ✅ Good
has_positive = any(x > 0 for x in arr)
# 6. String joining
# ❌ Bad
result = ""
for s in strings:
result += s
# ✅ Good
result = "".join(strings)
# 7. Swapping values
# ❌ Bad
temp = a
a = b
b = temp
# ✅ Good
a, b = b, a
# 8. Default dict for grouping
# ❌ Bad
groups = {}
for item in items:
key = get_key(item)
if key not in groups:
groups[key] = []
groups[key].append(item)
# ✅ Good
from collections import defaultdict
groups = defaultdict(list)
for item in items:
groups[get_key(item)].append(item)Practice Resources & Study Plan
Practice Platforms
- LeetCode (https://leetcode.com)
- Start with “Top Interview Questions”
- Progress: Easy → Medium → Hard
- Focus on “Most Frequent” tagged problems
- NeetCode 150 (https://neetcode.io)
- Curated list of 150 essential problems
- Organized by pattern
- Video explanations available
- Blind 75 (https://www.teamblind.com/post/New-Year-Gift—Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU)
- Most important 75 questions
- Covers all major patterns
- Frequently asked in FAANG
- AlgoExpert (https://www.algoexpert.io)
- Structured learning path
- 160+ curated questions
- Video explanations
- HackerRank (https://www.hackerrank.com)
- Good for beginners
- Interview preparation kits
- Company-specific practice
Recommended Study Plan
12-Week Interview Preparation Plan
Week 1-2: Arrays & Strings (Foundation)
├─ Two Sum, Best Time to Buy/Sell Stock
├─ Contains Duplicate, Product of Array Except Self
├─ Maximum Subarray, 3Sum
├─ Valid Anagram, Group Anagrams
├─ Valid Parentheses, Longest Substring Without Repeating
└─ Pattern: Hash maps, two pointers, sliding window
Week 3-4: Linked Lists & Stacks/Queues
├─ Reverse Linked List, Merge Two Sorted Lists
├─ Linked List Cycle, Remove Nth Node
├─ Implement Stack/Queue, Min Stack
├─ Valid Parentheses, Daily Temperatures
└─ Pattern: Two pointers, fast/slow pointers, stack
Week 5-6: Trees & Binary Search Trees
├─ Invert Binary Tree, Maximum Depth
├─ Same Tree, Subtree of Another Tree
├─ Validate BST, Lowest Common Ancestor
├─ Binary Tree Level Order Traversal
├─ Serialize/Deserialize Binary Tree
└─ Pattern: DFS, BFS, recursion
Week 7-8: Graphs & Advanced Trees
├─ Number of Islands, Clone Graph
├─ Course Schedule, Pacific Atlantic Water Flow
├─ Longest Consecutive Sequence
├─ Implement Trie, Word Search II
└─ Pattern: DFS, BFS, backtracking, union-find
Week 9-10: Dynamic Programming
├─ Climbing Stairs, House Robber
├─ Coin Change, Longest Increasing Subsequence
├─ Longest Common Subsequence, Word Break
├─ Combination Sum, Unique Paths
└─ Pattern: Memoization, tabulation, state transition
Week 11: Heaps & Advanced Topics
├─ Kth Largest Element, Top K Frequent Elements
├─ Merge K Sorted Lists, Find Median from Data Stream
├─ Binary Search variants
└─ Pattern: Heaps, binary search on answer
Week 12: Mock Interviews & Review
├─ Practice under timed conditions
├─ Review weak areas
├─ System design basics (for senior roles)
└─ Behavioral interview preparationDaily Practice Schedule
Beginner (1-2 problems/day):
├─ 30 min: Review concepts/patterns
├─ 45 min: Solve 1 new problem
└─ 15 min: Review solution, alternative approaches
Intermediate (2-3 problems/day):
├─ 20 min: Warm-up (easy problem)
├─ 60 min: 2 medium problems
└─ 20 min: Review patterns
Advanced (3-4 problems/day):
├─ 15 min: Easy warm-up
├─ 45 min: Medium problem
├─ 45 min: Hard problem
└─ 15 min: Optimize & reviewProblem Difficulty Progression
# Week 1-2: Easy (Build confidence)
easy_problems = [
"Two Sum",
"Best Time to Buy and Sell Stock",
"Valid Anagram",
"Valid Parentheses",
"Merge Two Sorted Lists",
"Maximum Subarray",
]
# Week 3-6: Easy to Medium (Build skills)
easy_medium_problems = [
"3Sum",
"Container With Most Water",
"Longest Substring Without Repeating Characters",
"Group Anagrams",
"Reverse Linked List",
"Binary Tree Level Order Traversal",
]
# Week 7-10: Medium (Interview level)
medium_problems = [
"Coin Change",
"Number of Islands",
"Course Schedule",
"Longest Increasing Subsequence",
"Word Break",
"Combination Sum",
]
# Week 11-12: Medium to Hard (Advanced)
medium_hard_problems = [
"Merge K Sorted Lists",
"Word Search II",
"Serialize and Deserialize Binary Tree",
"Edit Distance",
"Regular Expression Matching",
"Median of Two Sorted Arrays",
]Company-Specific Focus
FAANG Companies:
├─ Google: Focus on system design, algorithms
│ └─ Heavy on graphs, trees, DP
├─ Amazon: Focus on OOP, leadership principles
│ └─ Medium problems, practical scenarios
├─ Facebook/Meta: Focus on data structures
│ └─ Arrays, strings, hash tables, BFS/DFS
├─ Apple: Focus on efficiency, clean code
│ └─ Low-level optimization, edge cases
└─ Netflix: Focus on system design
└─ Scalability, distributed systems
Startups:
├─ Practical coding ability
├─ Less focus on hard algorithms
└─ More focus on clean code, testing
Finance/Trading:
├─ Mathematical problems
├─ Optimization problems
└─ Low-latency considerationsKey Takeaways & Final Tips
The 80/20 Rule for Interview Prep
Focus on these 20% of topics that cover 80% of interview questions:
1. Arrays & Hash Tables (30%)
2. Trees & Graphs (25%)
3. Dynamic Programming (15%)
4. Strings (10%)
5. Linked Lists (10%)
6. Stacks & Queues (5%)
7. Heaps & Sorting (5%)Problem-Solving Mantras
"""
1. "Understand before solving"
→ Spend time understanding the problem deeply
2. "Simple first, optimize later"
→ Brute force shows you can solve it
3. "Draw it out"
→ Visualize with examples, especially for trees/graphs
4. "Think out loud"
→ Communication is 50% of the interview
5. "Test with edge cases"
→ Empty, single element, duplicates, negatives
6. "Complexity matters"
→ Always discuss time/space complexity
7. "Pythonic is better"
→ Use built-ins, comprehensions, idioms
8. "Practice under pressure"
→ Timed mock interviews are essential
"""Interview Day Checklist
Before Interview:
□ Review common patterns (2 hours before)
□ Solve 1-2 warm-up problems
□ Have pen & paper ready
□ Test your video/audio setup
□ Have water nearby
During Interview:
□ Take notes while problem is explained
□ Repeat the problem in your own words
□ Ask clarifying questions
□ Discuss approach before coding
□ Think out loud while coding
□ Test your solution
□ Discuss optimizations
After Interview:
□ Write down questions you were asked
□ Review your approach
□ Identify areas for improvement
□ Practice similar problemsRed Flags to Avoid
❌ Silent coding without explanation
❌ Jumping to code without clarifying
❌ Ignoring edge cases
❌ Not testing the solution
❌ Giving up when stuck
❌ Arguing with the interviewer
❌ Bad-mouthing previous employers
❌ Not asking any questions at the endGreen Flags to Demonstrate
✅ Clear communication
✅ Structured problem-solving approach
✅ Considering multiple solutions
✅ Analyzing time/space complexity
✅ Writing clean, readable code
✅ Testing thoroughly
✅ Being receptive to hints
✅ Asking thoughtful questionsQuick Reference: Python Interview Snippets
Common Operations Complexity
# List Operations
arr.append(x) # O(1)
arr.pop() # O(1)
arr.pop(0) # O(n)
arr.insert(0, x) # O(n)
x in arr # O(n)
arr.sort() # O(n log n)
# Dictionary Operations
dict[key] # O(1) average
key in dict # O(1) average
dict.get(key) # O(1) average
dict.items() # O(n)
# Set Operations
set.add(x) # O(1) average
x in set # O(1) average
set1 & set2 # O(min(len(set1), len(set2)))
set1 | set2 # O(len(set1) + len(set2))
# String Operations
s.find(sub) # O(n*m) worst case
s.replace(old, new) # O(n)
s.split() # O(n)
''.join(list) # O(n)
# Heapq Operations
heapq.heappush() # O(log n)
heapq.heappop() # O(log n)
heapq.heapify() # O(n)Essential Code Snippets
# 1. Frequency counter
from collections import Counter
freq = Counter(arr)
most_common = freq.most_common(k)
# 2. Default dictionary
from collections import defaultdict
graph = defaultdict(list)
graph[node].append(neighbor)
# 3. Deque for BFS
from collections import deque
queue = deque([start])
node = queue.popleft()
queue.append(neighbor)
# 4. Min/Max heap
import heapq
min_heap = []
heapq.heappush(min_heap, value)
smallest = heapq.heappop(min_heap)
# For max heap, negate values:
max_heap = []
heapq.heappush(max_heap, -value)
largest = -heapq.heappop(max_heap)
# 5. Binary search
import bisect
idx = bisect.bisect_left(sorted_arr, target)
# 6. Sorting with custom key
arr.sort(key=lambda x: (x[0], -x[1])) # sort by first asc, second desc
# 7. Multiple assignment
a, b = b, a # swap
left, right = 0, len(arr) - 1
# 8. Slice operations
arr[:] # copy
arr[::-1] # reverse
arr[::2] # every other element
arr[i:j] # substring from i to j-1
# 9. Comprehensions
squares = [x**2 for x in range(10) if x % 2 == 0]
dict_comp = {k: v for k, v in pairs if v > 0}
set_comp = {x for x in arr if x > 0}
# 10. Infinity values
float('inf') # positive infinity
float('-inf') # negative infinityDiscover more from Altgr Blog
Subscribe to get the latest posts sent to your email.
