8 Problem-Solving Interview Questions with Checked Python Examples

These eight problem-solving questions exercise lookup, ordering, traversal, selection, system design, and binary-search invariants. Use them to practice explaining why an approach works, then change one constraint to check whether you understand its limits.

The coding examples below are original Python implementations with explicit contracts and small assertions. They teach general patterns; they are not copied solutions to the linked company questions. Some linked variants require different tie rules, return values, or implementations.

Microsoft's technical interview guidance emphasizes clarification, planning, coding, and testing. For each exercise, state the inputs and output first, explain a baseline, identify an invariant, and test a boundary before calling the answer complete. The Coding and Algorithms question bank provides related practice across these patterns.

1. Two Sum: preserve the right index information

Given integer values and a target, return two distinct zero-based indices whose values sum to the target. Our version returns the first matching right index encountered from left to right, using the earliest matching left index. It returns None if no pair exists and leaves the input unchanged.

def two_sum(values, target):
    first_index = {}
    for right, value in enumerate(values):
        complement = target - value
        if complement in first_index:
            return first_index[complement], right
        first_index.setdefault(value, right)
    return None

assert two_sum([3, 3], 6) == (0, 1)
assert two_sum([-4, 7, 2], 3) == (0, 1)
assert two_sum([5], 10) is None

Invariant: before processing position right, the map contains only earlier positions. Checking before insertion prevents using one element twice. Keeping the earliest position for each value makes this contract deterministic.

Expected time is O(n) and auxiliary space is O(n) under average constant-time hash operations. A quadratic baseline checks every distinct pair. If the input is already sorted, two pointers can use constant extra space; sorting an unsorted copy while preserving original indices has additional costs.

The public lexicographically smallest Two Sum pair prompt deliberately changes the contract. For [1, 4, 6, 9] and target 10, our function returns (1, 2), while the lexicographically smallest pair is (0, 3). Stopping at the first matching right index does not solve that variant.

Follow-up: return every distinct value pair. Explain whether duplicate input positions create duplicate outputs before changing the algorithm.

2. LRU cache: couple lookup with recency

A least-recently-used cache needs fast key lookup and fast recency changes. The usual manual design combines a hash map with a doubly linked list: the map points directly to nodes, and the list orders them by recency. Sentinel nodes simplify removal at the ends.

Python's OrderedDict operations provide an alternative when a library implementation is permitted. This version treats successful reads and writes as accesses. Missing reads return the caller's default, so stored None values remain usable with a distinct sentinel default.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        if type(capacity) is not int or capacity < 0:
            raise ValueError("capacity must be a nonnegative integer")
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key, default=None):
        if key not in self.data:
            return default
        self.data.move_to_end(key)
        return self.data[key]

    def put(self, key, value):
        if self.capacity == 0:
            return
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)

cache = LRUCache(2)
cache.put("A", 10)
cache.put("B", 20)
assert cache.get("A") == 10
cache.put("C", 30)
assert cache.get("B", "missing") == "missing"
assert list(cache.data) == ["A", "C"]

The oldest entry is at the beginning. Reading A makes B oldest, so inserting C evicts B. Updating an existing key must also refresh its recency. Capacity zero stores nothing.

Average get and put time is O(1) for ordinary hashable keys, with O(capacity) stored entries. This teaching class is not thread-safe and implements neither TTL nor weighted capacity. Concurrency requires protecting the combined lookup, update, and eviction operation; a lock around only one dictionary access is insufficient.

Use the public fixed-capacity LRU object-design prompt for a manual-design discussion. The Java Collections article offers language-specific collection trade-offs.

3. Merge intervals: define what touching means

Our input consists of closed intervals with valid endpoints start <= end. Touching intervals merge: [1, 3] and [3, 5] become [1, 5]. A half-open scheduling contract may make a different choice.

def merge_intervals(intervals):
    merged = []
    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 merged

assert merge_intervals([(8, 10), (1, 3), (2, 6)]) == [[1, 6], [8, 10]]
assert merge_intervals([(1, 10), (2, 3), (4, 5)]) == [[1, 10]]
assert merge_intervals([(1, 3), (3, 5)]) == [[1, 5]]
assert merge_intervals([]) == []

Invariant: after each step, the accumulated intervals are sorted, disjoint, and represent exactly the processed input. Sorting makes it sufficient to compare the next interval with the last accumulated one. Taking the maximum end prevents a contained interval from shrinking the result.

Time is O(n log n). This Python implementation creates a sorted copy and output intervals, using O(n) space. It does not mutate the caller's intervals. Do not describe it as constant-space merely because the sweep itself tracks one current interval.

