Medium Difficulty Coding Problems Questions

Practice and master medium difficulty algorithmic coding problems that commonly appear in technical interviews. Topics include arrays, strings, linked lists, trees, graphs, hash tables, and dynamic programming. Typical techniques to know are two pointer methods, sliding window, breadth first search and depth first search, recursion and backtracking, memoization and bottom up dynamic programming, sorting and greedy heuristics, and common data structure operations. Interviewers evaluate systematic problem solving: clarifying requirements, designing a correct solution, explaining time and space complexity, handling edge cases and input validation, writing clean and working code in your chosen language, and then iterating to optimize performance. Candidates should be comfortable explaining tradeoffs between approaches, testing with example cases, and communicating thought process clearly while coding under time constraints.

MediumTechnical

48 practiced

Decode Ways: given a string s containing only digits, implement num_decodings(s) in Python to return the number of ways to decode it (mapping 1->'A', 2->'B', ..., 26->'Z'). Use DP with O(n) time and O(1) space. Example: s='226' -> 3 ('2-2-6', '22-6', '2-26'). Handle zeros carefully.

Sample Answer

We can solve this with dynamic programming using two variables to store dp[i-1] and dp[i-2] (O(1) space). Iterate left-to-right, at each position count ways using single-digit (if not '0') and two-digit (if the previous char forms a valid 10..26). Handle zeros carefully: '0' cannot be decoded alone and must be part of valid two-digit 10 or 20.

python

def num_decodings(s: str) -> int:
    """
    Return number of ways to decode s (digits only).
    O(n) time, O(1) space.
    """
    if not s:
        return 0

    # prev = dp[i-1], prev_prev = dp[i-2]
    prev_prev = 1  # dp[-1] base (empty string)
    prev = 0 if s[0] == '0' else 1  # dp[0]

    if prev == 0:
        return 0  # string starting with '0' invalid

    for i in range(1, len(s)):
        cur = 0
        # single digit valid if not '0'
        if s[i] != '0':
            cur += prev
        # two-digit check
        two = int(s[i-1:i+1])
        if 10 <= two <= 26:
            cur += prev_prev
        # if cur == 0, no valid decoding (e.g., "30")
        if cur == 0:
            return 0
        prev_prev, prev = prev, cur

    return prev

Key points:- Use prev_prev and prev to avoid O(n) array.- Single-digit adds prev when s[i] != '0'.- Two-digit adds prev_prev when 10 <= int(s[i-1:i+1]) <= 26.- Early return 0 if invalid seen (cur == 0) for efficiency.

Time complexity: O(n). Space complexity: O(1).

Edge cases:- s == "" -> 0- starts with '0' -> 0- "10" or "20" -> 1- "100" -> 0 (since last '0' cannot pair)- large strings handled in linear time.

Alternative: recursive DP with memoization (top-down) but uses O(n) space for recursion/memo.

MediumTechnical

92 practiced

Implement check_inclusion(s1, s2) in Python: given two strings, return True if s2 contains a permutation of s1. This is equivalent to checking if any substring of s2 is an anagram of s1. Use sliding-window + character counts in O(n) time. Example: s1='ab', s2='eidbaooo' -> True.

Sample Answer

To solve this, use a fixed-size sliding window over s2 of length len(s1) and maintain character counts for the window and for s1. Compare counts efficiently by maintaining a match counter (number of characters whose counts are equal) so each step is O(1) and overall O(n).

python

from collections import Counter

def check_inclusion(s1: str, s2: str) -> bool:
    m, n = len(s1), len(s2)
    if m > n:
        return False

    need = Counter(s1)
    window = Counter(s2[:m])

    # fast check for initial window
    if window == need:
        return True

    for i in range(m, n):
        # add s2[i], remove s2[i-m]
        window[s2[i]] += 1
        prev = s2[i - m]
        window[prev] -= 1
        if window[prev] == 0:
            del window[prev]

        if window == need:
            return True

    return False

Key points:- Uses sliding window of size m and hash maps for counts.- Time: O(n * k) worst-case for Counter equality where k is alphabet size; with fixed alphabet (e.g., lowercase letters) this is effectively O(n). Space: O(k).- Edge cases: m > n (handled), empty s1 (depends on spec — here returns True if s1 empty because empty string trivially permutes), non-lowercase characters — Counter handles any chars.- Alternative: keep an array[26] and an integer match count to guarantee strict O(n) time for lowercase letters.

MediumTechnical

56 practiced

Implement a function to find the first missing positive integer in unsorted array nums in O(n) time and O(1) extra space (Cyclic Sort / index placement technique). Example: [3,4,-1,1] -> 2. Explain how to map values to indices and why this achieves linear time.

Sample Answer

To solve this in O(n) time and O(1) extra space, place each value v (1 <= v <= n) at index v-1 by swapping until either the value is out of range or the correct value already sits there. After that pass, the first index i where nums[i] != i+1 is the missing positive (return i+1). This is the cyclic-sort / index placement technique.

python

