Technical interviews reward clear thinking more than clever syntax. Before writing code, restate the problem, ask about edge cases, and work through a small example. Then write the simplest solution you can explain and test it with a few deliberate cases.
The questions below are a mixture of problems I have encountered and small exercises that are useful for practising common interview patterns. Try each one before opening the answer.
Lonely numbers
Given a list of integers, return every number that has no neighbour in the list. A number is lonely when the list contains neither number - 1 nor number + 1.
For example, [10, 3, 5, 11, 4] contains the lonely number 5: 4 is present, so it is not lonely; 10 is not lonely because 11 is present; and 3 is not lonely because 4 is present. The result is therefore an empty list. What would your function return for [10, 3, 5, 12]?
Show answer
def lonely_numbers(numbers: list[int]) -> list[int]:
"""Return numbers whose immediate neighbours are both absent."""
present = set(numbers)
return [
number
for number in numbers
if number - 1 not in present and number + 1 not in present
]
assert lonely_numbers([10, 3, 5, 12]) == [10, 3, 5, 12]
assert lonely_numbers([1, 2, 4, 6, 7]) == [4]
assert lonely_numbers([]) == []
The set gives constant-time average membership checks, so the time complexity is O(n) and the additional space complexity is O(n). If duplicate input values should appear only once in the answer, iterate over sorted(present) instead of numbers.
A stack of payment changes
Imagine that a set of payment changes is applied in groups. A group might contain several payments and refunds, but it should be undone as one unit. Design a structure that can:
- apply a group of changes;
- report the current balance; and
- undo the most recently applied group.
Assume that a payment has a positive amount and a refund has a negative amount. Undoing a group should restore the balance that existed before that group was applied.
Show answer
from dataclasses import dataclass
@dataclass(frozen=True)
class Change:
description: str
amount: int
class PaymentStack:
def __init__(self) -> None:
self._balance = 0
self._groups: list[tuple[Change, ...]] = []
@property
def balance(self) -> int:
return self._balance
def apply(self, changes: list[Change]) -> None:
group = tuple(changes)
self._groups.append(group)
self._balance += sum(change.amount for change in group)
def undo(self) -> bool:
"""Undo the latest group. Return False when there is nothing to undo."""
if not self._groups:
return False
group = self._groups.pop()
self._balance -= sum(change.amount for change in group)
return True
payments = PaymentStack()
payments.apply([
Change("order", 25),
Change("shipping", 5),
])
assert payments.balance == 30
payments.apply([Change("partial refund", -10)])
assert payments.balance == 20
assert payments.undo() is True
assert payments.balance == 30
assert payments.undo() is True
assert payments.balance == 0
assert payments.undo() is False
The important choice is to store each group as one item on a stack. The stack gives last-in, first-out behaviour, and undoing a group is the inverse of applying its total. Applying and undoing a group both take O(k) time for a group containing k changes; the history uses O(n) space for n stored changes.
In a production payment system, an undo would usually be represented by a compensating transaction rather than deleting history. The interview version is deliberately focused on the data structure.
Two Sum
Given a list of numbers and a target, return the indices of two different numbers that add up to the target. Assume that exactly one pair exists.
For example, [4, 7, 1, 9] with a target of 10 should return the indices for 1 and 9.
Show answer
def two_sum(numbers: list[int], target: int) -> tuple[int, int] | None:
"""Return the indices of two numbers whose sum is target."""
seen: dict[int, int] = {}
for index, number in enumerate(numbers):
complement = target - number
if complement in seen:
return seen[complement], index
seen[number] = index
return None
assert two_sum([4, 7, 1, 9], 10) == (2, 3)
assert two_sum([3, 3], 6) == (0, 1)
assert two_sum([1, 2, 3], 20) is None
Store values as you visit them. At each step, the dictionary answers whether the required complement has already appeared. This takes O(n) time and O(n) additional space, compared with O(nĀ²) time for checking every pair.
Overlapping intervals
Given a list of intervals, merge every pair that overlaps. For example, [(1, 3), (2, 5), (8, 10)] becomes [(1, 5), (8, 10)].
Show answer
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
if not intervals:
return []
merged: list[list[int]] = []
for start, end in sorted(intervals):
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return [(start, end) for start, end in merged]
assert merge_intervals([(1, 3), (2, 5), (8, 10)]) == [(1, 5), (8, 10)]
assert merge_intervals([(1, 4), (4, 7)]) == [(1, 7)]
assert merge_intervals([]) == []
Sorting by start means that the only interval that can overlap the current one is the last interval in merged. The sort makes the complexity O(n log n); the merge pass itself is O(n).
Binary search in a sorted list
Given a sorted list of numbers and a target, return the target's index or None if it is not present. The list can be large, so avoid scanning every item from left to right.
Show answer
def binary_search(numbers: list[int], target: int) -> int | None:
left = 0
right = len(numbers) - 1
while left <= right:
middle = (left + right) // 2
if numbers[middle] == target:
return middle
if numbers[middle] < target:
left = middle + 1
else:
right = middle - 1
return None
assert binary_search([1, 3, 5, 7, 9], 7) == 3
assert binary_search([1, 3, 5, 7, 9], 4) is None
assert binary_search([], 4) is None
Each comparison eliminates roughly half of the remaining search space, giving O(log n) time and O(1) additional space. If duplicates are allowed, clarify whether any matching index, the first index, or the last index is required.
A binary search tree for mixed insertions and retrievals
Design a structure that supports lots of intermixed insertions and retrievals. A binary search tree keeps values smaller than a node on its left and larger values on its right, allowing each lookup to discard half of the remaining tree when the tree is balanced.
Show answer
from dataclasses import dataclass
@dataclass
class Node:
value: int
left: "Node | None" = None
right: "Node | None" = None
class BinarySearchTree:
def __init__(self) -> None:
self.root: Node | None = None
def insert(self, value: int) -> None:
if self.root is None:
self.root = Node(value)
return
current = self.root
while True:
if value == current.value:
return # Ignore duplicates.
if value < current.value:
if current.left is None:
current.left = Node(value)
return
current = current.left
else:
if current.right is None:
current.right = Node(value)
return
current = current.right
def contains(self, value: int) -> bool:
current = self.root
while current is not None:
if value == current.value:
return True
current = current.left if value < current.value else current.right
return False
tree = BinarySearchTree()
for value in [8, 3, 10, 1, 6, 14]:
tree.insert(value)
assert tree.contains(6) is True
assert tree.contains(7) is False
For a balanced tree, insertion and lookup are both O(log n) on average. If values arrive in sorted order, this implementation degenerates into a linked list and becomes O(n). If predictable performance is important, use a self-balancing tree such as an AVL tree or a red-black tree, or use Python's built-in set when ordering is not part of the requirement.
Longest substring without repeating characters
Given a string, return the length of the longest substring that contains no repeated characters. For example, "abcabcbb" contains "abc", so the answer is 3.
Show answer
def longest_unique_substring(text: str) -> int:
last_seen: dict[str, int] = {}
window_start = 0
longest = 0
for index, character in enumerate(text):
if character in last_seen and last_seen[character] >= window_start:
window_start = last_seen[character] + 1
last_seen[character] = index
longest = max(longest, index - window_start + 1)
return longest
assert longest_unique_substring("abcabcbb") == 3
assert longest_unique_substring("bbbbb") == 1
assert longest_unique_substring("") == 0
Maintain a window whose contents are unique. When a repeated character appears, move the left edge just beyond its previous position. Every character is processed a constant number of times, giving O(n) time and O(k) space, where k is the number of distinct characters.
Valid parentheses and a minimum stack
These are two short stack exercises. First, determine whether brackets in a string are correctly matched and nested. Then design a stack that supports push, pop, and retrieving its smallest value in constant time.
Show answer
def valid_parentheses(text: str) -> bool:
matching = {")": "(", "]": "[", "}": "{"}
opening = set(matching.values())
stack: list[str] = []
for character in text:
if character in opening:
stack.append(character)
elif character in matching:
if not stack or stack.pop() != matching[character]:
return False
return not stack
assert valid_parentheses("{[()]}") is True
assert valid_parentheses("{[(])}") is False
assert valid_parentheses("") is True
class MinStack:
def __init__(self) -> None:
self._values: list[int] = []
self._minimums: list[int] = []
def push(self, value: int) -> None:
self._values.append(value)
minimum = min(value, self.minimum()) if self._minimums else value
self._minimums.append(minimum)
def pop(self) -> int:
if not self._values:
raise IndexError("pop from empty stack")
self._minimums.pop()
return self._values.pop()
def minimum(self) -> int:
if not self._minimums:
raise IndexError("minimum from empty stack")
return self._minimums[-1]
stack = MinStack()
stack.push(5)
stack.push(2)
stack.push(4)
assert stack.minimum() == 2
stack.pop()
assert stack.minimum() == 2
The bracket checker stores unmatched opening brackets and compares each closing bracket with the most recent one. The minimum stack keeps a second stack containing the minimum at every depth, so all operations take O(1) time. Both solutions use O(n) space in the worst case.
Number of islands
Given a grid containing "1" for land and "0" for water, count the number of islands. Land cells are connected horizontally or vertically, but not diagonally.
Show answer
def number_of_islands(grid: list[list[str]]) -> int:
if not grid:
return 0
rows, columns = len(grid), len(grid[0])
islands = 0
def visit(row: int, column: int) -> None:
if (
row < 0 or row >= rows
or column < 0 or column >= columns
or grid[row][column] != "1"
):
return
grid[row][column] = "0"
for row_change, column_change in ((1, 0), (-1, 0), (0, 1), (0, -1)):
visit(row + row_change, column + column_change)
for row in range(rows):
for column in range(columns):
if grid[row][column] == "1":
islands += 1
visit(row, column)
return islands
assert number_of_islands([
["1", "1", "0"],
["1", "0", "0"],
["0", "0", "1"],
]) == 2
assert number_of_islands([]) == 0
When an unvisited land cell is found, count one island and traverse all connected land, marking it as water as you go. Each cell is visited once, so the time complexity is O(rows * columns). This implementation mutates the input and uses recursion; an interview follow-up might ask you to preserve the grid or replace recursion with an explicit queue/stack.
Course schedule
There are num_courses courses numbered from 0 to num_courses - 1. Each prerequisite pair [course, prerequisite] means that prerequisite must be completed first. Return whether it is possible to complete every course.
Show answer
from collections import deque
def can_finish(
num_courses: int,
prerequisites: list[tuple[int, int]],
) -> bool:
graph: list[list[int]] = [[] for _ in range(num_courses)]
prerequisites_needed = [0] * num_courses
for course, prerequisite in prerequisites:
graph[prerequisite].append(course)
prerequisites_needed[course] += 1
ready = deque(
course
for course, count in enumerate(prerequisites_needed)
if count == 0
)
completed = 0
while ready:
course = ready.popleft()
completed += 1
for next_course in graph[course]:
prerequisites_needed[next_course] -= 1
if prerequisites_needed[next_course] == 0:
ready.append(next_course)
return completed == num_courses
assert can_finish(2, [(1, 0)]) is True
assert can_finish(2, [(1, 0), (0, 1)]) is False
assert can_finish(3, []) is True
This is Kahn's topological-sort algorithm. Start with courses that have no prerequisites, then remove their outgoing edges. If every course can be removed, there is no cycle. The time complexity is O(V + E) and the space complexity is also O(V + E).
Generating subsets and permutations
Given a list of distinct values, return every subset. This is a useful introduction to backtracking; a natural follow-up is to return every permutation instead.
Show answer
def subsets(values: list[int]) -> list[list[int]]:
result: list[list[int]] = []
def visit(index: int, chosen: list[int]) -> None:
if index == len(values):
result.append(chosen.copy())
return
visit(index + 1, chosen)
chosen.append(values[index])
visit(index + 1, chosen)
chosen.pop()
visit(0, [])
return result
def permutations(values: list[int]) -> list[list[int]]:
result: list[list[int]] = []
def visit(start: int) -> None:
if start == len(values):
result.append(values.copy())
return
for index in range(start, len(values)):
values[start], values[index] = values[index], values[start]
visit(start + 1)
values[start], values[index] = values[index], values[start]
visit(0)
return result
assert subsets([1, 2]) == [[], [2], [1], [1, 2]]
assert len(permutations([1, 2, 3])) == 6
At each item, the subset solution makes two choices: exclude it or include it. The permutation solution swaps each remaining value into the current position, then swaps it back when backtracking. There are 2^n subsets and n! permutations, so the output size itself determines the dominant time and space complexity.
A good interview habit
Once the happy path works, test the boundaries: an empty input, one item, duplicate values, negative values, and repeated operations. Explain the complexity and mention what you would change if the requirements became stricter. That discussion often demonstrates more than squeezing a few lines out of the implementation.