Python Algorithms¶
20 cards — 🟢 2 easy | 🟡 12 medium | 🔴 6 hard
🟢 Easy (2)¶
1. How do hash maps provide O(1) lookup and when should you use them in interviews?
Show answer
Hash maps (Python dicts) use a hash function to map keys to array indices, giving average O(1) get/set/delete. Use them whenever you need to track seen elements, count frequencies, or replace a nested loop with a lookup.Classic pattern: "two-sum" -- build a dict of {value: index} as you iterate, checking if target-current exists.
Code: `seen = {}; for i, n in enumerate(arr): if target-n in seen: return [seen[target-n], i]; seen[n] = i`
2. How do you reverse words in a sentence?
Show answer
Split by whitespace, reverse the list, and join.`def reverse_words(s):
return ' '.join(s.split()[::-1])`
Example: "hello world foo" -> "foo world hello". The split() without arguments handles multiple spaces. For in-place reversal (C-style), you would reverse the entire string, then reverse each word individually. Time: O(n), Space: O(n) for the new string.
🟡 Medium (12)¶
1. Explain the two-pointer technique and give an example use case.
Show answer
The two-pointer technique uses two indices that move toward each other (or in the same direction) to solve problems in O(n) time instead of O(n^2). Classic example: finding all pairs in a sorted array that sum to k.Sort the array, set left=0 and right=len-1. If arr[left]+arr[right]==k, record the pair. If the sum is too small, increment left; if too large, decrement right.
Code: `left, right = 0, len(arr)-1; while left < right: s = arr[left]+arr[right]; ...`
2. What is the sliding window technique and when do you use it?
Show answer
Sliding window maintains a window (subarray/substring) that expands or contracts as you iterate. It solves problems like "longest substring without repeating characters" or "maximum sum subarray of size k" in O(n).Two types: fixed-size (move both ends together) and variable-size (expand right, shrink left when condition breaks).
Example: `start=0; for end in range(len(arr)): window_sum += arr[end]; while window_sum > target: window_sum -= arr[start]; start += 1`
3. Find all pairs in an array that sum to k.
Show answer
Sort the array and use two pointers, or use a hash set for O(n) average time.Hash set approach:
`def pair_sum(arr, k):
seen = set()
pairs = []
for x in arr:
if k - x in seen:
pairs.append((k - x, x))
seen.add(x)
return pairs`
Time: O(n), Space: O(n). The two-pointer approach on a sorted array uses O(1) extra space but O(n log n) for sorting.
4. Find the first non-repeating character in a string.
Show answer
Use a Counter (or dict) to count character frequencies, then iterate the string again to find the first char with count 1.Code:
`from collections import Counter
def first_unique(s):
counts = Counter(s)
for c in s:
if counts[c] == 1:
return c
return None`
Time: O(n), Space: O(k) where k is the alphabet size. This is optimal since you must examine every character at least once.
5. Compute the product of all elements except self (without division).
Show answer
Build two arrays: prefix products (left to right) and suffix products (right to left). The answer at index i is prefix[i] * suffix[i].Code:
`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`
Time: O(n), Space: O(1) extra (output array not counted).
6. How do you find the middle element of a linked list in one pass?
Show answer
Use the slow/fast pointer technique. Initialize two pointers at the head. Move slow one step at a time and fast two steps. When fast reaches the end, slow is at the middle.Code:
`def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow`
Time: O(n), Space: O(1). This is the classic "tortoise and hare" pattern applied to finding the midpoint.
7. How do you detect a cycle in a linked list?
Show answer
Use Floyd's cycle detection (tortoise and hare). Two pointers start at head: slow moves 1 step, fast moves 2 steps. If they meet, there is a cycle. If fast reaches None, there is no cycle.Code:
`def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False`
Time: O(n), Space: O(1). To find the cycle start, reset one pointer to head and advance both one step until they meet.
8. Implement a linked list with insert, find, and delete operations.
Show answer
Define a Node class and a LinkedList class:`class Node:
def __init__(self, val): self.val = val; self.next = None
class LinkedList:
def __init__(self): self.head = None
def insert(self, val):
node = Node(val); node.next = self.head; self.head = node
def find(self, val):
cur = self.head
while cur:
if cur.val == val: return cur
cur = cur.next
return None
def delete(self, val):
if self.head and self.head.val == val: self.head = self.head.next; return
cur = self.head
while cur.next:
if cur.next.val == val: cur.next = cur.next.next; return
cur = cur.next`
Insert: O(1), Find/Delete: O(n).
9. Check how many characters need to be removed from two strings to make them anagrams.
Show answer
Count character frequencies for each string and sum the absolute differences.`from collections import Counter
def min_removals_anagram(s1, s2):
c1, c2 = Counter(s1), Counter(s2)
all_chars = set(c1.keys()) | set(c2.keys())
return sum(abs(c1.get(ch, 0) - c2.get(ch, 0)) for ch in all_chars)`
Time: O(n + m), Space: O(k) where k is alphabet size. The total removals equal characters that don't match between the two frequency maps.
10. Determine if a zero-sum subarray exists.
Show answer
Use a running prefix sum and a set. If the prefix sum was seen before, the subarray between those two indices sums to zero. Also check if prefix sum equals zero (subarray from start).`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`
Time: O(n), Space: O(n). This is a classic prefix-sum + hash-set pattern.
11. Calculate the stock span problem using a stack.
Show answer
The stock span for day i is the number of consecutive preceding days where the price was <= price[i]. Use a stack of indices.`def stock_span(prices):
spans = []
stack = [] # stack of indices
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
spans.append(i + 1 if not stack else i - stack[-1])
stack.append(i)
return spans`
Time: O(n) amortized -- each index is pushed/popped at most once. This is a classic monotonic stack pattern also used for next-greater-element problems.
12. Solve the valid parentheses problem using a stack.
Show answer
Push opening brackets onto a stack. For each closing bracket, check if the stack top matches. If the stack is empty at the end, the string is valid.`def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
elif ch in pairs:
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
return len(stack) == 0`
Time: O(n), Space: O(n). This is one of the most common stack interview questions.
🔴 Hard (6)¶
1. Implement DFS and BFS for a graph.
Show answer
BFS uses a queue (deque) and visits level by level. DFS uses a stack (or recursion) and goes deep first.BFS:
`from collections import deque
def bfs(graph, start):
visited, queue = {start}, deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)`
DFS (iterative):
`def dfs(graph, start):
visited, stack = set(), [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node])`
BFS finds shortest path in unweighted graphs; DFS is better for exhaustive search / topological sort.
2. Implement QuickSort and explain when to use it vs MergeSort.
Show answer
QuickSort picks a pivot, partitions elements around it, and recurses on each half.`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 pivots. In-place variant uses O(log n) space.
Use QuickSort when average performance matters and memory is limited. Use MergeSort when you need stable sort or guaranteed O(n log n) worst case (e.g., sorting linked lists, external sort).
3. Implement MergeSort and explain its advantages.
Show answer
MergeSort divides the array in half, recursively sorts each half, then merges them.`def mergesort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return merge(left, right)
def merge(l, r):
result = []
i = j = 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: result.append(l[i]); i += 1
else: result.append(r[j]); j += 1
result.extend(l[i:]); result.extend(r[j:])
return result`
Always O(n log n). Stable sort. Uses O(n) extra space. Preferred for linked lists and external sorting.
4. Implement a Trie (prefix tree).
Show answer
A trie stores strings character by character in a tree. Each node has a dict of children and an end-of-word flag.`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.root
for ch in word:
if ch not in node.children: return False
node = node.children[ch]
return node.is_end
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children: return False
node = node.children[ch]
return True`
Used for autocomplete, spell checking, and IP routing tables.
5. Generate the largest number from a list of integers.
Show answer
Convert integers to strings and sort using a custom comparator: for two numbers a and b, compare a+b vs b+a as strings.`from functools import cmp_to_key
def largest_number(nums):
nums_str = list(map(str, nums))
nums_str.sort(key=cmp_to_key(lambda a, b: -1 if a+b > b+a else 1))
result = ''.join(nums_str)
return '0' if result[0] == '0' else result`
Example: [3, 30, 34, 5, 9] -> "9534330". Time: O(n log n) for the sort. The key insight is that string concatenation comparison gives the correct ordering.
6. Generate all permutations of a string.
Show answer
Use recursion with backtracking. Fix one character at each position and recurse on the rest.`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 use itertools: `from itertools import permutations; list(permutations("abc"))`.
Time: O(n! * n), Space: O(n!) for storing results. For strings with duplicate characters, use a set or sort-based dedup to avoid duplicate permutations.