Intermediate Algorithm Problem Solving Questions

Practical skills for solving medium difficulty algorithmic problems. Topics include two pointer techniques, sliding window, variations of binary search, medium level dynamic programming concepts such as recursion with memoization, breadth first search and depth first search on graphs and trees, basic graph representations, heaps and priority queues, and common string algorithms. Emphasis is on recognizing problem patterns, constructing correct brute force solutions and then applying optimizations, analyzing trade offs between time and space, and practicing systematic approaches to reach optimal or near optimal solutions.

EasyTechnical

19 practiced

Given a string, find the first non-repeating character and return its index; return -1 if none exists. Implement in O(n) time using appropriate data structures and discuss considerations for Unicode/multi-byte characters and case-sensitivity. Example: s = "leetcode" -> return 0; s = "loveleetcode" -> return 2.

Sample Answer

Approach: Do a single pass to count character frequencies with an ordered structure, then a second pass to find the first char with count 1. Use a hash map (dict) for O(1) average access. This yields O(n) time and O(k) space where k = distinct characters.

python

def first_unique_char(s: str) -> int:
    """
    Return index of first non-repeating character or -1.
    Works in O(n) time using a frequency hashmap.
    """
    # Count frequencies in one pass
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1

    # Second pass: first char with freq 1
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

Key points:- Uses Python str so characters are Unicode code points; iterating s yields logical characters (not bytes), which handles multi-byte UTF-8 correctly.- If you must treat grapheme clusters (e.g., emoji with modifiers or composed accented chars) as single user-perceived characters, use the `regex` library with `\X` or Python's `unicodedata` normalization before processing.- Case-sensitivity: current implementation is case-sensitive ("A" != "a"). To be case-insensitive, normalize with `s = s.lower()` (or `.casefold()` for better Unicode folding) before counting.

Time Complexity: O(n) (two linear passes). Space Complexity: O(k) for the frequency map.

Edge cases:- Empty string -> -1- All repeated characters -> -1- Very large input: memory grows with distinct characters; streaming or limited alphabet optimizations possible (e.g., fixed-size array for ASCII).

EasyTechnical

21 practiced

Given two sorted singly linked lists, merge them into a single sorted list and return its head. Implement the iterative solution with O(1) extra space and O(n+m) time, and discuss the recursive alternative and potential stack depth implications. Example input lists: 1->2->4 and 1->3->4 -> result 1->1->2->3->4->4.

Sample Answer

Approach: Use a dummy head and a tail pointer to build the merged list iteratively by always attaching the smaller current node from the two input lists. This is O(n+m) time and O(1) extra space (in-place node re-linking).

python

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

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
    # Dummy simplifies edge cases; tail points to last node in merged list
    dummy = ListNode(-1)
    tail = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    # Attach remaining nodes (one of l1 or l2 may be non-empty)
    tail.next = l1 if l1 else l2

    return dummy.next

Key points:- Time: O(n + m) — each node visited once.- Space: O(1) extra — only a few pointers; nodes reused.- Handles duplicates and differing lengths; returns None for two empty lists.

Recursive alternative:- Recursively pick the smaller head, set its next to merge(rest). Simpler code:

python

def merge_recursive(a,b):
    if not a: return b
    if not b: return a
    if a.val <= b.val:
        a.next = merge_recursive(a.next, b)
        return a
    else:
        b.next = merge_recursive(a, b.next)
        return b

- Stack depth: recursion depth = number of nodes processed in call chain (could be up to n+m). For very long lists this risks RecursionError/stack overflow; iterative approach is safer in production.

MediumTechnical

24 practiced

Given an integer array (which may include negative numbers) and an integer k, implement an algorithm to count the number of contiguous subarrays whose sum equals k. Aim for O(n) time using prefix sums and a hashmap; provide code and discuss handling very large arrays and integer overflow risks.

Sample Answer

To count contiguous subarrays summing to k in O(n), use prefix sums and a hashmap that tracks how many times each prefix sum has occurred. For each running sum S, the number of subarrays ending at current index with sum k equals counts[S - k].

python

def subarray_sum(nums, k):
    """
    Count contiguous subarrays with sum == k using prefix sums + hashmap.
    O(n) time, O(n) space.
    """
    from collections import defaultdict

    count = 0
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1  # empty prefix

    curr = 0
    for x in nums:
        curr += x
        # if curr - k seen before, add how many times
        count += prefix_counts.get(curr - k, 0)
        prefix_counts[curr] += 1

    return count

Key points:- We update count using prior prefix_counts[curr - k] before incrementing prefix_counts[curr].- Time: O(n); Space: O(n) in worst case (all distinct prefixes).

Handling very large arrays and overflow:- Python ints are unbounded so overflow isn’t an issue; in Java/C++ use 64-bit (long / long long) for prefix sums. If values and n can produce sums beyond 64-bit, consider using BigInteger (Java) or guard with problem constraints.- For memory pressure on huge arrays, stream through input and maintain hashmap; if distinct prefix sums approach memory limits, consider external counting (e.g., chunking, compressing values) or probabilistic methods (count-min sketch) at the cost of exactness.

