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.

HardTechnical

51 practiced

Given an array of bar heights representing a histogram, compute the area of the largest rectangle in the histogram. Implement an O(n) solution using a monotonic stack and explain why the stack yields linear complexity. Discuss edge cases like equal heights and empty histogram.

Sample Answer

Approach: Use a monotonic increasing stack of indices. Traverse bars, pushing indices while heights increase. When a lower height appears, pop taller bars and compute area using popped height × width (width = current_index - stack_top_after_pop - 1). Append a sentinel 0 height at end to flush stack.

python

def largest_rectangle_area(heights):
    """
    O(n) monotonic-stack solution.
    heights: list[int]
    returns: int (max area)
    """
    # Add sentinel to flush remaining bars
    heights = heights + [0]
    stack = [-1]          # stack of indices; sentinel -1 simplifies width calc
    max_area = 0

    for i, h in enumerate(heights):
        # Maintain increasing heights in stack
        while stack[-1] != -1 and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Key concepts:- Stack stores indices of increasing bar heights; when encountering a lower bar, the popped bar's right boundary is current index, left boundary is new stack top.- Using indices (not heights) simplifies width calculation.

Why O(n): Each index is pushed exactly once and popped at most once — the while-loop across entire run performs at most n pops. All other operations are O(1), so total is O(n).

Time/Space:- Time: O(n)- Space: O(n) worst-case for stack

Edge cases:- Empty histogram -> returns 0 (function returns 0 because sentinel only, no area).- All equal heights -> stack grows, then sentinel triggers pops computing full-width area correctly.- Single bar -> handled.- Large inputs -> avoids recursion; iterative and memory-efficient.

Alternatives: Divide-and-conquer gives O(n log n) average, or segment tree for range-min queries; monotonic stack is simplest O(n).

MediumTechnical

62 practiced

Implement a function similar to C's atoi that converts a string to a 32-bit signed integer. The function should discard whitespace, handle optional sign, parse digits until non-digit, and clamp overflow to int32 limits. Provide clear behavior for inputs like ' -42' and '4193 with words'.

Sample Answer

To implement atoi-like behavior: trim leading whitespace, handle optional '+'/'-' sign, parse consecutive digits stopping at first non-digit, build result while checking overflow and clamp to 32-bit signed int range [-2**31, 2**31 -1]. Return 0 when no digits found.

python

def my_atoi(s: str) -> int:
    """
    Convert string to 32-bit signed integer similar to C's atoi.
    """
    s = s.lstrip()  # discard leading whitespace
    if not s:
        return 0

    INT_MIN, INT_MAX = -2**31, 2**31 - 1
    sign = 1
    i = 0
    if s[0] in ('+', '-'):
        if s[0] == '-':
            sign = -1
        i += 1

    result = 0
    while i < len(s) and s[i].isdigit():
        digit = ord(s[i]) - ord('0')
        # Check overflow before multiplying by 10
        if result > (INT_MAX - digit) // 10:
            return INT_MAX if sign == 1 else INT_MIN
        result = result * 10 + digit
        i += 1

    return sign * result

Key points:- Uses lstrip to remove leading spaces, then processes sign and digits.- Overflow check uses safe inequality to avoid using bigger integer arithmetic.- Examples: " -42" -> -42; "4193 with words" -> 4193; "words 123" -> 0.Time complexity O(n), space O(1). Alternative: regex to extract pattern then convert, but manual parse is clearer and avoids overhead.

EasyTechnical

59 practiced

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and return the new length. Do not allocate extra space for another array and modify the input array in-place with O(1) additional memory. Explain the two pointer approach and how to handle arrays of size zero or one.

Sample Answer

To solve this in O(1) extra space we use the two-pointer (slow/fast) technique on the sorted array so duplicates are adjacent.

Approach:- If nums is empty, return 0. If length is 1, return 1.- Use slow (write index) starting at 0. Fast (read index) scans from 1..n-1.- When nums[fast] != nums[slow], increment slow and write nums[slow] = nums[fast].- At the end, length = slow + 1; array's first length elements are unique.

Code (Python):

python

def remove_duplicates(nums):
    """
    Removes duplicates in-place from sorted list nums.
    Returns new length. Modifies nums so first k elements are unique.
    """
    if not nums:
        return 0
    n = len(nums)
    if n == 1:
        return 1

    slow = 0
    for fast in range(1, n):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

