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

46 practiced

Implement a function in Python to reverse a singly linked list in-place and return the new head. Given the head node of a singly linked list, reverse the list iteratively in O(n) time and O(1) extra space. Example:Input: 1 -> 2 -> 3 -> 4 -> 5Output: 5 -> 4 -> 3 -> 2 -> 1Describe edge cases (empty list, single node) and provide clean, well-commented code. Explain time and space complexity and any pointer pitfalls.

Sample Answer

We can reverse a singly linked list iteratively by walking the list once and reversing next pointers as we go, using three pointers: prev, curr, next_node. This is O(n) time and O(1) extra space.

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    """
    Reverse a singly linked list in-place and return new head.
    Iterative, O(n) time, O(1) extra space.
    """
    prev = None
    curr = head

    while curr:
        # Save next node before breaking the link
        next_node = curr.next
        # Reverse pointer
        curr.next = prev
        # Move prev and curr one step forward
        prev = curr
        curr = next_node

    # prev is the new head (curr is None at end)
    return prev

Key points:- Edge cases: head is None (empty list) -> returns None; single node -> loop runs once, returns that node.- Pointer pitfalls: forgetting to save curr.next before reassigning curr.next will lose the rest of the list; ensure you update prev then curr in correct order.- Time complexity: O(n) — one pass through n nodes.- Space complexity: O(1) extra — only a few pointers used.

Example:Input 1->2->3 returns 3->2->1 after reverse_list(head).

HardTechnical

62 practiced

Sliding Window Median (Python): given an array nums and a sliding window size k, return the median for each sliding window as it moves from left to right. Implement the solution using two heaps (max-heap for lower half and min-heap for upper half) with lazy-deletion to support removals. Discuss complexity and balancing heaps for odd/even k.

Sample Answer

Approach:Use two heaps: max-heap (as negative values) called low for the lower half, and min-heap high for the upper half. Maintain sizes so that:- If k is odd: low has one more element than high (median = -low[0]).- If k is even: low and high have equal size (median = (-low[0] + high[0]) / 2).For removals, use lazy-deletion: keep a dictionary "del_map" counting values to remove. When the top of a heap is marked for deletion, pop and decrement the map. Rebalance after each add/remove.

Code:

python

import heapq
from collections import defaultdict

def sliding_window_median(nums, k):
    if not nums or k == 0:
        return []
    low, high = [], []            # low: max-heap (store negatives), high: min-heap
    delayed = defaultdict(int)    # value -> count to delete
    res = []
    low_size = high_size = 0

    def prune(heap):
        # remove top elements that are delayed
        while heap:
            val = -heap[0] if heap is low else heap[0]
            if delayed.get(val,0):
                heapq.heappop(heap)
                delayed[val] -= 1
                if delayed[val] == 0:
                    del delayed[val]
            else:
                break

    def rebalance():
        nonlocal low_size, high_size
        # ensure sizes respect k parity
        if low_size > high_size + 1:
            val = -heapq.heappop(low)
            low_size -= 1
            heapq.heappush(high, val)
            high_size += 1
            prune(low)
        elif low_size < high_size:
            val = heapq.heappop(high)
            high_size -= 1
            heapq.heappush(low, -val)
            low_size += 1
            prune(high)

    def add(num):
        nonlocal low_size, high_size
        if not low or num <= -low[0]:
            heapq.heappush(low, -num); low_size += 1
        else:
            heapq.heappush(high, num); high_size += 1
        rebalance()

    def remove(num):
        nonlocal low_size, high_size
        delayed[num] += 1
        # logically remove from appropriate heap
        if low and num <= -low[0]:
            low_size -= 1
            if low_size < 0: low_size = 0
            prune(low)
        else:
            high_size -= 1
            if high_size < 0: high_size = 0
            prune(high)
        rebalance()

    def get_median():
        if k % 2 == 1:
            prune(low)
            return float(-low[0])
        else:
            prune(low); prune(high)
            return (-low[0] + high[0]) / 2.0

    # init first window
    for i in range(k):
        add(nums[i])
    res.append(get_median())

    for i in range(k, len(nums)):
        add(nums[i])
        remove(nums[i-k])
        res.append(get_median())

    return res

Key points:- lazy-deletion avoids O(k) removal from heaps by marking deletions and pruning only at heap top.- Maintain low_size and high_size to track logical sizes (exclude delayed).Complexity:- Time: O(n log k) — each element pushed/popped at most once; prune operations amortized.- Space: O(k) for heaps plus O(k) for delayed map.Edge cases:- k = 1 (median = element), k = len(nums), duplicates, negative numbers.Balancing:- For odd k keep low one larger; for even keep equal sizes so median computed correctly.

HardTechnical

53 practiced

Kth Smallest Element in a Sorted Matrix (Python): given an n x n matrix where each of the rows and columns is sorted in ascending order, return the k-th smallest element in the matrix. Provide solutions using a min-heap or binary search on value range; explain when each approach is preferable and analyze time/space complexity for both.

Sample Answer

To solve this, two common approaches work well: a min-heap (k-way merge) and binary search on the value range using a count <= mid function that exploits row/column sorting.

Approach 1 — Min-heap (k-way merge)1. Idea: Treat each row as a sorted list. Push the first element of each row into a min-heap, repeatedly pop the smallest and push the next element from that row until you pop k times.

python

import heapq

