Data Structures and Algorithms Interview Questions

Data structures and algorithms interview questions look endless, but most of them are built from a small number of patterns. Interviewers are rarely checking whether you have seen a particular problem before. They want to see whether you can recognise which structure fits, explain the trade-off, write working code and test it.

Google’s preparation guide for its software engineering internship candidates spells this out: explain your thought process throughout, ask clarifying questions, know the complexity of your algorithm and how to improve it, and test your own code. Its list of topics to review covers trees and traversals, hash tables, heaps and priority queues, graphs with breadth-first and depth-first search, at least one O(n log n) sort, stacks, arrays, linked lists and recursion. The questions below are organised around those topics.

Each example shows the question, the pattern behind it, an annotated solution in Python and the follow-up you should expect. The problems are illustrative and written for this guide.

First, know what your language’s structures cost

Conceptual questions often start here: “What is the cost of looking up a key in a dictionary?” Answering with your language’s actual behaviour shows real experience. In CPython, according to the Python documentation:

Operation	Typical cost	Watch out for
`list[i]`, `list.append(x)`, `list.pop()`	O(1) (append is amortised)	A single append can be O(n) when the list resizes
`list.pop(0)`, `list.insert(0, x)`	O(n)	Every other element has to move
`x in list`	O(n)	A linear scan, easy to hide inside a loop
`key in dict`, `dict[key] = v`, `x in set`	O(1) on average	O(n) in the worst case, if every key hashes to the same value
`deque.appendleft`, `deque.popleft`	About O(1) at either end	Indexing into the middle of a deque is O(n)
`list.sort()`	O(n log n)	Only O(n) comparisons if the input is already sorted or reverse-sorted

A common trap: using a list as a queue with pop(0) turns an O(n) breadth-first search into O(n squared). Use collections.deque instead.

Data structures and algorithms interview questions for freshers

Graduate and junior interviews tend to test whether you can pick the right basic structure and write clean, correct code. These five cover the patterns that appear most often.

1. “Given a list of numbers and a target, return the indices of two numbers that add up to the target.”

Pattern: hash map for constant-time lookups.

The brute-force answer checks every pair, which is O(n squared). Say that first, then improve it: as you walk through the list, store each number’s index in a dictionary and check whether the complement is already there.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return None

Complexity: O(n) time on average, O(n) extra space.

Likely follow-up: “What if the list is sorted and you can’t use extra memory?” Answer: two pointers, one at each end, moving inwards depending on whether the sum is too small or too large. O(n) time, O(1) space.

2. “Check whether a string of brackets is balanced.”

Pattern: stack, last in, first out.

def balanced(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

What the interviewer is checking: the two edge cases. A closing bracket with an empty stack, and leftover opening brackets at the end. Mention both before you are asked.

3. “Reverse a singly linked list.”

Pattern: pointer manipulation.

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev, head = head, nxt
    return prev

Talk through it with a three-node example on paper. Interviewers like to see you trace your own code. Expect a follow-up asking for a recursive version, and a question about its cost: recursion uses O(n) call-stack space, while the loop uses O(1).

4. “Find the shortest path from the top-left to the bottom-right of a grid, where 1 is a wall.”

Pattern: breadth-first search on an unweighted graph.

from collections import deque

def shortest_path(grid):
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] or grid[rows-1][cols-1]:
        return -1
    q = deque([(0, 0, 0)])            # row, col, distance
    seen = {(0, 0)}
    while q:
        r, c, d = q.popleft()
        if (r, c) == (rows-1, cols-1):
            return d
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols \
               and not grid[nr][nc] and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Why BFS, not DFS? BFS explores in order of distance, so the first time it reaches the target is the shortest route. DFS would find a path, not necessarily the shortest. Being able to say this in one sentence is the conceptual half of the question.

5. “Search a sorted array for a value.”

Pattern: binary search. It sounds easy, but off-by-one errors are common, which is why interviewers still ask it.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Test it out loud on an empty array, a one-element array and a target smaller than everything. Those three cases catch most bugs.

Data structures and algorithms interview questions for experienced candidates

Experienced candidates get problems where the right structure is less obvious, plus design questions where you combine structures. Interviewers also expect you to discuss trade-offs without prompting.

6. “Return the k most frequent words in a large list.”

Pattern: counting plus a heap.

import heapq
from collections import Counter

def top_k(words, k):
    counts = Counter(words)
    return heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])

The trade-off to explain: sorting all distinct words costs O(m log m). Keeping a heap of size k costs O(m log k), which is better when k is small. The Python documentation makes the same point: nlargest works best for small n, and for larger values sorting is more efficient. Python’s heapq is a min-heap, with the smallest item always at heap[0]; dedicated max-heap functions were added in Python 3.14.

Likely follow-up: “What if the words arrive as a stream and don’t fit in memory?” Discuss approximate counting, or splitting the data by hash so each part can be counted separately and merged.

7. “Merge overlapping intervals.”