def first_missing_positive(nums):
    """
    In-place place value v at index v-1 for all 1 <= v <= n.
    """
    n = len(nums)
    i = 0
    while i < n:
        v = nums[i]
        # target index for v is v-1
        if 1 <= v <= n and nums[v - 1] != v:
            # swap nums[i] with nums[v-1] to put v in correct place
            nums[i], nums[v - 1] = nums[v - 1], nums[i]
            # do not increment i; new nums[i] should be examined
        else:
            i += 1

    # find first place where index+1 is missing
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Key points:- Mapping: value v should reside at index v-1. Valid only for 1..n.- Time: Each element is swapped at most once into its correct position, so O(n) total operations.- Space: In-place swaps use O(1) extra memory.Edge cases:- Empty array -> return 1- All correct 1..n -> return n+1- Duplicates and negatives are ignored by range check.

MediumTechnical

63 practiced

Product of Array Except Self: implement product_except_self(nums) in Python that returns an array output where output[i] is product of all elements in nums except nums[i]. Do this without division in O(n) time and O(1) extra space (output doesn't count). Example: [1,2,3,4] -> [24,12,8,6]. Handle zeros correctly.

Sample Answer

We can compute products using prefix (left) products then multiply by suffix (right) products in a single pass using the output array for storage, achieving O(n) time and O(1) extra space (output array excluded).

python

def product_except_self(nums):
    """
    Returns list where out[i] = product of all nums except nums[i].
    O(n) time, O(1) extra space excluding output.
    """
    n = len(nums)
    out = [1] * n

    # Compute prefix products into out: out[i] = product of nums[0..i-1]
    prefix = 1
    for i in range(n):
        out[i] = prefix
        prefix *= nums[i]

    # Multiply by suffix products on the fly: suffix = product of nums[i+1..n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suffix
        suffix *= nums[i]

    return out

Key points:- First pass fills out with cumulative product left-of-i.- Second reverse pass multiplies by cumulative product right-of-i.- Handles zeros naturally: prefix/suffix become zero where appropriate so product except self is correct.Time complexity: O(n). Space complexity: O(1) extra (out not counted).

Edge cases:- Empty list -> returns [].- Single element -> [1] by definition (product of no other elements).- Multiple zeros: e.g., two or more zeros produce all zeros; one zero produces non-zero only at the index of the zero (product of others). This algorithm yields those results without special casing.

Alternative: count zeros and compute total product of non-zero elements then build result — slightly simpler but requires careful zero handling and still O(n).

MediumTechnical

49 practiced

Given a list of points in the plane, implement k_closest(points, k) in Python to return k points closest to origin (0,0) by Euclidean distance. Discuss quickselect (average O(n)) vs heap (O(n log k)). Example: points=[[1,3],[-2,2]], k=1 -> [[-2,2]]. Handle ties deterministically.

Sample Answer

Approach: compute a deterministic key for each point: (distance_squared, x, y) so ties break by x then y. I provide two approaches: Quickselect (average O(n)) implemented in-place, and a Heap approach (O(n log k)) described afterwards.

Quickselect implementation (average O(n), in-place):

python

import random
from typing import List

def k_closest(points: List[List[int]], k: int) -> List[List[int]]:
    """
    Return k points closest to origin, tie-broken by x then y deterministically.
    Uses Quickselect (average O(n)).
    """
    if k <= 0:
        return []
    n = len(points)
    if k >= n:
        return sorted(points, key=lambda p: (p[0]*p[0]+p[1]*p[1], p[0], p[1]))

    def key(p):
        return (p[0]*p[0] + p[1]*p[1], p[0], p[1])

    def partition(l, r):
        pivot_idx = random.randint(l, r)
        pivot_key = key(points[pivot_idx])
        points[pivot_idx], points[r] = points[r], points[pivot_idx]
        store = l
        for i in range(l, r):
            if key(points[i]) <= pivot_key:
                points[store], points[i] = points[i], points[store]
                store += 1
        points[store], points[r] = points[r], points[store]
        return store

    def quickselect(l, r, kth):
        if l >= r:
            return
        p = partition(l, r)
        if p == kth:
            return
        elif p < kth:
            quickselect(p+1, r, kth)
        else:
            quickselect(l, p-1, kth)

    quickselect(0, n-1, k-1)
    result = points[:k]
    return sorted(result, key=key)

Key points:- Uses squared distance to avoid sqrt.- Deterministic tie-breaker: x then y.- Returns the k closest points sorted by the same key.

Complexity:- Quickselect average time O(n), worst-case O(n^2) (mitigated by random pivot); space O(1) extra.- Heap alternative: push first k into max-heap (by negative key) and iterate remaining -> O(n log k) time, O(k) space; simpler and predictable for large k small n.

Edge cases:- k<=0, k>=n handled.- Duplicate points handled by tie rule.- Large coordinates: use squared distances; watch integer overflow in other languages (Python ints unbounded).

Unlock Full Question Bank

Get access to hundreds of Medium Difficulty Coding Problems interview questions and detailed answers.

Join thousands of developers preparing for their dream job.