def kth_smallest_heap(matrix, k):
    n = len(matrix)
    if n == 0:
        raise ValueError("Empty matrix")
    heap = []
    # push (value, row, col)
    for r in range(min(n, k)):  # at most k rows needed
        heapq.heappush(heap, (matrix[r][0], r, 0))
    count = 0
    while heap:
        val, r, c = heapq.heappop(heap)
        count += 1
        if count == k:
            return val
        if c + 1 < n:
            heapq.heappush(heap, (matrix[r][c+1], r, c+1))
    raise IndexError("k out of range")

Key points:- Good when n is small or k is small relative to n^2; simple to implement.Time: O(k log min(n,k)) — each pop/push is log heap-size (≤ min(n,k)). Space: O(min(n,k)).

Approach 2 — Binary search on value range1. Idea: Binary search between smallest and largest matrix values. For a mid value, count how many elements ≤ mid in O(n) by walking from top-right down/left.

python

def count_leq(matrix, mid):
    n = len(matrix)
    r, c = 0, n - 1
    cnt = 0
    while r < n and c >= 0:
        if matrix[r][c] <= mid:
            cnt += c + 1
            r += 1
        else:
            c -= 1
    return cnt

def kth_smallest_bs(matrix, k):
    n = len(matrix)
    left, right = matrix[0][0], matrix[-1][-1]
    while left < right:
        mid = (left + right) // 2
        if count_leq(matrix, mid) < k:
            left = mid + 1
        else:
            right = mid
    return left

Key points:- Time: O(n log(range)) where range = max-min; with integer values, log(range) usually small. More precisely O(n log V). Space: O(1).- Preferred when n is large and matrix is dense (k could be large) because it avoids heap memory and touches each row only O(log V) times.

When to prefer:- Use heap when k is small (you only extract k elements) or when coding speed and clarity matter.- Use binary search when n is large or k ~ n^2; it's more efficient in time/space for big matrices and predictable performance.

Edge cases:- Empty matrix, k out of range, non-square but still works if you adapt dimensions (here n x n). Duplicate values are handled by both methods.

MediumTechnical

49 practiced

Top K Frequent Elements (Python): given an integer array nums and integer k, return the k most frequent elements. Implement an efficient solution using a hashmap to count frequencies followed by a min-heap of size k or bucket sort. Discuss time/space trade-offs and behavior when k is large (close to n).

Sample Answer

To solve this, first count frequencies with a hashmap, then either (A) maintain a min-heap of size k of (freq, num) or (B) use bucket sort (array indexed by frequency). Heap is good when k << unique, bucket is linear and simpler when k is large.

python

from collections import Counter
import heapq

def topKFrequent(nums, k):
    # Count frequencies
    freq = Counter(nums)  # O(n) time, O(u) space where u = unique elements

    # Use min-heap of size k
    heap = []
    for num, f in freq.items():
        if len(heap) < k:
            heapq.heappush(heap, (f, num))
        else:
            if f > heap[0][0]:
                heapq.heapreplace(heap, (f, num))
    # Extract results
    return [num for _, num in heapq.nlargest(k, heap)]

Key points:- Heap approach: O(n + u log k) time, O(u + k) space. Best when k is small relative to u.- Bucket sort: build buckets of size n+1, place numbers in bucket[freq] and scan descending → O(n) time, O(n + u) space. Prefer when k is large (close to n) or when you need strict linear time.- When k ≈ n (or k ≈ u), heap gives little benefit and may be slower than bucket sort; bucket/partial sort or simply sorting by frequency (O(u log u)) are viable.Edge cases:- k == 0 -> return []- nums empty -> return []- duplicates and negative numbers handled by CounterTrade-offs:- Heap uses less memory for small k; bucket uses predictable linear time and is simpler to extract top-k when k large.

MediumTechnical

48 practiced

Clone Graph (Python): given a reference of a node in a connected undirected graph where each node contains a list of its neighbors, return a deep copy (clone) of the graph. Implement using BFS or DFS and a hashmap to keep mapping from original to clone. Handle empty graph and large graphs with cycles.

Sample Answer

Approach: Use BFS (or DFS) with a hashmap that maps original nodes to their cloned counterparts. Traverse the graph, clone nodes on first encounter, and populate neighbor lists using the hashmap to avoid infinite loops on cycles and to handle large graphs efficiently.

python

from collections import deque

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node: 'Node') -> 'Node':
    if node is None:
        return None

    # Map original node -> cloned node
    cloned = {node: Node(node.val)}
    q = deque([node])

    while q:
        cur = q.popleft()
        for nei in cur.neighbors:
            if nei not in cloned:
                # Clone neighbor and enqueue for processing
                cloned[nei] = Node(nei.val)
                q.append(nei)
            # Append cloned neighbor to current clone's neighbors
            cloned[cur].neighbors.append(cloned[nei])

    return cloned[node]

Key points:- BFS ensures we visit nodes level-by-level; DFS (recursive or stack) works similarly using the same hashmap.- Hashmap prevents re-cloning and handles cycles.- Time complexity: O(N + E) where N = nodes, E = edges (visit each edge/node once).- Space complexity: O(N) for hashmap and queue/stack.Edge cases:- node is None (empty graph) — return None.- Self-loop and cycles — handled by hashmap.- Very large graphs — avoid recursion (use BFS or iterative DFS) to prevent recursion depth issues.

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.