Pattern: sort, then sweep.

def merge(intervals):
    out = []
    for start, end in sorted(intervals):
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

The sort dominates at O(n log n). Ask whether intervals that only touch, such as [1, 3] and [3, 5], should merge. That clarifying question is exactly what interviewers want to hear.

8. “Design an LRU cache with O(1) get and put.”

Pattern: combine a hash map with a doubly linked list.

The hash map gives O(1) lookup by key. The linked list keeps items in order of use, so you can move an item to the front and remove the least recently used item from the back in O(1). In Python you can mention that collections.OrderedDict provides this combination, but most interviewers will ask you to build the linked list yourself to see that you understand why both structures are needed.

Follow-ups to prepare for: thread safety, what happens under memory pressure, and how you would make the cache expire entries after a time limit.

9. “Given course prerequisites, can all courses be completed?”

Pattern: directed graph, cycle detection, topological sort.

Build an adjacency list and count each course’s incoming edges. Repeatedly take courses with no remaining prerequisites (Kahn’s algorithm). If you process every course, there is no cycle; if some are left, there is one.

from collections import deque, defaultdict

def can_finish(n, prereqs):
    graph, indeg = defaultdict(list), [0] * n
    for course, pre in prereqs:
        graph[pre].append(course)
        indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        node = q.popleft()
        done += 1
        for nxt in graph[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return done == n

O(V + E) time. Explain why you chose an adjacency list over a matrix: for a sparse graph it uses far less memory.

10. “What is the fewest coins needed to make an amount?”

Pattern: dynamic programming.

Start by showing why the greedy approach (always take the largest coin) fails for some coin sets. With coins of 1, 3 and 4, greedy makes 6 as 4 + 1 + 1, but 3 + 3 uses fewer coins. Then build a table where best[a] is the fewest coins for amount a.

def coin_change(coins, amount):
    INF = float('inf')
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else -1

O(amount multiplied by number of coins) time. Saying “I’ll define the subproblem, the recurrence and the base case” before writing any code shows you know the method, not just this problem.

Conceptual questions to answer in two sentences

Interviewers often mix short conceptual checks into coding rounds. Practise answering each in two sentences or fewer:

Array or linked list? Arrays give O(1) access by index and are cache-friendly; linked lists allow O(1) insertion and removal once you hold a reference to the node, but access by position is O(n).
Why can a hash table be slow? If many keys collide, lookups degrade towards O(n); a good hash function and resizing keep the average close to O(1).
Quicksort or merge sort? Quicksort is usually fast in practice and sorts in place, but its worst case is O(n squared); merge sort is always O(n log n) and stable, but needs extra memory.
Why is building a heap O(n), not O(n log n)? Most nodes sit near the bottom of the tree and move only a short distance during heapify. Python’s documentation confirms that heapify runs in linear time.
When is recursion a bad idea? When the depth can grow with the input and risk a stack overflow, or when the same subproblems are recomputed many times without memoisation.

How to talk through any problem

Clarify. Input size, duplicates, negative numbers, empty input, expected output format.
State a brute-force answer and its cost. It proves you understand the problem and gives you a baseline.
Name the pattern and improve. “Repeated lookups suggest a hash map.” “Shortest path in an unweighted grid suggests BFS.”
Code steadily, narrating key decisions.
Test with small cases, including an edge case, by tracing the code rather than assuming it works.
State the final time and space complexity and one possible improvement.

Google’s guide says that in phone and video interviews you write code in real time in an interview coding document, so practise writing code without leaning on an IDE’s autocomplete.

Your CV should back up what you show in the interview. Name the languages you used, the scale you worked at and the performance gains you achieved. Our software engineer resume builder and these resume examples show how to phrase technical achievements concisely.

Frequently asked questions

Which data structures come up most in coding interviews?

Arrays and strings, hash maps and sets, stacks and queues, linked lists, trees, heaps and graphs. Google’s published preparation guide lists all of these, along with sorting and recursion.

Which language should I use for DSA interviews?

Use the language you know best, as long as the employer allows it. Know the costs of its built-in structures, for example which list operations in Python are O(1) and which are O(n).

How are DSA questions different for experienced candidates?

Experienced candidates get problems where the structure is less obvious, design questions that combine structures, such as an LRU cache, and follow-ups about scale, memory and concurrency.

Do I need to memorise solutions?

No. Memorising patterns is more useful than memorising problems. If you can recognise when to use a hash map, a heap, BFS or dynamic programming, you can handle problems you have not seen before.

What should I do if I get stuck?

Say what you have tried, return to the brute-force solution, and work through a small example by hand. Interviewers often give hints, and how you use a hint is part of the assessment.

Sources

Preparing for Google technical internship interviews (PDF) (Google)
Time complexity of operations on built-in types (Python Software Foundation)
heapq: Heap queue algorithm (Python Software Foundation)
collections: Container datatypes (Python Software Foundation)

Data Structures and Algorithms Interview Questions: Practical and Conceptual