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.

EasyTechnical

47 practiced

Two Sum (hash-table, O(n) expected): Given an integer array nums and an integer target, implement a function in your chosen language (Python/Java/C++) that returns indices of the two numbers such that they add up to target. Assume exactly one solution and you may not use the same element twice. Example: nums = [2,7,11,15], target = 9 -> [0,1]. Explain time and space complexity and discuss edge cases (empty input, negative numbers, duplicates).

Sample Answer

Use a single-pass hash table mapping value -> index. For each number x at index i, check if target - x is already in the map; if so return [map[target-x], i]; otherwise store x -> i. This is O(n) expected time and O(n) space.

python

def two_sum(nums, target):
    """
    Return indices of two numbers that add up to target.
    Assumes exactly one solution and you may not use the same element twice.
    """
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        complement = target - x
        if complement in seen:
            return [seen[complement], i]
        seen[x] = i
    raise ValueError("No two sum solution")  # defensive; per problem this won't happen

# Example:
# nums = [2,7,11,15], target = 9 -> returns [0,1]

Key points:- We check complements before inserting current value so we don't reuse the same element.- Handles negatives and duplicates naturally (duplicates map to last seen index, but earlier occurrence serves as complement when needed).

Time complexity: O(n) expected (hash lookups/inserts average O(1)).Space complexity: O(n) for the hash map.

Edge cases:- Empty or single-element array: loop never finds pair; function raises error (or return None based on spec).- Negative numbers: handled the same way since arithmetic/comparison unaffected.- Duplicates: e.g., nums=[3,3], target=6 — first 3 stored, second finds complement in map and returns indices [0,1]. Alternative approaches: two-pass hash (build map then search) or sorting + two pointers (O(n log n) and requires tracking original indices).

HardTechnical

53 practiced

Minimum Window Substring (hard sliding-window): Given strings s and t, find the minimum window substring in s which contains all characters in t (including multiplicities). Implement the optimal sliding-window approach using two pointers and frequency maps to expand and shrink the window. Discuss handling of character multiplicity, large alphabets, and why this approach is near-optimal.

Sample Answer

To solve this, use the canonical sliding-window: expand the right pointer to include characters until the window is valid (contains all of t with multiplicity), then move the left pointer to shrink while keeping it valid, tracking the minimum window.

python

def minWindow(s: str, t: str) -> str:
    if not s or not t:
        return ""
    from collections import Counter
    need = Counter(t)            # required counts
    window = Counter()           # current window counts
    required = len(need)         # number of distinct chars that must meet count
    formed = 0                   # how many distinct chars currently meet required count
    l = 0
    ans = (float('inf'), None, None)  # length, left, right

    for r, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            formed += 1

        while l <= r and formed == required:
            # update answer
            if (r - l + 1) < ans[0]:
                ans = (r - l + 1, l, r)
            # try to shrink
            window[s[l]] -= 1
            if s[l] in need and window[s[l]] < need[s[l]]:
                formed -= 1
            l += 1

    return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1]

Key points:- Multiplicity: Counter tracks counts; formed increments only when a char's count reaches required multiplicity.- Large alphabets: Using hash maps (Counter/dict) keeps it general (not limited to ASCII); memory is O(k) where k = distinct chars in s or t.- Near-optimality: Each character is visited at most twice (entering and leaving window) ⇒ O(n) time on average. Hash operations add O(1) amortized cost. Worst-case depends on hash performance but still linear in practice.- Edge cases: empty s/t, t longer than s, repeated chars in t, unicode characters.

HardTechnical

88 practiced

K-th Shortest Path in Weighted Directed Graph (allowing revisits): Given a weighted directed graph, source node, target node and integer k, compute the length of the k-th shortest path from source to target (paths may revisit nodes). Implement modified Dijkstra/A* style algorithm using a min-heap and a count of times each node is popped; stop when target has been popped k times. Assume non-negative weights and explain complexity analysis.

Sample Answer

Approach — idea: run a modified Dijkstra that allows revisiting nodes up to k times. Use a min-heap of (distance, node). Maintain pop-count cnt[node] = number of times node has been popped (i.e., the number of distinct shortest-to-that-node paths popped in increasing order). Each time you pop (d,u) if u == target and cnt[u] == k return d. Only expand a node when cnt[u] <= k (so we allow up to k expansions per node). This correctly enumerates path lengths in non-decreasing order because the heap always yields the next shortest partial path.

python

import heapq
from collections import defaultdict

def kth_shortest_path(n, edges, source, target, k):
    """
    n: number of nodes (0..n-1)
    edges: list of (u, v, w)
    source, target: ints
    k: integer >=1
    returns: distance of k-th shortest path or None if not exist
    """
    adj = [[] for _ in range(n)]
    for u,v,w in edges:
        adj[u].append((v,w))
    cnt = [0]*n
    heap = [(0, source)]
    while heap:
        d,u = heapq.heappop(heap)
        cnt[u] += 1
        if u == target and cnt[u] == k:
            return d
        if cnt[u] > k:
            continue
        for v,w in adj[u]:
            heapq.heappush(heap, (d + w, v))
    return None

