Data Structures and Algorithms Interview Questions

Dan Lee's profile image
Dan LeeData & AI Lead
Last update
Data Structures and Algorithms Interview Questions

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.

Software EngineerMachine Learning EngineerData EngineerData ScientistQuantitative Developer

Complexity Analysis and Hidden Costs

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
1def dedupe_slow(items):
2    out = []
3    for x in items:
4        if x not in out:          # scans out: O(n) per check
5            out.append(x)
6    return out
7
8def dedupe(items):
9    seen, out = set(), []
10    for x in items:
11        if x not in seen:         # hash lookup: O(1) on average
12            seen.add(x)
13            out.append(x)
14    return out
Learn this in the Data Structures & Algorithms course

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.

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
1def two_sum(nums, target):
2    seen = {}                        # value -> index
3    for i, x in enumerate(nums):
4        if target - x in seen:       # check before inserting x
5            return seen[target - x], i
6        seen[x] = i
7    return None
Learn this in the Data Structures & Algorithms course

Linked Lists, Stacks, Queues and Heaps

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
1class Node:
2    def __init__(self, val, next=None):
3        self.val, self.next = val, next
4
5def reverse(head):
6    prev = None
7    while head:
8        nxt = head.next          # save it before we overwrite it
9        head.next = prev
10        prev, head = head, nxt
11    return prev                  # new head (None for an empty list)
Learn this in the Data Structures & Algorithms course

Trees and Graphs

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
2
3def level_order(root):
4    if root is None:
5        return []
6    out, q = [], deque([root])
7    while q:
8        level = []
9        for _ in range(len(q)):          # exactly the nodes of this level
10            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)
14    return out
Learn this in the Data Structures & Algorithms course

Dynamic Programming and Greedy Algorithms

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
1def rob(houses):
2    take, skip = 0, 0       # best so far if the last house was robbed / skipped
3    for x in houses:
4        take, skip = skip + x, max(take, skip)
5    return max(take, skip)
Learn this in the Data Structures & Algorithms course

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.

Dan Lee's profile image

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.

Connect on LinkedIn