Key points:- Two pointers: fast reads, slow writes only when new value found.- Time: O(n) single pass. Space: O(1) extra.- Edge cases: empty list -> 0, single element -> 1, all-equal elements -> result 1, no duplicates -> n.- Practical note for data engineers: this pattern is efficient for in-memory dedup on sorted streams; for large-scale pipelines, sort/partition then apply same logic in streaming/batch transforms (e.g., Spark mapPartitions).

EasyTechnical

44 practiced

Given the root of a binary tree, return the inorder traversal of its nodes values using an iterative approach (no recursion). Implement in your chosen language and explain why an explicit stack is necessary. Discuss time and space complexity and behavior on skewed trees.

Sample Answer

To perform iterative inorder traversal (left, root, right) we simulate the recursion call stack with an explicit stack: push nodes while going left, then process node, then go right. The explicit stack is necessary because recursion implicitly uses the call stack to remember nodes; iterative approach must store the path from root to current node.

python

# Python iterative inorder traversal
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal(root):
    """
    Returns list of node values in inorder using an explicit stack (no recursion).
    """
    result = []
    stack = []
    current = root

    # Traverse until all nodes are processed
    while current or stack:
        # Reach the leftmost node of current
        while current:
            stack.append(current)
            current = current.left
        # current is None here; pop the last node and process it
        node = stack.pop()
        result.append(node.val)
        # Visit right subtree
        current = node.right

    return result

Key points:- The stack stores ancestors waiting to be visited after exhausting their left subtrees.- Time complexity: O(n) — each node is pushed and popped at most once.- Space complexity: O(h) where h is tree height (stack size).- Skewed trees: For a completely skewed tree (like a linked list), h = n so space becomes O(n). Balanced tree gives O(log n) space.

HardTechnical

62 practiced

Design an algorithm to maintain the median of a stream of integers. Implement data structures that support addNum and findMedian in logarithmic time per insert. Explain how two heaps (a max-heap and a min-heap) are used and how balancing works, and discuss memory and performance implications for high-rate data streams.

Sample Answer

Approach:Use two heaps: a max-heap (left) for the lower half and a min-heap (right) for the upper half. Keep sizes balanced so either equal or left has one extra. Invariant: every value in left <= every value in right. Median is either top of left (odd total) or average of tops (even).

python

import heapq

class MedianFinder:
    def __init__(self):
        # Python has min-heap; left stores negatives to act as max-heap
        self.left = []   # max-heap (store -x)
        self.right = []  # min-heap

    def addNum(self, num: int) -> None:
        # Push to appropriate heap
        if not self.left or num <= -self.left[0]:
            heapq.heappush(self.left, -num)
        else:
            heapq.heappush(self.right, num)

        # Rebalance sizes: allow left to have at most 1 extra
        if len(self.left) > len(self.right) + 1:
            heapq.heappush(self.right, -heapq.heappop(self.left))
        elif len(self.right) > len(self.left):
            heapq.heappush(self.left, -heapq.heappop(self.right))

    def findMedian(self) -> float:
        if len(self.left) > len(self.right):
            return float(-self.left[0])
        return (-self.left[0] + self.right[0]) / 2.0

Key concepts:- addNum: O(log n) for heap push/pop.- findMedian: O(1) to read tops.- Space: O(n) storing stream values.

Balancing details:- Always ensure size difference ≤1 and ordering invariant holds by inserting then moving one element when needed.

Edge cases:- Duplicates, negative numbers handled.- Empty stream: define behavior (e.g., raise exception).

Memory & performance for high-rate streams:- Heaps keep full history—may be unacceptable at very high rates. Options: - Windowed median (fixed-size buffer) to bound memory. - Approximate medians: use streaming summaries (t-digest, GK sketch) for much lower memory and faster amortized insertion with controlled error. - Sharding: partition stream across workers, compute local summaries, merge periodically. - Persist older data to disk / columnar storage and keep only recent window in memory.

Trade-offs:- Exact median with two heaps is simple and exact but memory-linear and single-threaded; for high-throughput/low-memory use probabilistic/summary structures or distributed aggregation.

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.