The closed-interval merging prompt matches the boundary decision. A meeting-room-count question asks for maximum simultaneous occupancy, which is a different output from the merged union.

4. Number of Islands: mark when scheduling traversal

Count connected components of land in a rectangular grid of strings containing 0 and 1. Land connects horizontally and vertically. The function below preserves the grid and uses an explicit stack, avoiding recursion-depth limits.

def count_islands(grid):
    rows = len(grid)
    cols = len(grid[0]) if rows else 0
    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")
    seen = set()
    islands = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] != "1" or (row, col) in seen:
                continue
            islands += 1
            seen.add((row, col))
            stack = [(row, col)]
            while stack:
                r, c = stack.pop()
                for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
                    if (0 <= nr < rows and 0 <= nc < cols
                            and grid[nr][nc] == "1" and (nr, nc) not in seen):
                        seen.add((nr, nc))
                        stack.append((nr, nc))
    return islands

assert count_islands(["110", "010", "001"]) == 2
assert count_islands(["10", "01"]) == 2
assert count_islands([]) == 0

Each land cell is scheduled at most once because it is marked before being pushed. Scanning and traversal take O(rows × cols) time; the visited set and stack can occupy O(rows × cols) space. Mutating visited land can remove the separate set, but the traversal stack can still be large. Input mutation alone does not guarantee constant auxiliary space.

The public nonmutating BFS island-count prompt requires a queue rather than our DFS stack, and its grid holds the integers 0 and 1 rather than strings, so count_islands as written would find no islands there; compare cells with 1 when adapting it. Both find connected components under the same neighbor rule. Change the neighbor rule to include diagonals and the two diagonal land cells in the example become one component.

5. Valid brackets: make the accepted alphabet explicit

Here, only ()[]{} characters are allowed, and an empty string is valid. Non-bracket characters are rejected. A parser that ignores letters has a different contract.

def valid_brackets(text):
    opener_for = {")": "(", "]": "[", "}": "{"}
    stack = []
    for char in text:
        if char in "([{":
            stack.append(char)
        elif char in opener_for:
            if not stack or stack.pop() != opener_for[char]:
                return False
        else:
            return False
    return not stack

assert valid_brackets("{[()]}")
assert valid_brackets("")
assert not valid_brackets(")(")
assert not valid_brackets("()(")
assert not valid_brackets("(a)")

Invariant: the stack contains unmatched openers in their encounter order. Each closer must match the most recent opener; a mismatch fails immediately. Finally, the stack must be empty.

Worst-case time and space are both O(n). Test a leading closer, an unmatched opener, crossing pairs such as ([)], and long nesting. Use the public bracket-sequence prompt for another wording of this pattern, checking its alphabet and return requirements before submitting an answer.

6. Top K frequent values: count all the memory

For integer input, return k distinct values in descending frequency, breaking ties by smaller numeric value. Accept k from zero through the number of distinct values; reject other values.

from collections import Counter
from heapq import nsmallest

def top_k_frequent(values, k):
    counts = Counter(values)
    if type(k) is not int or not 0 <= k <= len(counts):
        raise ValueError("k must be between zero and the distinct-value count")
    return nsmallest(k, counts, key=lambda value: (-counts[value], value))

assert top_k_frequent([1, 1, 1, 2, 2, 3], 2) == [1, 2]
assert top_k_frequent([4, 4, -1, -1, 8], 2) == [-1, 4]
assert top_k_frequent([], 0) == []

Python's heap selection helpers are useful when selecting a small subset. With d distinct values, counting costs expected O(n) time; heap-based selection and final result ordering fit O(d log(k + 1)), giving O(n + d log(k + 1)) overall. Selecting everything can use sorting instead.

The frequency map still stores O(d) entries. A size-k heap does not make total memory O(k): exact counting retains the distinct-value state. Bucket selection can achieve linear time when arbitrary ordering among tied values is acceptable; imposing a sorted tie order can add work.

Try the public top-K frequency and tie-break prompt, whose contract differs: it returns [] for k <= 0 and every distinct value when k exceeds that count, where top_k_frequent raises ValueError. For an unbounded stream with a hard memory cap, discuss approximate heavy-hitter methods or an external store rather than silently pretending exact counts fit in a bounded heap.

7. URL shortener: connect requirements to guarantees

This is a system-design exercise rather than another array function. Define custom aliases, expiry, abuse controls, link ownership, and whether click accounting must pass through your service. Estimate creation and redirect traffic from stated workload assumptions; a read-heavy workload should be established, not assumed universally.

