DSA interview questions for freshers
The basics asked in campus placements: the core structures, how they differ, and short array and string problems.
What is a data structure, and what is an algorithm?
A data structure organizes data so the operations you need are cheap: an array reads by index in O(1), a hash table finds a key in O(1) on average. An algorithm is a finite sequence of steps from input to output, such as binary search. You choose them together: finding duplicates pair by pair is O(n²), with a set it is O(n).
What is the difference between linear and non-linear data structures?
In a linear structure the elements form a sequence, each with at most one predecessor and one successor: arrays, linked lists, stacks, queues. In a non-linear one an element connects to several others: trees, heaps, graphs, tries. Linear ones are walked in one pass; non-linear ones need DFS or BFS.
What is the difference between an array and a linked list?
An array stores elements in one contiguous block, so a[i] is O(1) but inserting in the middle is O(n). A linked list stores each element in a node pointing to the next, so inserting after a node you hold is O(1), but reaching the i-th element is O(n). Arrays win most benchmarks because of CPU caching. See a linked list step by step.
What is the difference between a stack and a queue?
A stack is LIFO (last in, first out): push and pop at the same end. A queue is FIFO (first in, first out): add at the back, remove from the front. In Python use a list as a stack and deque as a queue, since list.pop(0) is O(n) (see the deque docs).
from collections import deque
stack = []
for x in [1, 2, 3]:
stack.append(x)
print("stack pops:", stack.pop(), stack.pop())
queue = deque()
for x in [1, 2, 3]:
queue.append(x)
print("queue pops:", queue.popleft(), queue.popleft())What is recursion, and what is a base case?
Recursion is a function calling itself on a smaller input. The base case is an input small enough to answer directly; without one, the calls never stop.
import sys
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # smaller input
print(factorial(5))
print(sys.getrecursionlimit())Each pending call holds a stack frame, so recursion uses O(depth) memory; CPython raises RecursionError at a depth of about 1000 by default. See the call stack grow and unwind.
What does this print: a recursive function that adds n down to 0?
def f(n):
if n == 0:
return 0
return n + f(n - 1)
print(f(4))Predict the output
f(4) expands to 4 + 3 + 2 + 1 + f(0), and the base case returns 0, so it prints 10. Reading it as factorial (24) is the common slip; the operator is +. It takes O(n) time and O(n) stack.
What does this print: a string sliced with step -1?
s = "coddy"
print(s[::-1], s)Predict the output
A slice with step -1 builds a new, reversed string, yddoc. Strings are immutable, so s is still coddy.
Follow-up: reverse it by hand? Copy the string into a list and swap from both ends with two pointers.
How do you check whether a string is a palindrome?
Compare characters from both ends moving inward; any mismatch means it is not a palindrome. That is O(n) time and O(1) space; s == s[::-1] is also O(n) but builds a reversed copy.
def is_palindrome(s):
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
for word in ["racecar", "level", "coddy", ""]:
print(repr(word), is_palindrome(word))Follow-up: ignore case and punctuation? Skip characters that fail isalnum() inside the same loop and compare lowercased characters, without building a cleaned copy.
How do you find the second largest element in an array in one pass?
Keep first and second. A value above first pushes the old first down to second; a value above second that is not equal to first becomes second. One pass, O(1) space; sorting costs O(n log n).
def second_largest(nums):
first = second = None
for x in nums:
if first is None or x > first:
first, second = x, first
elif x != first and (second is None or x > second):
second = x
return second
print(second_largest([12, 35, 1, 10, 34, 1]))
print(second_largest([10, 10, 10]))Raise duplicates yourself: [10, 10, 10] has no second largest, so this returns None, not 10.
How do you find the missing number in an array that holds 0 to n with one number missing?
Subtract the array's sum from n * (n + 1) // 2, the sum of 0 to n. O(n) time, O(1) space. XORing every index and every value gives the same answer and avoids overflow in languages with fixed-size integers.
def missing_sum(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
def missing_xor(nums):
result = len(nums)
for i, x in enumerate(nums):
result ^= i ^ x
return result
nums = [3, 0, 1, 5, 2]
print(missing_sum(nums), missing_xor(nums))Both print 4.
Which data structure would you use for undo, a printer queue, autocomplete and a leaderboard?
Match the structure to the operation the feature does most: two stacks for undo and redo, a queue for a printer queue, a trie for autocomplete, a heap for a leaderboard's top k, a hash map for a phone book, and a graph for routes on a map. Say the operation out loud: "we mostly look up by key, so a hash map".
How should you approach a DSA problem in a coding interview?
Clarify, work an example, state the brute force, remove its bottleneck, then code and test:
- Ask about input size, duplicates, negatives and empty input.
- Work a small example by hand.
- State the brute force and its complexity.
- Remove the bottleneck: a hash map for lookups, two pointers on sorted data, a heap for top k.
- Code it and trace your example.
Around 10^5 elements means O(n log n) or better.
Time and space complexity interview questions
Big O, the cost of loops and recursion, and the complexity of common Python operations.
What is Big O notation?
Big O describes how running time or memory grows with input size n, ignoring constants and smaller terms: 3n² + 5n + 2 is O(n²). From fastest to slowest: O(1) hash lookup, O(log n) binary search, O(n) one pass, O(n log n) merge sort, O(n²) every pair, O(2^n) all subsets, O(n!) all permutations. Interviews usually mean the tight worst case.
What does this print: a loop that halves n until it reaches 1?
n = 64
steps = 0
while n > 1:
n //= 2
steps += 1
print(steps)Predict the output
Each pass halves n: 64, 32, 16, 8, 4, 2, 1 is 6 halvings, log₂(64). Any loop that divides the remaining work by a constant runs O(log n) times; a million items takes only about 20 steps.
What does this print, and what is its complexity: an inner loop that starts at i?
count = 0
n = 4
for i in range(n):
for j in range(i, n):
count += 1
print(count)Predict the output
The inner loop runs 4, 3, 2, then 1 times, so it prints 10. In general that is n(n + 1)/2 iterations, still O(n²): halving the work changes the constant, not the growth rate.
What is space complexity, and does recursion use extra space?
Space complexity is the extra memory an algorithm needs as n grows, usually not counting the input. Recursion does use space: each pending call keeps a stack frame, so depth d costs O(d). Binary search is O(1) space as a loop and O(log n) recursive.
Follow-up: can you do it in O(1) space? Usually by working in place with pointers.
What does amortized O(1) mean, for example when appending to a dynamic array?
Amortized O(1) means one operation can be slow, but n operations cost O(n) in total. A dynamic array copies everything into a bigger block when full, an O(n) step, but capacity grows by a constant factor (about 1.125× in CPython, 1.5× in OpenJDK's ArrayList), so the copies add up to O(n). The Java ArrayList docs promise only the amortized cost, not the factor.
import sys
items = []
last = sys.getsizeof(items)
for i in range(40):
items.append(i)
size = sys.getsizeof(items)
if size != last:
print(f"len {len(items):>2}: {size} bytes")
last = sizeOnly 6 of the 40 appends changed the allocation.
What is the time complexity of common Python list, dict and set operations?
These CPython average costs come up most:
- O(1):
lst[i],append(amortized),lst.pop(),popleft(), set and dict lookup. - O(log n):
heappush,heappop. - O(n):
lst.pop(0),insert(0, x),x in lst,lst[:]; a k-item slice is O(k). - O(n log n):
sorted(lst).
The hidden O(n²) is if x in some_list inside a loop; use a set.
How do you find the time complexity of a recursive algorithm like merge sort?
Write the recurrence and solve it. Merge sort is T(n) = 2T(n/2) + O(n): log₂ n levels of O(n) merging, so O(n log n). Others to know: binary search T(n/2) + O(1) is O(log n); recursive sum T(n-1) + O(1) is O(n); all subsets 2T(n-1) + O(1) is O(2^n); naive Fibonacci T(n-1) + T(n-2) is O(1.618^n), quoted as O(2^n). The master theorem covers T(n) = aT(n/b) + f(n), not T(n-1) ones.
Array and string interview questions
Two pointers, sliding windows, prefix sums and the in-place tricks behind most array and string questions.
What is the two pointer technique, and when do you use it?
Two pointers walks an array with two indexes, from both ends inward or both from the left at different speeds, turning many O(n²) pair searches into O(n). Pair sums need a sorted array.
def pair_with_sum(nums, target):
# nums is sorted
i, j = 0, len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == target:
return nums[i], nums[j]
if s < target:
i += 1 # need a bigger sum
else:
j -= 1 # need a smaller sum
return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))If nums[i] + nums[j] is too small, nums[i] cannot pair with anything left of j, so i can move.
What is the sliding window technique?
A sliding window keeps a range [left, right] and updates the answer as it moves instead of recomputing. A fixed window adds the entering element and drops the leaving one; a variable window grows right and shrinks left while a condition is broken. O(n).
def max_sum_of_k(nums, k):
window = sum(nums[:k])
best = window
for right in range(k, len(nums)):
window += nums[right] - nums[right - k]
best = max(best, window)
return best
print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3))With negative numbers, "sum at least k" breaks a shrinking window; use prefix sums.
How does Kadane's algorithm find the maximum subarray sum?
Track the best sum of a subarray ending at the current index: extend the previous one or start fresh here, whichever is larger. The answer is the largest of those. O(n) time, O(1) space.
def max_subarray(nums):
best = current = nums[0]
for x in nums[1:]:
current = max(x, current + x)
best = max(best, current)
return best
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))Do not start best at 0: with all negatives the answer is -1.
What is a prefix sum, and what problems does it solve?
prefix[i] holds the sum of the first i elements, so after O(n) preprocessing any range sum [l, r] is prefix[r + 1] - prefix[l] in O(1). It pays off for many range queries on one array.
from itertools import accumulate
nums = [3, 1, 4, 1, 5, 9, 2]
prefix = [0] + list(accumulate(nums))
def range_sum(l, r):
return prefix[r + 1] - prefix[l]
print(prefix)
print(range_sum(2, 4)) # 4 + 1 + 5With a hash map of earlier prefix sums it also counts subarrays summing to k.
How do you move all zeros to the end of an array while keeping the order of the other elements?
Keep a write index: swap every non-zero value to it, then move it forward. O(n) time, O(1) extra space, and the non-zero values keep their order.
def move_zeroes(nums):
write = 0
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
return nums
print(move_zeroes([0, 1, 0, 3, 12]))The same read and write pointers remove duplicates from a sorted array in place.
What does this print: a grid built with [[0] * 3] * 3?
grid = [[0] * 3] * 3
grid[0][0] = 1
print(grid)Predict the output
[[0] * 3] * 3 holds three references to the same inner list, so changing one row changes all three. It breaks grid and DP code that looks right. Build each row separately:
grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)[0] * 3 alone is fine, because integers are immutable.
How do you rotate an array to the right by k steps in place?
Reverse the whole array, then the first k elements, then the rest: O(n) time, O(1) extra space. Take k % n first, since rotating by n changes nothing.
def reverse(a, i, j):
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
def rotate(a, k):
n = len(a)
k %= n
reverse(a, 0, n - 1)
reverse(a, 0, k - 1)
reverse(a, k, n - 1)
return a
print(rotate([1, 2, 3, 4, 5, 6, 7], 3))a[-k:] + a[:-k] is the Python one-liner, but it allocates a new list, O(n) extra space.
How do you sort an array of 0s, 1s and 2s in one pass?
Use the Dutch national flag algorithm: low is the next slot for a 0, mid the current element, high the next slot for a 2. Swap 0s to low and 2s to high. One pass, O(1) space.
def sort_colors(nums):
low, mid, high = 0, 0, 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 -= 1 # mid stays: the swapped-in value is unchecked
return nums
print(sort_colors([2, 0, 2, 1, 1, 0]))The usual bug is advancing mid after swapping with high, before checking the value swapped in.
How do you compute the product of all elements except self without division?
Make two passes: the left pass stores the product of everything left of each index, the right pass multiplies in everything to its right from one running variable. O(n) time, O(1) extra space besides the output.
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right
right *= nums[i]
return out
print(product_except_self([1, 2, 3, 4]))
print(product_except_self([2, 0, 5]))Division would break on zeros.
How do you find the longest common prefix of a list of strings?
Compare the strings column by column and stop at the first position where a string ends or a character differs. That is O(S) for S total characters.
def longest_common_prefix(words):
if not words:
return ""
for i, ch in enumerate(words[0]):
for w in words[1:]:
if i == len(w) or w[i] != ch:
return words[0][:i]
return words[0]
print(longest_common_prefix(["flower", "flow", "flight"]))
print(repr(longest_common_prefix(["dog", "car"])))When the follow-up is many prefix queries against the same words, use a trie.
Linked list, stack and queue interview questions
Linked list pointer work, stacks and queues, heaps as priority queues, and the LRU cache.
How do you reverse a singly linked list?
Walk with prev and curr: save curr.next, point curr.next at prev, then move both forward. When curr is None, prev is the new head. O(n) time, O(1) space.
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def build(values):
head = None
for v in reversed(values):
head = ListNode(v, head)
return head
def to_list(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
return prev
print(to_list(reverse(build([1, 2, 3, 4, 5]))))The recursive version is shorter but uses O(n) stack, which matters on long lists.
How do you detect a cycle in a linked list?
Use Floyd's tortoise and hare: slow moves one node, fast two. With a cycle they meet; if fast reaches None, there is none. O(n) time, O(1) space.
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
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
nodes = [ListNode(i) for i in range(5)]
for a, b in zip(nodes, nodes[1:]):
a.next = b
print(has_cycle(nodes[0]))
nodes[4].next = nodes[2] # the tail points back into the list
print(has_cycle(nodes[0]))Follow-up: where does the cycle start? After they meet, reset one pointer to the head and step both by one; they meet at the cycle's first node.
How do you find the middle of a linked list in one pass?
Move slow one step and fast two; when fast reaches the end, slow is at the middle. For an even length it returns the second middle node.
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.val
five = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
six = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
print(middle(five), middle(six))It is the first step of merge sort on a linked list.
What is the difference between singly, doubly and circular linked lists?
A singly linked node points to the next node; a doubly linked node also points to the previous one; in a circular list the last node points back to the first. Only a doubly linked list can delete a node you hold in O(1), which is why LRU caches use one. A circular traversal must stop when it returns to the start.
How do you check if a string of brackets is balanced?
Push every opening bracket; each closing bracket must match the popped top; at the end the stack must be empty. O(n) time and space.
def is_valid(s):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in s:
if ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch)
return not stack
for s in ["()[]{}", "([)]", "{[]}", "(("]:
print(s, is_valid(s))Test a closer on an empty stack, a mismatch (([)]) and leftover openers ((().
What does this print: a list used as a stack, one pop then one append?
stack = []
for x in [1, 2, 3]:
stack.append(x)
stack.pop()
stack.append(4)
print(stack)Predict the output
After the loop the stack is [1, 2, 3]. pop() removes the top, 3, then 4 goes on top: [1, 2, 4]. Picking [2, 3, 4] means you treated it as a queue.
What does this print: a deque after append, popleft and appendleft?
from collections import deque
q = deque([1, 2, 3])
q.append(4)
q.popleft()
q.appendleft(0)
print(list(q))Predict the output
append(4) gives [1, 2, 3, 4], popleft() removes 1, and appendleft(0) puts 0 in front: [0, 2, 3, 4]. Both ends are O(1), which is why BFS uses deque.popleft() and not list.pop(0), an O(n) shift.
How do you implement a queue using two stacks?
Push onto an inbox stack and pop from an outbox stack; when the outbox is empty, move everything from the inbox onto it, reversing the order. Each item moves at most twice, so operations are amortized O(1).
class Queue:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, x):
self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
q = Queue()
for x in [1, 2, 3]:
q.push(x)
print(q.pop())
q.push(4)
print(q.pop(), q.pop(), q.pop())Moving items back to the inbox after every pop is the common wrong version, O(n) per operation.
How do you design a stack that returns its minimum in O(1)?
Push each value together with the minimum of it and everything below it. The top then always holds the current minimum, and popping restores the previous one. Every operation is O(1).
class MinStack:
def __init__(self):
self.items = [] # (value, minimum so far)
def push(self, x):
low = min(x, self.items[-1][1]) if self.items else x
self.items.append((x, low))
def pop(self):
return self.items.pop()[0]
def get_min(self):
return self.items[-1][1]
s = MinStack()
for x in [5, 3, 7, 1]:
s.push(x)
print(s.get_min())
s.pop()
print(s.get_min())
s.pop()
s.pop()
print(s.get_min())It prints 1, then 3, then 5. A leaner version keeps a second stack pushed only when the value is <= its top; with <, popping one of two equal minimums would lose the other.
What is a monotonic stack, and how does it find the next greater element?
A monotonic stack keeps its elements in order by popping anything that would break it before pushing. For next greater element, keep indexes still waiting; a bigger value answers every smaller one it pops. Each index is pushed and popped once: O(n).
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # indexes whose values never increase
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
result[stack.pop()] = x
stack.append(i)
return result
print(next_greater([2, 1, 2, 4, 3]))
print(next_greater([73, 74, 75, 71, 69, 72, 76, 73]))The same loop solves daily temperatures and the largest rectangle in a histogram.
What is a heap, and how do you use it as a priority queue?
A binary heap is a complete binary tree in an array where every parent is at most its children (a min heap). The smallest item sits at index 0, push and pop are O(log n), and building one is O(n). Python's heapq is a min heap; negate values for a max heap.
import heapq
tasks = [(3, "write tests"), (1, "fix prod bug"), (2, "review PR")]
heapq.heapify(tasks)
while tasks:
priority, name = heapq.heappop(tasks)
print(priority, name)
# max heap trick: push negated values
nums = [5, 1, 8, 3]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)
print(-max_heap[0])Top k uses a min heap of size k, O(n log k). Watch heap insert and remove.
What does this print: h[0] before and after a heappop?
import heapq
h = []
for x in [5, 1, 8, 3]:
heapq.heappush(h, x)
print(h[0], heapq.heappop(h), h[0])Predict the output
h[0] is always the smallest item, so the first value is 1. Arguments are evaluated left to right: heappop returns 1, then h[0] is the new smallest, 3. Only index 0 is guaranteed; the rest of the list is not sorted.
How would you design an LRU cache with O(1) get and put?
Combine a hash map with a doubly linked list. The map finds a key's node in O(1); the list keeps nodes in order of use, so moving one to the front and evicting the tail are O(1). OrderedDict is that pair:
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False) # least recently used
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a")
cache.put("c", 3) # evicts "b"
print(cache.get("b"), cache.get("a"), cache.get("c"))Expect to write the list by hand; sentinel head and tail nodes remove the None checks. See a doubly linked list.
Hashing interview questions
How hash tables work, collisions, and the hash map patterns that turn O(n²) searches into one pass.
What is a hash table, and why is lookup O(1)?
A hash table stores key-value pairs in an array of buckets; the key's hash modulo the array size picks the bucket, so a lookup checks one bucket instead of scanning. That is O(1) on average, degrading toward O(n) when many keys share a bucket, which is why tables resize. See keys being hashed into buckets.
How do you solve two sum in O(n)?
Walk the array once with a map from value to index: if target - number is already in the map you have the pair, otherwise store the number. O(n) time and space.
def two_sum(nums, target):
seen = {}
for i, x in enumerate(nums):
need = target - x
if need in seen:
return [seen[need], i]
seen[x] = i
return []
print(two_sum([2, 7, 11, 15], 9))
print(two_sum([3, 3], 6))Check before you insert, or [3] with target 6 pairs the 3 with itself.
What is a hash collision, and how is it handled?
A collision is two keys landing in the same bucket, unavoidable because there are more keys than buckets. Separate chaining (Java HashMap) keeps a list per bucket; open addressing (CPython dict) probes other slots and needs tombstones for deletes. Both stay O(1) on average while the load factor is bounded. Since Java 8 (JEP 180), OpenJDK's HashMap turns a bucket past 8 entries into a red-black tree once the table has at least 64 buckets.
What does this print: 1, 1.0 and True used as dict keys?
d = {}
d[1] = "a"
d[1.0] = "b"
d[True] = "c"
print(len(d), d[1])Predict the output
1, 1.0 and True are equal and have the same hash, so the dict treats them as one key, and each assignment overwrites the value: one entry, "c". A hash table compares by hash and then ==, so equal objects must have equal hashes. The dict docs use this very example.
What does this print: a list used as a dict key?
try:
d = {[1, 2]: "x"}
print(d)
except TypeError as e:
print(e)Predict the output
Lists are mutable, and a key whose hash changed would sit in a bucket it no longer points to, so Python raises TypeError with that message. Use a tuple: {(1, 2): "x"} works, and coordinate tuples are how grid problems mark visited cells.
How do you check whether two strings are anagrams?
Count the characters of both strings and compare the counts: O(n). Sorting both and comparing is O(n log n).
from collections import Counter
def is_anagram(a, b):
return len(a) == len(b) and Counter(a) == Counter(b)
print(is_anagram("listen", "silent"))
print(is_anagram("rat", "car"))
print(sorted("listen") == sorted("silent"))Follow-up: group anagrams? Use the sorted string, or a tuple of 26 counts, as a dict key. The Python dictionaries page covers Counter.
How do you find the first non-repeating character in a string?
Count every character in one pass, then return the first character whose count is 1. O(n) time, and O(1) space for a fixed alphabet.
from collections import Counter
def first_unique(s):
counts = Counter(s)
for i, ch in enumerate(s):
if counts[ch] == 1:
return i, ch
return -1, None
print(first_unique("swiss"))
print(first_unique("aabb"))Answering the first time you see a character fails, because a later copy can make it repeat.
How do you find the longest consecutive sequence in an unsorted array in O(n)?
Put the numbers in a set. A number starts a run only if x - 1 is missing; from each start, count up while x + 1 is present. Each number is visited at most twice: O(n).
def longest_consecutive(nums):
values = set(nums)
best = 0
for x in values:
if x - 1 not in values: # x starts a run
length = 1
while x + length in values:
length += 1
best = max(best, length)
return best
print(longest_consecutive([100, 4, 200, 1, 3, 2]))Without the x - 1 check, each run is counted from every member: O(n²).
How do you count the subarrays whose sum equals k?
Keep a running prefix sum and a map counting each prefix sum seen. A subarray ending here sums to k when an earlier prefix equals total - k, so add that count. O(n), and unlike a sliding window it handles negatives.
from collections import defaultdict
def subarray_sum(nums, k):
counts = defaultdict(int)
counts[0] = 1 # the empty prefix
total = answer = 0
for x in nums:
total += x
answer += counts[total - k]
counts[total] += 1
return answer
print(subarray_sum([1, 1, 1], 2))
print(subarray_sum([3, 4, -7, 3, 1, 3, 1, -4], 7))Forgetting counts[0] = 1 misses subarrays that start at index 0.
Tree and graph interview questions
Traversals, BSTs, BFS and DFS, topological sort, shortest paths, tries and union find.
What is the difference between a binary tree and a binary search tree?
A binary tree is any tree with at most two children per node. A BST adds an order: left subtree smaller, right subtree larger, so search, insert and delete follow one path, O(h). Balanced, h is O(log n); sorted inserts make a plain BST a list.
Follow-up: validate a BST? Pass down the allowed (low, high) range; comparing a node only with its children is wrong. Try inserts and searches on a BST.
What are full, complete, perfect and balanced binary trees?
They are rules about a binary tree's shape. Full: every node has 0 or 2 children. Complete: every level is full except possibly the last, filled from the left. Perfect: every internal node has two children and all leaves are on one level, so height h (in edges) means 2^(h+1) - 1 nodes. Balanced: subtree heights differ by at most 1 everywhere, so height is O(log n). A heap is complete, which is why it fits in an array. See a binary tree built node by node.
What are inorder, preorder and postorder traversals?
They are depth-first orders that differ in when the node itself is visited: preorder is node, left, right; inorder is left, node, right; postorder is left, right, node.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
# 4 has children 2 and 6; 2 has 1 and 3; 6 has 5 and 7
root = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
def inorder(n):
return inorder(n.left) + [n.val] + inorder(n.right) if n else []
def preorder(n):
return [n.val] + preorder(n.left) + preorder(n.right) if n else []
def postorder(n):
return postorder(n.left) + postorder(n.right) + [n.val] if n else []
print("inorder: ", inorder(root))
print("preorder: ", preorder(root))
print("postorder:", postorder(root))Inorder on a BST gives sorted values. Preorder copies or serializes a tree; postorder computes from the children up, such as heights.
What does this print: a recursive preorder traversal of a five-node tree?
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
def preorder(n):
if not n:
return []
return [n.val] + preorder(n.left) + preorder(n.right)
print(preorder(root))Predict the output
Preorder visits a node before its subtrees: 1, then the left subtree (2, 4, 5), then 3. [4, 2, 5, 1, 3] is inorder, [4, 5, 2, 3, 1] postorder and [1, 2, 3, 4, 5] level order.
How do you find the height (maximum depth) of a binary tree?
A node's height is 1 plus the larger of its children's heights, and an empty tree has height 0. Each node is visited once: O(n) time, O(h) stack.
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def height(node):
if node is None:
return 0
return 1 + max(height(node.left), height(node.right))
root = Node(3, Node(9), Node(20, Node(15), Node(7, Node(1))))
print(height(root))Ask whether height counts nodes or edges; the two definitions differ by one.
How do you find the lowest common ancestor of two nodes in a binary tree or a BST?
The LCA of p and q is the deepest node with both in its subtree (a node is its own descendant). In a BST, walk down: both values smaller, go left; both larger, go right; otherwise this node is the LCA, in O(h).
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def lca_bst(root, p, q):
node = root
while node:
if p < node.val and q < node.val:
node = node.left
elif p > node.val and q > node.val:
node = node.right
else:
return node.val
return None
def lca_tree(node, p, q): # any binary tree, p and q both present
if node is None or node.val in (p, q):
return node
left = lca_tree(node.left, p, q)
right = lca_tree(node.right, p, q)
return node if left and right else left or right
# 6 has children 2 and 8; 2 has 0 and 4; 8 has 7 and 9
root = Node(6, Node(2, Node(0), Node(4)), Node(8, Node(7), Node(9)))
print(lca_bst(root, 2, 8), lca_bst(root, 0, 4), lca_bst(root, 2, 4))
print(lca_tree(root, 0, 4).val, lca_tree(root, 7, 9).val)A plain binary tree has no order, so lca_tree searches both sides in O(n). The BST trap: p itself can be the answer, as lca_bst(root, 2, 4) returns 2.
How do you do a level order traversal of a binary tree?
Use a queue: record its length, pop exactly that many nodes and push their children; that is one level. O(n) time, O(w) space for the widest level w.
from collections import deque
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def level_order(root):
if not root:
return []
levels, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(level)
return levels
root = Node(3, Node(9), Node(20, Node(15), Node(7)))
print(level_order(root))The same loop gives right side view (the last node of each level) and zigzag order.
What is the difference between BFS and DFS, and when do you use each?
BFS explores level by level with a queue; DFS follows one path as deep as it can before backtracking, with recursion or a stack. Both are O(V + E). BFS finds the fewest steps when every step costs the same; DFS does not, but suits islands, topological sort, cycles and backtracking, and holds only the current path in memory. Watch BFS spread out level by level.
What does this print: BFS from A over a graph where B and C share a neighbor?
from collections import deque
graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
seen = {"A"}
order = []
q = deque(["A"])
while q:
node = q.popleft()
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
q.append(nxt)
print(" ".join(order))Predict the output
BFS finishes A's neighbors, B and C, before going deeper, then visits D and E: A B C D E. A B D C E is the DFS order. Marking nodes seen when enqueued stops D being queued twice.
How do you represent a graph: adjacency list or adjacency matrix?
An adjacency list stores each node's neighbors, O(V + E) space; an adjacency matrix is a V × V grid where m[u][v] says whether the edge exists, O(V²) space but an O(1) edge check. Default to a list, since most graphs are sparse; in Python, a dict of lists:
from collections import defaultdict
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # drop this line for a directed graph
print(dict(graph))How do you count the number of islands in a grid?
Scan every cell; on unvisited land, count an island and flood fill from it, marking connected land visited. O(rows × cols).
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = set()
def fill(r, c):
stack = [(r, c)]
while stack:
r, c = stack.pop()
if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
continue
if grid[r][c] == "0":
continue
seen.add((r, c))
stack.extend([(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
count += 1
fill(r, c)
return count
grid = [
"11000",
"11000",
"00100",
"00011",
]
print(num_islands(grid))The fill uses an explicit stack because recursive DFS on a 1000 × 1000 land grid would pass Python's recursion limit.
How do you detect a cycle in a directed graph, and what is topological sort?
A topological order lists a directed graph's nodes so every edge goes from earlier to later, like prerequisites before courses. It exists exactly when there is no cycle, so computing it detects cycles. Kahn's algorithm repeatedly removes nodes with no incoming edges, O(V + E):
from collections import deque
def topo_order(n, edges):
graph = [[] for _ in range(n)]
indegree = [0] * n
for u, v in edges: # u must come before v
graph[u].append(v)
indegree[v] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order if len(order) == n else None # None: a cycle
print(topo_order(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))
print(topo_order(3, [(0, 1), (1, 2), (2, 0)]))The DFS version colors nodes white, gray and black; reaching a gray node means a cycle. See topological sort run on a graph.
How does Dijkstra's algorithm work, and when does it fail?
Dijkstra finds shortest paths from one source when no edge weight is negative. Pop the closest node from a min heap and relax its edges. O((V + E) log V) with a binary heap.
import heapq
def dijkstra(graph, source):
dist = {source: 0}
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
print(dijkstra(graph, "A"))Negative weights break it, since a node popped as final could later get a shorter path; use Bellman-Ford, O(VE). With equal weights, BFS is enough. See Dijkstra relax edges step by step.
What is a trie, and when is it better than a hash set?
A trie stores strings character by character: each node maps a character to a child, and a flag marks a word's end. Insert, search and "any word with this prefix?" are O(L) for length L; a hash set cannot answer the prefix query without scanning.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True # end of a word
def _walk(self, s):
node = self.root
for ch in s:
if ch not in node:
return None
node = node[ch]
return node
def search(self, word):
node = self._walk(word)
return node is not None and "$" in node
def starts_with(self, prefix):
return self._walk(prefix) is not None
t = Trie()
for w in ["code", "coder", "coddy"]:
t.insert(w)
print(t.search("cod"), t.starts_with("cod"), t.search("coder"))The cost is memory, one node per character of every distinct prefix. Watch words being inserted into a trie.
What is union find (disjoint set union), and where is it used?
Union find keeps disjoint sets: find(x) returns x's representative, union(a, b) merges two sets. With path compression and union by size, both are nearly O(1) amortized.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected: this edge closes a cycle
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
d = DSU(5)
for a, b in [(0, 1), (1, 2), (3, 4)]:
d.union(a, b)
groups = len({d.find(i) for i in range(5)})
print(groups, d.union(0, 2))Use it for connected components, undirected cycles and Kruskal's MST. It cannot split a set, so edge deletions do not fit.
What is a minimum spanning tree, and how do Kruskal's and Prim's algorithms differ?
A minimum spanning tree of a connected, undirected, weighted graph is the V - 1 edges that connect every vertex at the lowest total weight. Kruskal sorts edges and adds each that closes no cycle, using union find, O(E log E); Prim grows one tree by the lightest leaving edge, O(E log V) with a heap.
def kruskal(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total, used = 0, []
for w, u, v in sorted(edges):
ru, rv = find(u), find(v)
if ru != rv: # skip edges that would close a cycle
parent[ru] = rv
total += w
used.append((u, v, w))
return total, used
edges = [(1, 0, 1), (4, 0, 2), (3, 1, 2), (2, 1, 3), (5, 2, 3)] # (weight, u, v)
print(kruskal(4, edges))An MST minimizes total weight, not distance from a source. See Kruskal's algorithm pick edges.
Sorting and searching interview questions
Sorting trade-offs, binary search and its variants, and selecting the k-th element.
Compare the common sorting algorithms by time, space and stability.
Merge and heap sort are O(n log n) always, quick sort on average, the simple sorts O(n²):
- Insertion, and bubble with an early exit: O(1) space, stable, O(n) on sorted input.
- Selection: O(1) space, not stable.
- Merge: O(n) space, stable.
- Quick: O(n²) worst, O(log n) stack on average, not stable.
- Heap: O(1) space, not stable.
- Counting: O(n + k), stable.
How do you implement binary search, and what are the common bugs?
Keep a range [lo, hi] that holds the target if it exists, check the middle, and discard the half that cannot hold it. O(log n) on a sorted array.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
nums = [1, 3, 5, 7, 9, 11]
print(binary_search(nums, 7), binary_search(nums, 4))Watch for while lo < hi on a closed range (skips the last candidate), lo = mid (loops forever), and in Java or C++ (lo + hi) / 2 overflowing. Watch binary search halve the range.
What is the difference between merge sort and quick sort?
Both are divide and conquer. Merge sort works while merging: O(n log n) always, stable, O(n) extra space, good for linked lists. Quick sort works while partitioning around a pivot: O(n²) at worst (rare with a random pivot), not stable, O(log n) stack on average, and usually faster on arrays.
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= keeps it stable
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
return out + left[i:] + right[j:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))How does quick sort's partition work, and how do you avoid the O(n²) worst case?
Partition picks a pivot and moves smaller values before it and the rest after, leaving the pivot in its final place. Lomuto does it in one pass:
import random
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
p = random.randint(lo, hi) # random pivot
a[p], a[hi] = a[hi], a[p]
pivot, boundary = a[hi], lo
for i in range(lo, hi):
if a[i] < pivot:
a[i], a[boundary] = a[boundary], a[i]
boundary += 1
a[boundary], a[hi] = a[hi], a[boundary]
quick_sort(a, lo, boundary - 1)
quick_sort(a, boundary + 1, hi)
return a
print(quick_sort([5, 2, 9, 1, 5, 6, 3]))Pivots that split badly every time, like the last element of a sorted array, give O(n²); a random pivot avoids it. See quick sort partition an array.
What does this print: sorting people by age when two pairs share an age?
people = [("Asha", 25), ("Ravi", 30), ("Neha", 25), ("John", 30)]
print([name for name, age in sorted(people, key=lambda p: p[1])])Predict the output
Python's sort is guaranteed stable: items with equal keys keep their input order, so Asha stays before Neha and Ravi before John. To break ties by name in one call, use key=lambda p: (p[1], p[0]).
How do you search in a rotated sorted array in O(log n)?
Binary search, using the fact that one half of [lo, hi] is always sorted. Compare nums[lo] with nums[mid] to find that half, search it if the target is in its range, otherwise search the other.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0), search_rotated(nums, 3))With duplicates like [1, 1, 1, 3, 1] the worst case becomes O(n).
What is binary search on the answer?
When you need the smallest or largest value meeting a monotonic condition (if speed k works, every faster speed works), binary search over possible answers. With an O(n) check, O(n log range).
def min_eating_speed(piles, hours):
def can_finish(speed):
return sum((p + speed - 1) // speed for p in piles) <= hours
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
if can_finish(mid):
hi = mid # mid works, try smaller
else:
lo = mid + 1
return lo
print(min_eating_speed([3, 6, 7, 11], 8))Look for "minimum capacity" or "minimize the largest sum" with large limits, and argue the check is monotonic.
How do you find the k-th largest element, and which approach is fastest?
Sort in O(n log n), keep a min heap of size k in O(n log k), or run quickselect in O(n) average, O(n²) worst. The heap wins when data streams in or k is small.
import heapq
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for x in nums[k:]:
if x > heap[0]:
heapq.heapreplace(heap, x)
return heap[0]
print(kth_largest([3, 2, 1, 5, 6, 4], 2))
print(heapq.nlargest(2, [3, 2, 1, 5, 6, 4]))Quickselect partitions like quick sort but recurses into one side: n + n/2 + n/4 and so on, O(n).
Why can't a comparison sort be faster than O(n log n)?
A comparison sort must tell apart all n! orderings, and each comparison has two outcomes, so it needs at least log₂(n!) comparisons, which grows like n log n. Counting and radix sort beat it by using values as indexes, which needs integer keys in a limited range. See counting sort place values by index.
Dynamic programming interview questions
Spotting a DP problem, memoization against tabulation, and the classics: knapsack, LIS, LCS and edit distance.
What is dynamic programming?
Dynamic programming builds an answer from smaller subproblems and stores each one so it is computed once. It applies when subproblems overlap and the best answer is built from best sub-answers. Naive Fibonacci is exponential; storing results makes it O(n). Say what dp[i] means before the transition.
How many function calls does this naive Fibonacci make?
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
fib(10)
print(calls)Predict the output
Every call with n of 2 or more makes two more, so fib(10) makes 177 calls, 2 * F(n + 1) - 1, growing like 1.618^n. Caching cuts it to one call per n:
from functools import lru_cache
calls = 0
@lru_cache(maxsize=None)
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10), calls)That prints 55 and 11 calls.
What is the difference between memoization and tabulation?
Memoization is top-down: write the recursion and cache each result. Tabulation is bottom-up: fill a table from the smallest subproblems so dependencies are always ready. Same time complexity.
from functools import lru_cache
@lru_cache(maxsize=None)
def ways_memo(n): # top-down
if n <= 1:
return 1
return ways_memo(n - 1) + ways_memo(n - 2)
def ways_table(n): # bottom-up
dp = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(ways_memo(10), ways_table(10))Memoization computes only needed states but can hit the recursion limit; tabulation makes it easy to keep only the rows you need.
What is the difference between greedy and dynamic programming? Show a case where greedy fails.
Greedy takes the locally best choice and never revisits it; DP tries every choice per subproblem and keeps the best. Greedy is only correct when you can prove the local choice is safe. Coins [1, 3, 4] for 6 break it: greedy gives 4 + 1 + 1, the best is 3 + 3.
def greedy_coins(coins, amount):
count = 0
for c in sorted(coins, reverse=True):
count += amount // c
amount %= c
return count if amount == 0 else -1
def dp_coins(coins, amount):
INF = float("inf")
dp = [0] + [INF] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != INF else -1
print(greedy_coins([1, 3, 4], 6), dp_coins([1, 3, 4], 6))Greedy is right for interval scheduling and for US coins.
How do you solve the house robber problem?
Rob house i (its money plus the best up to two houses back) or skip it (the best up to the previous house): best[i] = max(best[i - 1], best[i - 2] + money[i]). Two variables suffice: O(n) time, O(1) space.
def rob(money):
prev2 = prev1 = 0
for m in money:
prev2, prev1 = prev1, max(prev1, prev2 + m)
return prev1
print(rob([2, 7, 9, 3, 1]))
print(rob([2, 1, 1, 2]))The second case shows taking every other house fails: the best, 4, robs the first and last.
What does this print: a DP table counting right and down paths in a 3 × 3 grid?
rows, cols = 3, 3
dp = [[1] * cols for _ in range(rows)]
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
print(dp[-1][-1])Predict the output
Paths into a cell come from the cell above plus the cell to its left, and the first row and column are all 1, so the last cell of a 3 × 3 grid is 6, which is C(4, 2). Keeping one row cuts space to O(cols).
How do you solve the 0/1 knapsack problem?
dp[w] is the best value with capacity w. For each item, loop w from high to low: dp[w] = max(dp[w], dp[w - weight] + value). Going downward uses each item once; going upward allows reuse, the unbounded knapsack. O(n × W) time, O(W) space.
def knapsack(items, capacity):
dp = [0] * (capacity + 1)
for weight, value in items:
for w in range(capacity, weight - 1, -1):
dp[w] = max(dp[w], dp[w - weight] + value)
return dp[capacity]
items = [(1, 1), (3, 4), (4, 5), (5, 7)] # (weight, value)
print(knapsack(items, 7))That is pseudo-polynomial: slow when W is huge.
How do you find the longest increasing subsequence, and how do you get it to O(n log n)?
The O(n²) DP sets dp[i] to the longest increasing subsequence ending at i. For O(n log n), keep tails, the smallest last value of an increasing subsequence of each length; each number extends it or replaces the first tail not smaller, found by binary search.
from bisect import bisect_left
def lis_length(nums):
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))Only the length of tails is meaningful, not its contents.
How do you solve longest common subsequence and edit distance?
Both fill a table where dp[i][j] covers the first i characters of one string and the first j of the other. On a match, extend the diagonal; otherwise LCS drops a character from either string, and edit distance takes 1 plus the cheapest of insert, delete or replace. O(m × n).
def lcs(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[-1][-1]
def edit_distance(a, b):
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(len(a) + 1):
dp[i][0] = i
for j in range(len(b) + 1):
dp[0][j] = j
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[-1][-1]
print(lcs("abcde", "ace"), edit_distance("horse", "ros"))Base cases: an empty prefix has LCS 0, and emptying a prefix of length i costs i deletions.
How do you recognize that a problem needs dynamic programming?
Look for a count of ways, a minimum or maximum, or "is it possible", where a big input's answer builds on smaller ones and brute force repeats subproblems. Then:
- Define the state: "
dp[i]is the fewest coins for amount i". - Write the transition.
- Set the base cases.
- Pick the fill order, or memoize.
Listing every solution, rather than counting, is usually backtracking.
DSA coding interview questions
Complete solutions to common coding problems, each with the edge case to raise.
How do you find the maximum profit from buying and selling a stock once?
Track the lowest price so far; each day's best sale is price - lowest, and you keep the maximum. O(n) time, O(1) space.
def max_profit(prices):
lowest = float("inf")
best = 0
for p in prices:
lowest = min(lowest, p)
best = max(best, p - lowest)
return best
print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))If prices only fall, the answer is 0, not a negative number. Follow-up: unlimited transactions? Add up every positive day-to-day increase.
How do you find the majority element (more than n/2 occurrences) in O(1) space?
Use Boyer-Moore voting: keep a candidate and a counter; when the counter is 0 take the current element, then add 1 on a match and subtract 1 otherwise. Other elements can cancel at most one copy each, so the majority survives. O(n) time, O(1) space.
def majority(nums):
candidate, count = None, 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate
print(majority([2, 2, 1, 1, 1, 2, 2]))If a majority might not exist, verify the candidate in a second pass.
How do you find the longest substring without repeating characters?
Use a sliding window and a map from each character to its last index. When the character at right was seen inside the window, jump left past it. O(n).
def longest_unique(s):
last = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return best
for s in ["abcabcbb", "bbbbb", "pwwkew", "abba"]:
print(s, longest_unique(s))"abba" catches the classic bug: without last[ch] >= left, the second a moves left backwards.
How do you merge overlapping intervals?
Sort by start; if the next interval starts at or before the last merged end, extend that end, otherwise start a new interval. O(n log n) for the sort.
def merge(intervals):
merged = []
for start, end in sorted(intervals):
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge([[1, 3], [8, 10], [2, 6], [15, 18], [17, 20]]))
print(merge([[1, 4], [2, 3]]))The max matters because [1, 4] contains [2, 3]. Ask whether touching intervals like [1, 2] and [2, 3] merge; <= says yes.
How do you find all unique triplets that sum to zero?
Sort, fix one number at a time, and find pairs that sum to its negative with two pointers over the rest. Skip equal values for the fixed number and after each match to avoid duplicate triplets. O(n²).
def three_sum(nums):
nums = sorted(nums)
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
result.append([nums[i], nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
hi -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))How do you solve trapping rain water in O(n) time and O(1) space?
Water above a bar is the lower of the tallest bars on its left and right, minus the bar. Move two pointers inward with running maximums, always moving the lower side: the other side has a bar at least as tall, so the water here depends only on this side's maximum.
def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water
print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))Two arrays of running maximums also work, at O(n) space.
How do you generate all subsets or permutations of an array?
Backtracking: add a choice, recurse, then undo it. For subsets each element is in or out, so there are 2^n subsets and O(n × 2^n) work; permutations give n! results.
def subsets(nums):
result, path = [], []
def go(i):
if i == len(nums):
result.append(path[:]) # copy, path keeps changing
return
path.append(nums[i]) # take nums[i]
go(i + 1)
path.pop() # undo
go(i + 1) # skip nums[i]
go(0)
return result
print(subsets([1, 2, 3]))The common bug is appending path instead of path[:]: every entry then points to the same list, which is empty by the end.
How do you find the maximum of every window of size k in O(n)?
Keep a deque of indexes with decreasing values. For each element, pop smaller values from the back, push its index, and drop the front once it leaves the window; the front is the maximum. Each index is pushed and popped once: O(n), against O(n × k).
from collections import deque
def window_max(nums, k):
dq, result = deque(), []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))The deque is a monotonic queue, the queue version of the monotonic stack.
Preparing for the interview
How do I prepare for a DSA interview?
Which DSA topics are asked most for freshers and campus placements?
What is asked in DSA interviews for experienced developers?
Which programming language should I use for DSA interviews?
deque, heapq and Counter built in, and Java and C++ are equally accepted. Know your language's collections and their complexities.