Key points:- We do not need visited[] as in standard Dijkstra because revisits are allowed.- cnt[u] bounds expansions so algorithm terminates even with cycles.

Complexity:- Each node can be popped at most k times => up to k*n pops.- Each pop expands all outgoing edges => up to k*m pushes.- Heap operations cost O(log (k*n)) each.- Time: O(k * (n + m) * log(k*n)) ≈ O(k*m*log(k*n)).- Space: O(k*m) worst-case for heap plus O(n+m) for graph.

Edge cases:- If fewer than k distinct path enumerations reach target, return None.- k = 1 reduces to standard Dijkstra (first time target popped).- Zero-weight cycles: allowed but controlled by cnt limit to avoid infinite loops.

Alternatives:- Use A* with an admissible heuristic (e.g., shortest distances from each node to target precomputed with reverse Dijkstra) to prune and accelerate enumerating k shortest paths. For enumerating simple (loopless) k-shortest paths, Yen's algorithm is used.

MediumTechnical

47 practiced

Merge Intervals (meeting room merging): Given an array of intervals where each interval is [start, end], merge all overlapping intervals and return the merged list. Implement by sorting intervals by start time then iterating once to merge. Provide code and discuss handling of inclusive/exclusive boundaries and large input size considerations.

Sample Answer

To solve this, sort intervals by start time, then iterate once keeping a "current" merged interval. If the next interval overlaps (next.start <= current.end for inclusive boundaries), extend the current end; otherwise append current and move to next. This is greedy, O(n log n) dominated by sort, O(n) extra for the output.

python

from typing import List

def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    """
    Merge overlapping intervals. Intervals are lists [start, end].
    Uses inclusive boundary merging: overlap if next_start <= current_end.
    """
    if not intervals:
        return []

    # Sort by start time (in-place)
    intervals.sort(key=lambda x: x[0])

    merged = []
    cur_start, cur_end = intervals[0]

    for s, e in intervals[1:]:
        if s <= cur_end:            # inclusive overlap; use s < cur_end for exclusive
            cur_end = max(cur_end, e)
        else:
            merged.append([cur_start, cur_end])
            cur_start, cur_end = s, e

    merged.append([cur_start, cur_end])
    return merged

Key points:- Inclusive vs exclusive: use s <= cur_end to merge when boundaries touch (e.g., [1,2] and [2,3] -> merged to [1,3]). If intervals are half-open [start, end) (exclusive end), use s < cur_end.- Time: O(n log n) due to sort; single pass O(n) after.- Space: O(n) worst-case for output; in-place sort reduces extra memory.- Large input considerations: sort dominates—use Timsort (Python) which is stable and memory efficient. For huge datasets that don't fit memory, perform external/parallel sort, or stream sorted chunks and merge (k-way merge). Avoid expensive per-interval allocations (use preallocated lists or generators where appropriate).- Edge cases: empty list, single interval, intervals with same start, negative times, unsorted inputs, zero-length intervals. Validate inputs if necessary.

MediumTechnical

54 practiced

Sliding Window Maximum (monotonic deque): Given an integer array nums and window size k, return an array of the maximums for every sliding window of size k. Implement an O(n) solution using a deque that stores indices of useful candidates and keeps them in decreasing order. Explain edge cases when k > n and how to handle ties.

Sample Answer

Approach:Use a monotonic deque (store indices) that keeps values in decreasing order. For each index i, pop indices from the back while nums[i] >= nums[deque[-1]] (this maintains decreasing order and handles ties by allowing the newer index to replace equal values). Remove the front if it's out of window (deque[0] <= i - k). Once i >= k-1, append nums[deque[0]] to results.

python

from collections import deque

def max_sliding_window(nums, k):
    """
    Returns list of max for every sliding window of size k.
    O(n) time, O(k) space.
    """
    n = len(nums)
    if k <= 0:
        return []
    if k > n:
        # Interpret: if window larger than array, return single max of entire array
        return [max(nums)] if nums else []
    
    dq = deque()  # will store indices, nums[dq[0]] is current max
    res = []
    
    for i, val in enumerate(nums):
        # Remove indices out of current window
        while dq and dq[0] <= i - k:
            dq.popleft()
        # Maintain decreasing order; for ties, allow current index to replace previous
        while dq and nums[dq[-1]] <= val:
            dq.pop()
        dq.append(i)
        # Record max once first window is complete
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Key points:- Deque stores indices to check window expiry easily.- Using <= when popping back ensures newest index replaces equal-value older ones; this handles ties and keeps window freshest.- Time: O(n) because each index enters/exits deque once. Space: O(k).Edge cases:- k <= 0 -> return []. k > n -> return single max of array (or [] for empty input). Empty nums -> [].

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.