Python Algorithms

← Back to all decks

37 cards — 🟢 6 easy | 🟡 11 medium | 🔴 3 hard

🟢 Easy (6)

1. Find all pairs in an array that sum to k

Show answer

Use a set to track complements in O(n) time.

def two_sum_pairs(arr, k):
seen = set()
pairs = []
for x in arr:
if k - x in seen:
pairs.append((k - x, x))
seen.add(x)
return pairs

Alternative: sort + two-pointer approach runs O(n log n) but uses O(1) extra space. The hash-set approach is preferred for interviews unless space is constrained.

2. Find the first non-repeating character in a string

Show answer

Use collections.Counter to count frequencies, then iterate to find the first with count 1.

from collections import Counter
def first_unique(s):
counts = Counter(s)
for ch in s:
if counts[ch] == 1:
return ch
return None

Time: O(n), Space: O(k) where k is alphabet size. Two-pass approach — first pass counts, second finds.

3. Reverse words in a sentence

Show answer

Split, reverse, rejoin.

def reverse_words(s):
return ' '.join(s.split()[::-1])

split() without args handles multiple spaces. For in-place reversal (interview follow-up): reverse entire string, then reverse each word. Python strings are immutable, so true in-place requires a list of chars.

4. Implement binary search

Show answer

Halve the search space each iteration.

def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1

O(log n) time, O(1) space. Use bisect module in production: bisect.bisect_left(arr, target).

5. Merge two sorted arrays

Show answer

Two-pointer merge in O(n + m) time.

def merge_sorted(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:])
result.extend(b[j:])
return result

This is the merge step of merge sort. O(n + m) time and space. In Python, heapq.merge(a, b) does this lazily.

6. Detect palindrome

Show answer

Compare string to its reverse, or use two pointers.

def is_palindrome(s):
return s == s[::-1]

# Two-pointer (better for follow-ups):
def is_palindrome_tp(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1; right -= 1
return True

For alphanumeric-only: filter with isalnum() and lower() first. Extends to 'valid palindrome II' (remove at most one char).

🟡 Medium (11)

1. Product array — compute products of all elements except self

Show answer

Build prefix and suffix product arrays, then multiply.

def product_except_self(nums):
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result

O(n) time, O(1) extra space (output array not counted). No division needed — handles zeros correctly.

2. Find the middle element of a linked list in one pass

Show answer

Use slow/fast pointer technique (Floyd's tortoise and hare).

def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow

When fast reaches the end, slow is at the middle. O(n) time, O(1) space. For even-length lists, this returns the second middle node.

3. Detect a cycle in a linked list

Show answer

Floyd's cycle detection: use slow (1 step) and fast (2 step) pointers.

def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False

To find the cycle start: when slow == fast, reset one pointer to head and advance both by 1 — they meet at the cycle entry. O(n) time, O(1) space.

4. Implement DFS and BFS for a graph

Show answer

DFS uses a stack (or recursion), BFS uses a queue.

from collections import deque

def bfs(graph, start):
visited, queue = set(), deque([start])
visited.add(start)
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited

def dfs(graph, start, visited=None):
if visited is None: visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited

BFS finds shortest path in unweighted graphs. DFS is better for detecting cycles and topological sorting.

5. Check anagram removal count for two strings

Show answer

Count character frequencies and sum absolute differences.

from collections import Counter
def anagram_removals(s1, s2):
c1, c2 = Counter(s1), Counter(s2)
return sum((c1 - c2).values()) + sum((c2 - c1).values())

This gives the total characters to remove from both strings to make them anagrams. Counter subtraction only keeps positive counts, so we sum both directions. O(n + m) time.

6. Determine if a zero-sum subarray exists

Show answer

Track prefix sums — if a prefix sum repeats, a zero-sum subarray exists.

def has_zero_sum_subarray(arr):
prefix_sums = set([0])
running = 0
for x in arr:
running += x
if running in prefix_sums:
return True
prefix_sums.add(running)
return False

Key insight: if prefix_sum[j] == prefix_sum[i], then sum(arr[i+1:j+1]) == 0. Include 0 in initial set to catch subarrays starting at index 0. O(n) time and space.

7. Generate the largest number from a list of integers

Show answer

Custom sort: compare concatenated strings.

from functools import cmp_to_key
def largest_number(nums):
strs = list(map(str, nums))
strs.sort(key=cmp_to_key(lambda a, b: (1 if a+b < b+a else -1 if a+b > b+a else 0)))
result = ''.join(strs)
return '0' if result[0] == '0' else result

Compare '9'+'34' vs '34'+'9' -> '934' > '349' so 9 comes first. Edge case: all zeros -> return '0'. O(n log n) time.

8. Calculate the stock span problem

Show answer

Use a monotonic decreasing stack to find previous greater elements.

def stock_span(prices):
spans = []
stack = [] # (price, index)
for i, price in enumerate(prices):
while stack and stack[-1][0] <= price:
stack.pop()
span = i + 1 if not stack else i - stack[-1][1]
spans.append(span)
stack.append((price, i))
return spans

The span for day i is the number of consecutive days before it (including itself) where price was <= price[i]. Classic monotonic stack pattern. O(n) amortized.

9. Implement a linked list with insert, find, delete

Show answer

class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt

class LinkedList:
def __init__(self):
self.head = None

def insert(self, val):
self.head = Node(val, self.head)

def find(self, val):
curr = self.head
while curr:
if curr.val == val: return curr
curr = curr.next
return None

def delete(self, val):
if not self.head: return
if self.head.val == val:
self.head = self.head.next; return
curr = self.head
while curr.next:
if curr.next.val == val:
curr.next = curr.next.next; return
curr = curr.next

Insert: O(1) at head. Find/Delete: O(n). Use a sentinel/dummy head node to simplify edge cases.

10. Generate all permutations of a string

Show answer

Use backtracking or itertools.permutations.

def permutations(s):
if len(s) <= 1:
return [s]
result = []
for i, ch in enumerate(s):
rest = s[:i] + s[i+1:]
for perm in permutations(rest):
result.append(ch + perm)
return result

Or simply: from itertools import permutations as p; list(p('abc'))

Time: O(n! * n). For deduplication with repeated chars, use a set or sort + skip approach.

11. Two-pointer technique for sorted array problems

Show answer

Two pointers converging from both ends of a sorted array.

def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
s = arr[left] + arr[right]
if s == target:
return (left, right)
elif s < target:
left += 1
else:
right -= 1
return None

O(n) time, O(1) space. Works because the array is sorted. Also used for: container with most water, remove duplicates, three-sum (fix one + two-pointer on rest).

🔴 Hard (3)

1. Implement QuickSort

Show answer

Divide-and-conquer: pick a pivot, partition, recurse.

def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + mid + quicksort(right)

Average O(n log n), worst O(n^2) with bad pivot choice. In-place variant uses Lomuto or Hoare partitioning. Python's built-in sorted() uses Timsort (O(n log n) guaranteed).

2. Implement a Trie (prefix tree)

Show answer

A tree where each node represents a character prefix.

class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True

def search(self, word):
node = self._find(word)
return node is not None and node.is_end

def starts_with(self, prefix):
return self._find(prefix) is not None

Used for autocomplete, spell-check, IP routing. O(m) per operation where m is word length.

3. Sliding window maximum

Show answer

Use a monotonic deque to track max in O(n).

from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices of useful elements
result = []
for i, num in enumerate(nums):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[dq[-1]] <= num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result

The deque stores indices in decreasing order of values. Front is always the max for the current window. O(n) total.