DSA course menu
Intermediate DSA Interview Questions and Answers
Intermediate data structures and algorithms interview questions with Python solutions: BFS vs DFS, heaps, BSTs, quick sort vs merge sort, top k frequent, rotated sorted array search, level order traversal, LRU cache and more.
On this page
- Concepts
- 1. BFS or DFS: when do you use each?
- 2. Merge sort or quick sort?
- 3. What is a heap, and what are its operation costs?
- 4. Why can a binary search tree become slow, and how is that fixed?
- 5. What is amortized O(1)?
- Coding questions
- 6. Top k most frequent elements.
- 7. Search in a rotated sorted array.
- 8. Level order traversal of a binary tree.
- 9. Validate a binary search tree.
- 10. Number of islands.
- 11. Kth largest element in a list.
- 12. Group anagrams.
- 13. Longest substring without repeating characters.
- Key takeaway
These questions are typical of software developer interviews after the first screening round. Each answer explains the idea, then shows code that you should be able to write from memory once you understand it.
Concepts#
1. BFS or DFS: when do you use each?#
Show solution
BFS (a queue) explores level by level, so it finds the shortest path in an unweighted graph and is natural for "minimum number of steps". DFS (recursion or a stack) goes deep first; it suits exhaustive exploration, cycle detection, topological sorting and backtracking. Both are O(V + E). BFS can use more memory on wide graphs; recursive DFS can hit recursion limits on deep ones.
2. Merge sort or quick sort?#
Show solution
Random pivots make quick sort's worst case very unlikely.
3. What is a heap, and what are its operation costs?#
Show solution
A complete binary tree stored in an array where every parent is ≤ its children (min-heap). Peek at the minimum: O(1). Push and pop: O(log n). Build from a list: O(n). It is the standard priority queue, used for Dijkstra, top-k problems and scheduling.
4. Why can a binary search tree become slow, and how is that fixed?#
Show solution
BST operations cost O(height). Inserting sorted data makes every node a right child, so the height becomes n and operations become O(n). Self-balancing trees (AVL, red-black) rotate nodes after inserts and deletes to keep the height O(log n).
5. What is amortized O(1)?#
Show solution
An operation that is occasionally expensive but cheap on average over a long sequence. Appending to a dynamic array is the classic case: a resize copies everything (O(n)), but capacity doubles each time, so n appends cost O(n) in total: O(1) each on average.
Coding questions#
6. Top k most frequent elements.#
Show solution
from collections import Counter
import heapq
def top_k_frequent(nums, k):
counts = Counter(nums)
return [x for x, _ in heapq.nlargest(k, counts.items(), key=lambda item: item[1])]
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))
print(top_k_frequent([4, 4, 5, 5, 5, 6], 1))[1, 2]
[5]Counting is O(n); picking k with a heap is O(n log k). Bucket sort by frequency gives O(n).
7. Search in a rotated sorted array.#
A sorted list was rotated at an unknown point ([4, 5, 6, 7, 0, 1, 2]). Find a target in O(log n).
Show solution
At every step, one half of the range is still sorted. Check whether the target lies inside that sorted half; if so search there, otherwise search the other half.
def search_rotated(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
if nums[low] <= nums[mid]: # left half is sorted
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1
data = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(data, 0), search_rotated(data, 3), search_rotated(data, 6))4 -1 28. Level order traversal of a binary tree.#
Show solution
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 []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
queue.extend(child for child in (node.left, node.right) if child)
result.append(level)
return result
root = Node(3, Node(9), Node(20, Node(15), Node(7)))
print(level_order(root))[[3], [9, 20], [15, 7]]BFS with a queue; reading len(queue) at the start of each round separates the levels. O(n).
9. Validate a binary search tree.#
Show solution
class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_bst(node, low=float("-inf"), high=float("inf")):
if node is None:
return True
if not low < node.val < high:
return False
return is_bst(node.left, low, node.val) and is_bst(node.right, node.val, high)
print(is_bst(Node(2, Node(1), Node(3))))
print(is_bst(Node(5, Node(1), Node(4, Node(3), Node(6)))))True
FalsePass down the allowed range; comparing only parent and child misses violations deeper down.
10. Number of islands.#
Show solution
def num_islands(grid):
grid = [list(row) for row in grid]
rows, cols = len(grid), len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
stack = [(r, c)]
grid[r][c] = "0"
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == "1":
grid[ni][nj] = "0"
stack.append((ni, nj))
return count
print(num_islands(["11000", "11000", "00100", "00011"]))3Each land cell is visited once: O(rows × cols). An explicit stack avoids recursion limits on big grids.
11. Kth largest element in a list.#
Show solution
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), kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))5 4A min-heap of size k: O(n log k). Quickselect is O(n) on average. Sorting is O(n log n) and also acceptable to mention.
12. Group anagrams.#
Show solution
from collections import defaultdict
def group_anagrams(words):
groups = defaultdict(list)
for w in words:
groups[tuple(sorted(w))].append(w)
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]The sorted letters are the key. O(n · L log L) for n words of length L.
13. Longest substring without repeating characters.#
Show solution
def longest_unique(s):
last_seen, left, best = {}, 0, 0
for right, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= left:
left = last_seen[ch] + 1 # jump past the repeat
last_seen[ch] = right
best = max(best, right - left + 1)
return best
print(longest_unique("abcabcbb"), longest_unique("pwwkew"), longest_unique("abba"))3 3 2A sliding window that jumps the left edge using the last position of each character: O(n). The >= left check matters for inputs like "abba".
Key takeaway#
Next: Advanced Questions.
Finished this lesson?