Edge cases:- Empty array, k = 0, negative numbers, duplicates—all handled by this approach.

Alternatives:- For non-negative arrays, sliding window can be O(n) with O(1) space, but doesn’t work with negatives.

MediumTechnical

25 practiced

Given a string containing parentheses and letters, remove the minimum number of invalid parentheses to make the input valid and return all possible valid results. Implement BFS or DFS with careful pruning and memoization to avoid duplicates; explain why BFS gives the minimal removal. Discuss complexity and provide code outline.

Sample Answer

Approach: Use BFS to generate states by removing one parenthesis at a time; BFS level-order guarantees the first time we find any valid string, it uses the minimal number of removals. Use a queue, a visited set (memoization) to avoid duplicates, and stop expanding deeper levels once you found valid strings at current level (pruning).

python

from collections import deque

def is_valid(s):
    # check parentheses balance ignoring letters
    balance = 0
    for ch in s:
        if ch == '(':
            balance += 1
        elif ch == ')':
            balance -= 1
            if balance < 0:
                return False
    return balance == 0

def remove_invalid_parentheses(s):
    """
    BFS approach: O(n * C) where C is number of generated states; see complexity notes.
    Returns all valid strings with minimal removals.
    """
    if is_valid(s):
        return [s]
    res = []
    visited = set([s])
    q = deque([s])
    found = False

    while q and not found:
        level_size = len(q)
        for _ in range(level_size):
            cur = q.popleft()
            for i in range(len(cur)):
                # only try removing parentheses to reduce branching
                if cur[i] not in ('(', ')'):
                    continue
                nxt = cur[:i] + cur[i+1:]
                if nxt in visited:
                    continue
                visited.add(nxt)
                if is_valid(nxt):
                    found = True
                    res.append(nxt)
                else:
                    q.append(nxt)
        # once found==True we finish current level and do not enqueue deeper states
    return list(set(res))  # dedupe just in case

Key points:- BFS finds minimal removals because it explores all strings at removal distance k before k+1; first valid level -> minimal k.- Pruning: only remove '(' or ')', skip contiguous duplicates optionally (avoid removing identical char in same position patterns).- Memoization: visited set prevents re-processing identical states (exponential blow-up avoidance).- Time complexity: Worst-case exponential O(2^n) states but BFS with pruning greatly reduces practical work. Each validity check is O(n), so O(n * states).- Space: O(states * n) for queue + visited.Edge cases: empty string, no parentheses, all invalid requiring full removals.

MediumTechnical

22 practiced

Given an m x n grid where some cells are obstacles, compute the number of unique paths from the top-left corner to the bottom-right corner moving only right or down. Implement a DP solution, show how to optimize space to O(n), and discuss edge cases when start or end cells are blocked. Example grids and constraints should be covered.

Sample Answer

Approach: Use dynamic programming where dp[i][j] = number of ways to reach cell (i,j). If a cell is an obstacle, dp[i][j] = 0. Base: dp[0][0] = 1 if not obstacle. We can reduce space to O(n) by keeping a single row array that accumulates ways from left and top.

python

def unique_paths_with_obstacles(obstacle_grid):
    """
    obstacle_grid: List[List[int]] where 1 is obstacle, 0 is free.
    Returns number of unique paths from top-left to bottom-right moving only right or down.
    Space: O(n) where n = number of columns.
    """
    if not obstacle_grid or not obstacle_grid[0]:
        return 0
    m, n = len(obstacle_grid), len(obstacle_grid[0])
    # If start or end is blocked, no paths.
    if obstacle_grid[0][0] == 1 or obstacle_grid[m-1][n-1] == 1:
        return 0

    dp = [0] * n
    dp[0] = 1  # start

    for i in range(m):
        for j in range(n):
            if obstacle_grid[i][j] == 1:
                dp[j] = 0  # obstacle: no ways to reach here
            else:
                if j > 0:
                    dp[j] += dp[j-1]  # ways from left + current dp[j] (which is from top)
    return dp[-1]

Key points:- dp[j] holds ways to reach current row's column j. Before updating dp[j], it represents ways from previous row (top).- When encountering obstacle, set dp[j]=0 to block propagation.

Time complexity: O(m*n). Space complexity: O(n).

Edge cases:- Empty grid -> 0.- Start or end blocked -> 0.- Single row/column: algorithm handles correctly (propagates zeros on obstacles).- Large grids: values may grow; use big integers (Python handles automatically) or modulo if required.

Example:- 3x3, obstacle at (1,1): returns 2.- All free 2x2: returns 2 (Right->Down, Down->Right).

Unlock Full Question Bank

Get access to hundreds of Intermediate Algorithm Problem Solving interview questions and detailed answers.

Join thousands of developers preparing for their dream job.