Data structures and algorithms rounds are less about remembering a solution than about reading a problem and naming the pattern underneath it. Interviewers give you a scenario (dedupe these IDs, find the cheapest route, schedule these meetings), watch you choose a structure, then push on the edges: duplicates, empty input, negative numbers, a million rows. The last question is almost always "what does this cost in time and space, and why?"
Candidates slip in a few predictable places. They call code O(n) without noticing that x in some_list or a slice is a loop of its own. They use a sliding window on data with negative values, mark BFS nodes visited at the wrong moment, run Dijkstra on negative edges, or trust a greedy rule that a three-element input breaks. Strong answers state the precondition for the pattern, then test the boundary cases out loud.
The 31 questions below are grouped into five areas: complexity and hidden costs; arrays, hashing and binary search; linked lists, stacks, queues and heaps; trees and graphs; and dynamic programming with greedy algorithms. Each has a worked answer and Python code that we ran and tested against brute force on small inputs. The page ends with prep advice, a short quiz and an FAQ.
Intermediate31 questions
Data Structures and Algorithms Interview Questions
Practice data structures and algorithms interview questions on complexity, hashing, two pointers, sliding windows, stacks, heaps, graphs, dynamic programming and greedy, with worked answers and tested Python.
Every coding round ends with "what is the time and space complexity?", and many interviewers ask it before you write a line. They want to know whether you can predict how code behaves at a million inputs from reading it, because that is what keeps a service from timing out in production.
The idea that matters most: count the work that a line does for you, not just the loops you wrote. Membership tests on lists, slicing, string concatenation and copies are all loops in disguise, and amortized analysis is how you defend a nested loop that is really linear.
Complexity Analysis and Hidden Costs
A teammate dedupes a list of 40,000 user IDs while keeping the first-seen order. It takes two seconds and nobody can see why: there is only one loop. What is going on, and how do you fix it?
EasyComplexity Analysis and Hidden Costs
Sample Answer
The x not in out test is a second loop. Membership on a list scans it from the front, so each check costs up to the length of out, and the whole function is O(n^2). With 20,000 distinct IDs, each appearing twice, the list version took 2.06 seconds in a local run and the set version took about 0.001 seconds. A set hashes the value and jumps to a bucket, so a lookup is O(1) on average and the function is O(n) time with O(n) extra space. When you only need the result, list(dict.fromkeys(items)) does the same thing in one line, because dicts keep insertion order. The trap is calling one loop "O(n)" without checking what each line costs.
Python
1defdedupe_slow(items):2 out =[]3for x in items:4if x notin out:# scans out: O(n) per check5 out.append(x)6return out
78defdedupe(items):9 seen, out =set(),[]10for x in items:11if x notin seen:# hash lookup: O(1) on average12 seen.add(x)13 out.append(x)14return out
You build a 400,000-piece report with s += piece in a loop. It runs fast on your laptop, so you argue it is linear. The interviewer says it is quadratic. Who is right?
MediumComplexity Analysis and Hidden Costs
Sample Answer
Both, which is why this comes up. Python strings are immutable, so s += piece creates a new string and copies everything so far: O(n) per step and O(n^2) in total. CPython has an optimization that resizes the string in place when nothing else refers to it, and that is what your laptop measured: 0.011 seconds for 400,000 appends against 0.001 for "".join. The optimization is fragile. PEP 8 says not to rely on it, and other Python implementations do not have it. Keep one extra reference to s inside the loop and it disappears: 20,000, 40,000 and 80,000 appends took 0.004, 0.021 and 0.117 seconds, about five times longer per doubling. Use "".join(parts) or io.StringIO.
Python
1defbuild_slow(parts):2 s =""3for p in parts:4 s += p # may copy all of s on every pass5return s
67defbuild(parts):8return"".join(parts)# sizes the result once, copies each part once
An interviewer asks why list.append is called O(1) when the list sometimes has to copy every element into a bigger block of memory. Explain it, and say what you would tell a latency-sensitive caller.
MediumComplexity Analysis and Hidden Costs
Sample Answer
Append is amortized O(1). When the array is full, CPython allocates a larger block and copies, but it over-allocates by about one eighth plus a small constant, so the capacity grows geometrically (4, 8, 16, 24, 32, 40, 52...). The copy costs form a geometric series that sums to O(n) over n appends, so the average cost per append is constant. The snippet counts capacity changes with sys.getsizeof and printed 86 for one million appends. Amortized is a guarantee about the total, not about each call: a single append can still take O(n). If one slow call hurts, as in a latency-bound loop, preallocate ([0] * n) or use a structure with a real per-operation bound. Also, amortized is not average-case: it holds for every input sequence.
Python
1import sys
23lst, resizes, last =[],0, sys.getsizeof([])4for i inrange(1_000_000):5 lst.append(i)6if sys.getsizeof(lst)!= last:# capacity grew: a reallocation7 resizes, last = resizes +1, sys.getsizeof(lst)8print(resizes)
A candidate writes a recursive palindrome check that calls itself on s[1:-1]. It looks O(n). What is the real time and space cost, and what happens on a 2,000-character string?
MediumComplexity Analysis and Hidden Costs
Sample Answer
Slicing copies. s[1:-1] builds a new string of length n - 2, then n - 4, and so on, so the copies add up to about n^2 / 4 characters: O(n^2) time. Memory is O(n^2) too, because the recursion goes n / 2 frames deep and every live frame holds its own slice. Python has no tail-call elimination and the default recursion limit is 1000, so in a local run a 2,000-character string raised RecursionError. The two-index loop does the same comparisons with no copies: O(n) time, O(1) extra space, and it handled a million characters without trouble. The same trap shows up in recursive binary search written with arr[mid:]: the slice alone makes it O(n) instead of O(log n).
Python
1defis_pal_slice(s):2iflen(s)<2:3returnTrue4return s[0]== s[-1]and is_pal_slice(s[1:-1])# copies len(s) - 2 chars56defis_pal(s):7 lo, hi =0,len(s)-18while lo < hi:9if s[lo]!= s[hi]:10returnFalse11 lo, hi = lo +1, hi -112returnTrue
Your solution for "shortest subarray with sum at least target" (all values positive) has a while loop inside a for loop. The interviewer says that makes it O(n^2). Defend your O(n) claim.
HardComplexity Analysis and Hidden Costs
Sample Answer
Count how many times each line runs over the whole run, not per outer iteration. right advances n times. Inside the while, left only moves forward and never passes right, so across the entire run the inner body executes at most n times in total, however those moves are spread out. Total work is at most 2n steps: O(n) time, O(1) space. The snippet counts inner moves and returned 99,903 for a 100,000-element input. This is aggregate amortized analysis, and the same argument proves that monotonic stacks and two-pointer scans are linear. The argument depends on positive values: with negatives, shrinking the window can increase the sum, the window is no longer monotonic, and you need prefix sums instead.
Python
1defshortest_at_least(nums, target):# nums are positive2 best, left, total, moves =float("inf"),0,0,03for right, x inenumerate(nums):4 total += x
5while total >= target:# left only moves forward6 best =min(best, right - left +1)7 total -= nums[left]8 left +=19 moves +=110return(0if best ==float("inf")else best), moves
Most first-round coding questions are array or string problems, because they test pattern recognition quickly: can you replace a brute-force pair loop with a hash map, two pointers, a sliding window, a prefix sum or a binary search? Interviewers also watch how you handle duplicates, empty input and off-by-one boundaries.
The idea that matters most: each pattern has a precondition. Sliding windows need a condition that changes in one direction as the window grows, two pointers need sorted data or a monotonic rule, binary search needs a yes/no test that flips once. Say the precondition out loud before you code.
Arrays, Strings, Hashing and Binary Search
Given an array of integers and a target, return the indices of two different elements that add up to the target. The brute force is O(n^2). Do better, and make sure [3, 3] with target 6 works.
EasyArrays, Strings, Hashing and Binary Search
Sample Answer
Walk the array once with a dict from value to index. For each x, the partner you need is target - x; if it is already in the dict, you are done. Checking before inserting x is what stops the function from pairing an element with itself, so [3, 2, 4] with target 6 returns (1, 2), not (0, 0). It also handles duplicates: [3, 3] returns (0, 1), because the first 3 is stored before the second one looks for it. That is O(n) time and O(n) space. If the array were sorted, two pointers from both ends would solve it in O(1) extra space, but sorting first costs O(n log n) and loses the original indices.
Python
1deftwo_sum(nums, target):2 seen ={}# value -> index3for i, x inenumerate(nums):4if target - x in seen:# check before inserting x5return seen[target - x], i
6 seen[x]= i
7returnNone
A dashboard asks for the sum of daily revenue between two dates, thousands of times per page load, over a fixed array of 10 years of days. Summing the slice each time is too slow. What do you build?
EasyArrays, Strings, Hashing and Binary Search
Sample Answer
Precompute a prefix-sum array once, where pre[i] is the sum of the first i values. Then the sum from lo to hi inclusive is pre[hi + 1] - pre[lo]: O(n) to build, O(1) per query, versus O(length of the range) per query by summing. The leading 0 (accumulate(nums, initial=0)) is the detail that removes the special case for ranges starting at index 0. For [3, -1, 4, 1, 5] the snippet built [0, 3, 2, 6, 7, 12] and answered query(1, 3) with 4. Prefix sums work for any invertible operation, so XOR works too, but max and min do not, since you cannot subtract a max. If the values change between queries, move to a Fenwick tree for O(log n) updates and queries.
Find the length of the longest substring with no repeated characters in a log line. Your first sliding-window version returns 3 for "abba". Find the bug and fix it.
MediumArrays, Strings, Hashing and Binary Search
Sample Answer
Keep a dict of the last index where each character appeared and a left edge for the window. When the current character repeats inside the window, jump left to one past its last position. The bug is jumping on any earlier occurrence, even one already outside the window. In "abba", the second b moves left to 2; then the final a sees its last index 0 and moves left back to 1, which brings the duplicate b back into the window and reports 3. Checking last[c] >= left (or writing left = max(left, last[c] + 1)) keeps the left edge moving forward only. The fixed version returns 3, 1, 3, 0 and 2 for "abcabcbb", "bbbbb", "pwwkew", "" and "abba". It is O(n) time and O(alphabet) space.
Python
1deflongest_unique(s):2 last, left, best ={},0,03for right, c inenumerate(s):4if last.get(c,-1)>= left:# repeat inside the current window5 left = last[c]+16 last[c]= right
7 best =max(best, right - left +1)8return best
Count the subarrays whose sum equals k in an array that can contain negative numbers. A sliding window passed your positive-only tests but fails now. Why, and what replaces it?
MediumArrays, Strings, Hashing and Binary Search
Sample Answer
A sliding window works only when growing the window moves the sum one way and shrinking moves it the other. Negatives break that, so you cannot tell whether to shrink. Use prefix sums instead: the subarray ending at i sums to k exactly when some earlier prefix equals total - k. Keep a count of prefix sums seen so far, add seen[total - k] at each step, then record total. The trap is forgetting seen[0] = 1, which counts subarrays that start at index 0. [1, -1, 0] with k = 0 has three such subarrays, and the function returns 3. O(n) time, O(n) space. A randomized comparison against an O(n^2) brute force over 500 small arrays matched on every case.
Python
1from collections import defaultdict
23defcount_subarrays(nums, k):4 seen = defaultdict(int)5 seen[0]=1# the empty prefix6 total = count =07for x in nums:8 total += x
9 count += seen[total - k]# earlier prefixes that leave exactly k10 seen[total]+=111return count
Given a string s and a pattern t (with possible repeated characters), return the shortest substring of s that contains every character of t with multiplicity. Aim for linear time.
HardArrays, Strings, Hashing and Binary Search
Sample Answer
Use a variable window with a frequency map. need counts how many of each character are still owed, and missing counts the total still owed. Expand right; a character reduces missing only if it was still needed, which is how extra copies get ignored. Once missing hits 0 the window is valid, so shrink from the left, recording the best window, until removing a character makes it owed again. Each index enters and leaves the window once, so the run is O(|s| + |t|). It returned "BANC" for "ADOBECODEBANC" and "ABC", "" for s = "a", t = "aa", and "aa" for "aa", "aa". The common bug is decrementing missing for every matching character, which miscounts repeats like t = "aa".
Python
1from collections import Counter
2defmin_window(s, t):3 need, missing = Counter(t),len(t)4 left, best =0,(0,float("inf"))5for right, c inenumerate(s):6 missing -= need[c]>07 need[c]-=18while missing ==0:# window covers t: shrink it9if right - left < best[1]- best[0]:10 best =(left, right)11 need[s[left]]+=112 missing += need[s[left]]>013 left +=114return""if best[1]==float("inf")else s[best[0]:best[1]+1]
A sorted array of event timestamps has many duplicates. Return the index of the first occurrence of a timestamp, or -1. Your binary search sometimes returns a middle duplicate and sometimes loops forever. Write it correctly.
MediumArrays, Strings, Hashing and Binary Search
Sample Answer
Search for a boundary, not a match. Keep a half-open range [lo, hi). If nums[mid] < target, the first match is to the right, so lo = mid + 1; otherwise mid could be the first match, so hi = mid, never mid - 1. The loop ends with lo at the first index whose value is at least the target, the same as bisect.bisect_left. Then check that lo is in range and holds the target. The infinite loop comes from mixing styles: lo = mid with a floor mid stalls when hi = lo + 1. Returning as soon as nums[mid] == target gives a duplicate from the middle. The function returned 1 for [1, 2, 2, 2, 3], and it agreed with bisect_left on 500 random arrays.
Python
1deffirst_index(nums, target):2 lo, hi =0,len(nums)# half-open range [lo, hi)3while lo < hi:4 mid =(lo + hi)//25if nums[mid]< target:6 lo = mid +17else:8 hi = mid # mid might be the first match9return lo if lo <len(nums)and nums[lo]== target else-1
Packages with given weights must ship in order within days days. Find the smallest ship capacity that makes it. Weights go up to 500 and there are 50,000 packages, so trying every capacity is too slow.
HardArrays, Strings, Hashing and Binary Search
Sample Answer
Binary search on the answer. You cannot search the array, but you can search the capacity, because the question "can capacity cap finish in days?" is monotonic: if it works, any larger capacity works too. The check is greedy and O(n): load each day until the next package would overflow, then start a new day. Bounds matter: the lowest sensible capacity is max(weights) (otherwise one package never fits) and the highest is sum(weights) (one day). That gives O(n log(sum)) time, about 50,000 times 25 steps here. For weights 1 to 10 over 5 days the function returned 15. The usual bug is starting lo at 1, so the check accepts capacities smaller than the heaviest package.
Python
1defmin_capacity(weights, days):2deffits(cap):# greedy: fill each day before the next3 used, load =1,04for w in weights:5if load + w > cap:6 used, load = used +1,07 load += w
8return used <= days
9 lo, hi =max(weights),sum(weights)10while lo < hi:11 mid =(lo + hi)//212if fits(mid): hi = mid
13else: lo = mid +114return lo
These structures show up less as "implement a stack" and more as the hidden engine of a solution: a stack for nesting, a monotonic stack for "next greater" questions, a deque for BFS, a heap for top-k and scheduling. Linked list questions test whether you can move references without losing the rest of the list.
The idea that matters most: know exactly when an element is pushed and popped, and argue that each element is pushed and popped once. That argument is what turns a loop with an inner while into an O(n) answer the interviewer accepts.
Linked Lists, Stacks, Queues and Heaps
Reverse a singly linked list in place and return the new head. Then explain what goes wrong in the version a colleague wrote as head, head.next, prev = head.next, prev, head.
EasyLinked Lists, Stacks, Queues and Heaps
Sample Answer
Walk the list with prev and head. Before you redirect head.next, save the next node, or you lose the rest of the list. Then point the current node back at prev and step both forward. O(n) time, O(1) space, and it handles an empty list (returns None) and a single node. The colleague's tuple assignment fails because Python evaluates the right side first, then assigns targets left to right: head is reassigned to the next node before head.next is written, so the code sets the wrong node's pointer. On [1, 2, 3] it crashed with AttributeError on None. Writing head.next, prev, head = prev, head, head.next happens to work, but the explicit nxt version is easier to defend.
Python
1classNode:2def__init__(self, val,next=None):3 self.val, self.next= val,next45defreverse(head):6 prev =None7while head:8 nxt = head.next# save it before we overwrite it9 head.next= prev
10 prev, head = head, nxt
11return prev # new head (None for an empty list)
A job scheduler stores tasks as a linked list, and a bug occasionally creates a cycle, hanging any loop that walks it. Detect whether there is a cycle and return the node where it begins, using O(1) extra memory.
MediumLinked Lists, Stacks, Queues and Heaps
Sample Answer
Floyd's algorithm. Move slow one step and fast two steps; if there is a cycle they must meet inside it, and if fast reaches the end there is none. To find the start, reset slow to the head and move both one step at a time; they meet at the cycle's first node. Why: let a be the distance from head to the cycle start and b the distance from the start to the meeting point. Fast traveled twice as far as slow, so a + b is a multiple of the cycle length, which means walking a more steps from the meeting point lands on the start. O(n) time, O(1) space. A visited set is simpler but uses O(n) memory.
Python
1defcycle_start(head):2 slow = fast = head
3while fast and fast.next:4 slow, fast = slow.next, fast.next.next5if slow is fast:# they met inside the cycle6 slow = head
7while slow isnot fast:# same speed now8 slow, fast = slow.next, fast.next9return slow
10returnNone
A config parser must reject strings with mismatched brackets such as "([)]", and accept other characters between them. Write the check and name the edge cases you would test.
EasyLinked Lists, Stacks, Queues and Heaps
Sample Answer
Push every opener on a stack. On a closer, the stack top must be the matching opener, so pop and compare. Two edge cases cause most failed attempts. A closer with an empty stack, as in ")(", must return false instead of raising on pop(). Leftover openers at the end, as in "((", mean something was never closed, so the function returns not stack rather than True. A counter per bracket type is the tempting shortcut and it is wrong: it accepts "([)]" because the counts balance even though the nesting does not. The snippet returned True for "()[]{}", "{[]}", "" and "a(b)c", and False for "([)]", "((" and ")(". O(n) time, O(n) space.
Python
1defbalanced(s):2 pairs ={")":"(","]":"[","}":"{"}3 stack =[]4for c in s:5if c in"([{":6 stack.append(c)7elif c in pairs:8ifnot stack or stack.pop()!= pairs[c]:9returnFalse10returnnot stack # leftovers mean unclosed brackets
For each day's temperature, return how many days you wait for a warmer one (0 if none). The array has a million entries, so the O(n^2) scan forward from each day is out.
MediumLinked Lists, Stacks, Queues and Heaps
Sample Answer
Use a monotonic stack of indices whose temperatures are non-increasing from bottom to top. These are days still waiting for an answer. When today is warmer than the day on top, today is that day's answer: pop it and record the gap, and repeat while the condition holds. Then push today. Each index is pushed once and popped at most once, so the total work is O(n) even with the inner while, and space is O(n) in the worst case (a strictly falling series). For [73, 74, 75, 71, 69, 72, 76, 73] it returned [1, 1, 4, 2, 1, 1, 0, 0]. Use strict < so equal temperatures do not count as warmer: [5, 5, 5] returns all zeros.
Python
1defdays_until_warmer(temps):2 ans, stack =[0]*len(temps),[]# stack: indices, temps not increasing3for i, t inenumerate(temps):4while stack and temps[stack[-1]]< t:5 j = stack.pop()# i is j's first warmer day6 ans[j]= i - j
7 stack.append(i)8return ans
Given bar heights of a histogram, find the area of the largest rectangle that fits under it. The interviewer expects O(n) and will ask you to justify it.
HardLinked Lists, Stacks, Queues and Heaps
Sample Answer
For each bar, the best rectangle using its full height extends left and right until a shorter bar. A stack of increasing heights finds both edges in one pass. When the current bar h is not taller than the top, the top bar cannot extend past i, so pop it and score height * (i - start). The popped bar's start is inherited by the current bar, because the current bar can extend left over everything taller that was just popped. Appending a 0 as a sentinel flushes the stack at the end, which avoids a second cleanup loop. Each bar is pushed and popped once: O(n) time and space. It returned 10 for [2, 1, 5, 6, 2, 3] and matched an O(n^2) brute force on 500 random inputs.
Python
1deflargest_rectangle(heights):2 stack, best =[],0# (start index, height), heights increasing3for i, h inenumerate(heights +[0]):# the 0 flushes the stack at the end4 start = i
5while stack and stack[-1][1]>= h:6 start, height = stack.pop()# this bar can't extend past i7 best =max(best, height *(i - start))8 stack.append((start, h))# h extends left to start9return best
A stream of a few billion request latencies arrives from a log, and you need the 100 largest. The stream does not fit in memory. What structure do you use, and what are the costs?
MediumLinked Lists, Stacks, Queues and Heaps
Sample Answer
Keep a min-heap of size k. The root is the smallest of the current top k, so a new value only matters if it beats the root, and heapq.heapreplace swaps it in for O(log k). That is O(n log k) time and O(k) memory, which works on a stream. Sorting is O(n log n) and needs everything in memory. A max-heap of all n values also needs O(n) memory. The direction trips people up: for the largest k you want a min-heap, because you need quick access to the one to evict. heapq.nlargest does the same job, and the snippet agreed with it on 300 random tests. Guard k = 0: without the check, heap[0] raised IndexError in testing. For an in-memory array, quickselect gives O(n) average time.
Python
1import heapq
23deftop_k(stream, k):4if k <=0:5return[]6 heap =[]# min-heap of the k largest so far7for x in stream:8iflen(heap)< k:9 heapq.heappush(heap, x)10elif x > heap[0]:# beats the smallest of the top k11 heapq.heapreplace(heap, x)12returnsorted(heap, reverse=True)
Trees and graphs carry the most weight in mid-level and senior coding rounds, because they combine recursion, a choice of traversal and a visited rule. Many problems never say "graph": a grid, a list of course prerequisites or a set of friendships is a graph once you name the nodes and edges.
The idea that matters most: pick the traversal from the question. BFS gives shortest paths when every edge costs the same, DFS explores structure, topological sort orders dependencies, union-find answers connectivity, and Dijkstra handles non-negative weights. Then decide when a node is marked visited.
Trees and Graphs
Return the values of a binary tree grouped by level, top to bottom. A candidate uses a list as the queue with pop(0). What would you change, and how do you know where each level ends?
EasyTrees and Graphs
Sample Answer
BFS with collections.deque. list.pop(0) shifts every remaining element, so it is O(n) per pop and the traversal becomes O(n^2) on a wide tree, while deque.popleft() is O(1). To split levels, read len(q) at the start of each round: at that moment the queue holds exactly the current level, so pop that many nodes and push their children for the next round. No depth tags or sentinel nodes are needed. O(n) time and O(w) space, where w is the widest level (up to about n / 2 for a complete tree). Return [] for an empty tree. On a five-node tree it returned [[3], [9, 20], [15, 7]].
Python
1from collections import deque
23deflevel_order(root):4if root isNone:5return[]6 out, q =[], deque([root])7while q:8 level =[]9for _ inrange(len(q)):# exactly the nodes of this level10 node = q.popleft()# O(1); list.pop(0) is O(n)11 level.append(node.val)12 q.extend(c for c in(node.left, node.right)if c)13 out.append(level)14return out
Check whether a binary tree is a valid binary search tree. A candidate compares each node only with its two children and passes all their tests. Give a tree that breaks it, and a correct check.
MediumTrees and Graphs
Sample Answer
Root 5, left child 1, right child 6, and 6 has a left child 4. Every parent-child pair is in order, so the local check returns True, but 4 sits in the right subtree of 5 and must be greater than 5. The BST rule is about all ancestors, so pass down an open interval: going left tightens the upper bound to the node's value, going right tightens the lower bound. That returned False on the example, and False on a duplicate (2 with left child 2) because the bounds are strict. An in-order traversal that checks strictly increasing values is the other standard answer. Both are O(n). The recursion is O(h) deep, and a 5,000-node chain raised RecursionError, so mention an iterative stack for skewed trees.
Python
1defis_bst(node, lo=float("-inf"), hi=float("inf")):2if node isNone:3returnTrue4ifnot lo < node.val < hi:# every ancestor's bound, not just the parent5returnFalse6return(is_bst(node.left, lo, node.val)and7 is_bst(node.right, node.val, hi))
A warehouse robot moves up, down, left or right on a grid with shelves (#) and open floor (.). Return the fewest moves from start to goal, or -1. Why is BFS correct here, and when do you mark a cell visited?
MediumTrees and Graphs
Sample Answer
Every move costs 1, so BFS settles cells in order of distance: everything at distance d is dequeued before anything at d + 1, and the first time you reach the goal is the shortest. DFS gives a path, not the shortest one. Mark a cell when you enqueue it, by writing its distance, not when you pop it. If you wait until the pop, the same cell can be queued by several neighbors: on an empty 30 by 30 grid, marking on pop pushed 1,741 cells versus 900 when marking on push. O(rows times cols) time and space. Check the start equals goal case (returns 0) and a blocked goal (returns -1).
Python
1from collections import deque
2defshortest_path(grid, start, goal):3 rows, cols =len(grid),len(grid[0])4 dist, q ={start:0}, deque([start])5while q:6 r, c = q.popleft()7if(r, c)== goal:8return dist[r, c]9for nr, nc in((r +1, c),(r -1, c),(r, c +1),(r, c -1)):10if(0<= nr < rows and0<= nc < cols and grid[nr][nc]=="."11and(nr, nc)notin dist):12 dist[nr, nc]= dist[r, c]+1# mark when enqueued, not when popped13 q.append((nr, nc))14return-1
Given n courses and pairs (course, prerequisite), return an order to take them all, or an empty list if it is impossible. Explain how your algorithm detects the impossible case.
MediumTrees and Graphs
Sample Answer
Topological sort with Kahn's algorithm. Count each course's incoming edges, start a queue with every course that has none, and repeatedly take one, append it to the order and decrement its dependents; any that reach zero join the queue. If there is a cycle, the courses in it never reach in-degree zero, so the order comes out shorter than n. That length check is the whole cycle detection. O(V + E) time and space. It returned [0, 1, 2, 3] for a diamond of four courses, [] for two courses that require each other and [] for a course that lists itself. Watch the edge direction: the pair is (course, prerequisite), so the edge runs from prerequisite to course. Reversing it gives a valid-looking but backwards order.
Python
1from collections import deque
2defcourse_order(n, prereqs):# (course, prerequisite) pairs3 graph, indeg =[[]for _ inrange(n)],[0]* n
4for course, pre in prereqs:5 graph[pre].append(course)6 indeg[course]+=17 q, order = deque(i for i inrange(n)if indeg[i]==0),[]8while q:9 u = q.popleft()10 order.append(u)11for v in graph[u]:12 indeg[v]-=113if indeg[v]==0: q.append(v)14return order iflen(order)== n else[]# short means a cycle
A social app receives friendship edges one at a time and must report after each one whether it joined two groups or connected people who were already linked. There are millions of edges. What structure do you use?
MediumTrees and Graphs
Sample Answer
Union-find (disjoint set union). find follows parent pointers to a root that names the group; union links two roots. Two optimizations make it fast: union by size, which attaches the smaller tree under the larger one, and path compression (here path halving), which shortens paths during find. Together they give amortized O(α(n)) per operation, where α is the inverse Ackermann function and at most 4 for any practical input size. Without them a chain of unions builds an O(n) deep tree. union returning False means both ends were already connected, which is the redundant-edge and cycle signal. For edges (0,1), (1,2), (3,4), (0,2), (2,4) on 5 nodes it returned True, True, True, False, True and ended with one group. BFS per query would cost O(V + E) each time.
Python
1classDSU:2def__init__(self, n):3 self.parent, self.size =list(range(n)),[1]* n
4deffind(self, x):5while self.parent[x]!= x:6 self.parent[x]= self.parent[self.parent[x]]# path halving7 x = self.parent[x]8return x
9defunion(self, a, b):10 ra, rb = self.find(a), self.find(b)11if ra == rb:returnFalse# already connected: a cycle edge12if self.size[ra]< self.size[rb]: ra, rb = rb, ra
13 self.parent[rb], self.size[ra]= ra, self.size[ra]+ self.size[rb]14returnTrue
Implement shortest travel times from one warehouse to every other over roads with non-negative travel times. Python's heapq has no decrease-key. How do you handle that, and what is the complexity?
MediumTrees and Graphs
Sample Answer
Dijkstra with lazy deletion. When an edge improves a node's distance, push a new (distance, node) pair instead of updating the old one. When a pair comes off the heap with a distance larger than the recorded one, it is stale, so skip it. Every edge pushes at most once, so the heap holds O(E) entries and the run is O((V + E) log V) time, using log E = O(log V). The skip check is what keeps a node from relaxing its edges twice. On a four-node graph where the direct edge A to B costs 4 and the route through C costs 3, it returned {A: 0, B: 3, C: 1, D: 4}. Unreached nodes stay out of the dict.
Python
1import heapq
23defdijkstra(graph, src):# graph[u] = [(v, weight), ...], weights >= 04 dist, heap ={src:0},[(0, src)]5while heap:6 d, u = heapq.heappop(heap)7if d > dist[u]:8continue# stale entry: u was already improved9for v, w in graph.get(u,[]):10if d + w < dist.get(v,float("inf")):11 dist[v]= d + w
12 heapq.heappush(heap,(d + w, v))13return dist
Your routing service adds refund edges with negative cost, and the Dijkstra code starts returning wrong totals. Explain why on a small example and say what you would use instead.
HardTrees and Graphs
Sample Answer
Dijkstra settles the closest unsettled node and assumes nothing found later can beat it, because adding an edge never makes a path shorter. A negative edge breaks that. Take A to B costing 5, A to C costing 2, B to C costing -4, and C to D costing 1. A version with a settled set finalizes C at 2 before it ever pops B, so it returned C = 2 and D = 3, while the true answers are 1 and 2. The lazy heap version re-pushes C and happens to recover on this graph, but nodes can be processed many times and the worst case is exponential. Bellman-Ford relaxes every edge V - 1 times, O(VE), and one more pass that still improves something proves a negative cycle.
Python
1defbellman_ford(nodes, edges, src):# edges = [(u, v, weight), ...]2 dist ={u:float("inf")for u in nodes}3 dist[src]=04for _ inrange(len(nodes)-1):# a shortest path has at most n - 1 edges5for u, v, w in edges:6if dist[u]+ w < dist[v]:7 dist[v]= dist[u]+ w
8ifany(dist[u]+ w < dist[v]for u, v, w in edges):9raise ValueError("negative cycle reachable from the source")10return dist
Dynamic programming separates candidates more than any other topic, because the hard part is not the code. It is choosing a state that captures everything the future depends on, and writing the transition. Greedy questions test the opposite skill: knowing when a local choice is provably safe.
The idea that matters most: define the state in one sentence ("best[i] is the most value using the first i houses") before writing code. For greedy, either state the exchange argument or look for a small counterexample, and prefer the counterexample hunt first, because it is faster.
Dynamic Programming and Greedy Algorithms
You can rob houses along a street but never two neighbors. Return the most money. A candidate sums the even-indexed and odd-indexed houses and takes the larger. Show that it fails, then solve it in O(1) space.
EasyDynamic Programming and Greedy Algorithms
Sample Answer
Alternating sums assume the best plan skips exactly one house each time. For [2, 1, 1, 2] the best is the two ends, 4, but alternating gives 3. The state is two numbers: the best total if the last house considered was robbed (take) and if it was skipped (skip). Robbing house x needs the previous one skipped, so take = skip + x. Skipping x keeps the better of both, so skip = max(take, skip). Update both in one tuple assignment so the new take uses the old skip. Each step looks back one house, so two variables replace the table: O(n) time, O(1) space. It returned 12 for [2, 7, 9, 3, 1], 0 for an empty street, and matched brute force on 300 random streets.
Python
1defrob(houses):2 take, skip =0,0# best so far if the last house was robbed / skipped3for x in houses:4 take, skip = skip + x,max(take, skip)5returnmax(take, skip)
A payments team gives change with "largest coin first". With coins 1, 3 and 4 a customer reports getting three coins for 6 cents. Explain, and write a function that always returns the fewest coins.
MediumDynamic Programming and Greedy Algorithms
Sample Answer
Greedy takes 4, then 1 and 1, three coins, while 3 + 3 uses two. Greedy is safe only for so-called canonical coin systems: a DP check found no counterexample with 1, 5, 10 and 25 up to 500 cents, but coins 1, 3 and 4 fail at 6, 10 and 14. The DP state is best[a], the fewest coins that sum to a, with best[0] = 0 and best[a] = 1 + min(best[a - c]) over coins that fit. Unreachable amounts stay infinite and return -1, as with coins [2] and amount 3. That is O(amount times coins) time and O(amount) space. It is pseudo-polynomial: the cost grows with the amount's value, not its number of digits.
Python
1defmin_coins(coins, amount):2 INF =float("inf")3 best =[0]+[INF]* amount # best[a] = fewest coins summing to a4for a inrange(1, amount +1):5for c in coins:6if c <= a and best[a - c]+1< best[a]:7 best[a]= best[a - c]+18return best[amount]if best[amount]< INF else-1
You wrote a memoized recursive solution with functools.cache and it is correct, but it crashes on the largest test case. The interviewer asks you to convert it to tabulation. Why does it crash, and when is each style better?
MediumDynamic Programming and Greedy Algorithms
Sample Answer
Memoization keeps the recursion. ways(n) calls ways(n - 1) before anything returns, so the call stack is n frames deep, and with CPython's default limit of 1000, ways(1000) raised RecursionError in testing while ways(999) worked. Raising it with sys.setrecursionlimit is a patch: the depth still grows with n, and the Python docs warn that a limit set too high can crash the interpreter. Tabulation fills answers from the base cases upward in a loop, so there is no recursion, and when each answer depends only on the last two, two variables replace the table: ways_table(5000) returned a 1,045-digit number. Memoization is still the better first draft: it only computes the states you reach and maps directly onto the recurrence.
Python
1from functools import cache
23@cache4defways(n):# top-down: recursion n frames deep5return1if n <=1else ways(n -1)+ ways(n -2)67defways_table(n):# bottom-up: a loop, two variables8 a, b =1,19for _ inrange(n -1):10 a, b = b, a + b
11return b
A spell checker needs the minimum number of single-character inserts, deletes and replacements to turn one word into another. Write it, then cut the memory from O(mn) to O(n).
HardDynamic Programming and Greedy Algorithms
Sample Answer
The state is D[i][j], the distance between the first i characters of a and the first j of b. The base row and column are j and i: building a prefix from nothing costs one insert per character. Each cell is the minimum of a delete (D[i-1][j] + 1), an insert (D[i][j-1] + 1) and a replace or free match (D[i-1][j-1] + (a[i-1] != b[j-1])). Row i reads only row i - 1 and earlier cells of row i, so two rows are enough: O(mn) time, O(n) space, or O(min(m, n)) if you swap so that b is the shorter word. It returned 3 for "horse" and "ros" and 5 for "intention" and "execution". The trade-off: with only two rows you cannot trace back the actual edits.
Python
1defedit_distance(a, b):2 prev =list(range(len(b)+1))# row for a[:0]: insert j chars3for i, ca inenumerate(a,1):4 cur =[i]+[0]*len(b)5for j, cb inenumerate(b,1):6 cur[j]=min(prev[j]+1,# delete ca7 cur[j -1]+1,# insert cb8 prev[j -1]+(ca != cb))# replace, or free match9 prev = cur
10return prev[-1]
Meeting requests are intervals [start, end). Remove the fewest so the rest do not overlap. Pick a greedy rule and prove it is safe; the interviewer will propose "earliest start" and "shortest first" as alternatives.
MediumDynamic Programming and Greedy Algorithms
Sample Answer
Sort by end time and keep each meeting that starts at or after the last kept end. Exchange argument: take any optimal schedule and look at its first meeting. The meeting that ends earliest finishes no later than that one, so swapping it in conflicts with nothing else, and the schedule stays optimal. Repeat on the rest. The alternatives break on tiny inputs. Earliest start keeps [1, 10) and loses both [2, 3) and [4, 5), so it removes 2 where 1 is enough. Shortest first picks [4, 7) from [1, 5), [4, 7), [6, 10) and then blocks both others. O(n log n) for the sort. The function matched a brute force over all subsets on 400 random inputs. Use >= because touching intervals do not overlap.
Python
1defmin_removals(intervals):2 kept, end =0,float("-inf")3for s, e insorted(intervals, key=lambda iv: iv[1]):# earliest end first4if s >= end:# half-open: touching is allowed5 kept, end = kept +1, e
6returnlen(intervals)- kept
A 0/1 knapsack (each item used at most once) solution uses a one-dimensional array but returns 6 for a single item of weight 2 and value 3 with capacity 4. Find the bug.
HardDynamic Programming and Greedy Algorithms
Sample Answer
The inner loop runs over capacity forward. With one array, best[c - weight] has to mean "before this item was considered". Going upward, best[2] is already updated with the item when you compute best[4], so the item gets used twice, which solves the unbounded knapsack and returns 6. Looping capacity from high to low reads only values from the previous item, giving 3. That loop direction is the whole difference between 0/1 and unbounded in the space-reduced form, and it is worth saying explicitly. O(n times capacity) time and O(capacity) space, pseudo-polynomial like coin change. On items (1,1), (3,4), (4,5), (5,7) with capacity 7 it returned 9, and it matched brute force on 300 random cases.
Python
1defknapsack(items, cap):# items = [(weight, value), ...]2 best =[0]*(cap +1)# best[c] = top value within capacity c3for weight, value in items:4for c inrange(cap, weight -1,-1):# backward: each item used once5 best[c]=max(best[c], best[c - weight]+ value)6return best[cap]
How to Prepare for Data Structures and Algorithms Interviews
State the cost of every line, not just the loops
Before you say a complexity, read each line and ask what it does for you: membership on a list, a slice, sorted, string += and list.pop(0) are all O(n). Practice by annotating old solutions line by line. The Time and space complexity lesson covers these hidden loops, and Hash maps and sets shows when a set removes one.
Learn windows and prefix sums as one decision
Most subarray questions come down to one choice: a sliding window when the condition moves one way as the window grows, prefix sums with a hash map when values can be negative. Solve the same problem both ways once so the precondition sticks. Work through Variable-size windows and then Count subarrays with a hash map.
Write the monotonic stack until the pop rule is automatic
Next greater element, daily temperatures, histogram area and sliding-window maximum all use the same loop: pop while the new value breaks the order, record answers for what you pop, then push. Get comfortable explaining why each index is popped at most once. The Monotonic stacks and Sliding-window maximum lessons build both versions.
Name the graph algorithm from the edge weights
Unweighted edges mean BFS, dependencies mean topological sort, connectivity under added edges means union-find, non-negative weights mean Dijkstra, and negative weights mean Bellman-Ford. Say which one and why before you code. Topological ordering and Shortest paths cover the cases interviewers lean on most, including the negative-edge failure.
Try to break a greedy rule before you defend it
Spend two minutes hunting a counterexample on inputs of size two or three, or write a brute force that checks every option on small inputs. If none turns up, state the exchange argument. When greedy fails, the fix is usually DP: define the state in one sentence, then pick memoization or a table. See When greedy fails, Repeated subproblems and memoization and Binary search on the answer for the pattern that pairs a greedy check with binary search.
How Ready Are You for Data Structures and Algorithms Interviews?
1 / 6
Complexity
A loop runs n times and each pass checks x in seen, where seen is a list that grows to n items. What is the time complexity?
Frequently Asked Questions
Are data structures and algorithms questions asked in data science interviews?
Often, but at a lighter level than for software engineers. Many data science loops include one coding round with an easy or medium array, string or hash map problem in Python, and some add SQL alongside it. Machine learning engineer and data engineer loops usually go further, into trees, graphs, heaps and sometimes dynamic programming. Check the recruiter's description of the coding round: if it says "general coding" or "algorithms", prepare as a software engineer would.
How long does it take to prepare for a data structures and algorithms interview?
With a computer science background and some recent practice, four to six weeks of steady work (about an hour a day) is typical. Starting from scratch, plan on two to three months. Spend the first part learning one pattern at a time, such as hashing, windows, stacks or BFS, and the last two weeks doing timed mixed problems where you must recognize the pattern yourself. Recognizing the pattern is the skill interviews test.
Which programming language should I use in a coding interview?
Use the language you write fastest and most correctly. Python is the most common choice because it is short and has a deque, heapq, Counter and bisect in the standard library. Know its costs, though: list.pop(0) and slicing are O(n), recursion stops at a default depth of 1000, and heapq is a min-heap only. Java and C++ are fine choices too, but watch integer overflow on large sums.
How many practice problems do I need to solve before interviewing?
Breadth of patterns matters more than the count. Around 100 to 150 well-chosen problems usually cover the patterns that come up: hashing, two pointers, sliding windows, prefix sums, stacks, binary search, BFS and DFS, topological sort, union-find, heaps, intervals, greedy and dynamic programming. Solving each one, then re-solving it a week later without notes, does more than doing 400 problems once. Track the ones you missed and the reason why.
Do I really need dynamic programming for coding interviews?
For software engineer and machine learning engineer roles at larger companies, expect at least the one-dimensional and grid problems: climbing stairs, house robber, coin change, longest common subsequence and edit distance. Harder interval or bitmask DP is rarer. The skill being tested is defining a state and a recurrence, then choosing memoization or a table and reducing space. Data science and analytics roles ask for DP far less often.
Is it okay to start with a brute-force solution in an interview?
Yes, as long as you say it is a starting point and give its complexity. Stating the brute force shows you understand the problem and gives you a baseline to improve on and test against. Do not spend long coding it, though. Explain it in a sentence or two, then name the bottleneck, such as a repeated scan or a recomputed subproblem, and pick the structure that removes it. Interviewers score that reasoning heavily.
Written by
Dan Lee
Data & AI Lead
Dan is a seasoned data scientist and ML coach with 10+ years of experience at Google, PayPal, and startups. He has helped candidates land top-paying roles and offers personalized guidance to accelerate your data career.