A minimal design has a create API, durable alias-to-destination storage, a redirect handler, and an optional cache. Persist a unique alias mapping before returning the short URL. If generated aliases collide, an atomic uniqueness constraint must reject the duplicate and allow bounded regeneration. A pre-insert existence check alone races with concurrent creators.

Base62 encoding a unique integer is reversible encoding, not encryption. IDs remain guessable unless another design addresses that concern. Random aliases make guessing less predictable but require collision handling. Hashing the long URL still needs a policy for collisions, ownership, expiry, and whether identical URLs should share an alias.

Redirect caching is another contract. HTTP semantics distinguishes permanent and temporary redirects, but choosing 302 alone does not guarantee every click reaches your origin. Cache directives, intermediaries, and client behavior also matter. Decide whether fast cached redirects or origin-observed click events are required, and define what your analytics actually measures.

Cache entries must respect expiry and updates; a long cache TTL must not keep serving a deleted or expired mapping, so cap server-side TTLs at the link's expiry and invalidate entries on deletion. Redirects already cached by browsers or intermediaries cannot be recalled this way. Restrict accepted destination schemes and address abuse. If a later feature fetches destination previews, evaluate its server-side request risks separately from merely returning a redirect.

Practice with the public URL shortener design prompt, then use the system architecture article to discuss availability and consistency trade-offs. Amazon's senior engineer preparation guidance lists reliability and scalability among its design objectives; it does not establish that this particular question appears in every interview.

8. Median of two sorted arrays: search for a cut

Assume two ascending lists of integers. Searching the shorter list bounds the possible cut positions. Choose left partitions containing (m + n + 1) // 2 values in total, then require each left boundary to be no greater than the opposite right boundary.

This function returns an integer for odd totals and an exact Fraction for even totals. It rejects two empty lists. The sorted-input precondition belongs to the caller; a full sortedness check would add linear work.

from fractions import Fraction

def median_two_sorted(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    if m + n == 0:
        raise ValueError("at least one value is required")
    low, high = 0, m
    half = (m + n + 1) // 2
    while low <= high:
        i = (low + high) // 2
        j = half - i
        left_a = a[i-1] if i else float("-inf")
        right_a = a[i] if i < m else float("inf")
        left_b = b[j-1] if j else float("-inf")
        right_b = b[j] if j < n else float("inf")
        if left_a <= right_b and left_b <= right_a:
            if (m + n) % 2:
                return max(left_a, left_b)
            return Fraction(max(left_a, left_b) + min(right_a, right_b), 2)
        if left_a > right_b:
            high = i - 1
        else:
            low = i + 1
    raise ValueError("inputs must satisfy the sorted-list contract")

assert median_two_sorted([1, 3], [2]) == 2
assert median_two_sorted([1, 2], [3, 4]) == Fraction(5, 2)
assert median_two_sorted([], [7]) == 7

If the left boundary of a is too large, move its cut left. Otherwise, when the opposite boundary violates the invariant, move it right. Each step removes possible cut positions, giving O(log(min(m, n) + 1)) time and constant auxiliary storage under the usual arithmetic-operation model.

A merge-and-select baseline takes O(m + n) time and is a useful correctness oracle for small tests. Cover an empty side, repeated values, unequal lengths, and odd and even totals. The combined-median practice prompt is a related exercise; adapt return types to its specification.

Compare the patterns without hiding assumptions

Here, n is input length, d is the number of distinct values, c is cache capacity, and r × s is grid size. Costs describe the implementations above, including their main auxiliary structures.

Turn repetition into a useful practice session

Choose one pattern, explain its contract, solve it, and then change one requirement. Keep a short record of the bug you found and the assumption that caused it. Revisit that variant later without looking at the prior implementation. The coding interview patterns article offers further worked traces.

Use research as context rather than a hiring guarantee. The commentary Structured interviews: moving beyond mean validity discusses variation in interview validity and how methodology and context can affect it. It does not validate this particular eight-question curriculum or imply that a specific practice routine increases an individual's hiring probability by a fixed amount.

The historical 2025 CoderPad and CodinGame survey reports several assessment formats. Its multiple-choice responses can overlap and describe that survey's respondents, rather than every employer or today's universal interview format. Practice explanation, debugging, code review, and design alongside algorithms.

If you use AI during preparation, follow the assessment's actual rules and verify generated code yourself. Re-run a task without assistance to identify what you can explain independently. Measure progress through correctness, clearer assumptions, and successful follow-ups rather than the number of memorized answers.

Keep practicing

• Merge overlapping and touching closed intervals
• Count islands without modifying the grid
• Find the median of two sorted inputs
• Design a URL shortener and defend its trade-offs
• Coding interview patterns and worked traces