Twenty (20) Intermediate Whiteboard Programming Questions (Pseudo-Code)

Alright, so you’ve gotten comfortable with the basics and you’re ready to step up your game. Good for you! These intermediate problems are where things get interesting. You’ll start seeing patterns that show up in real software engineering interviews and actual production code.

Here’s the thing about intermediate problems - they’re not about memorizing more algorithms. They’re about learning to think recursively, handle more complex data structures, and solve problems that require multiple steps or approaches. You’ll start seeing how the basic building blocks you learned combine into more sophisticated solutions.

Don’t get discouraged if these feel harder - that’s the point! The goal is to stretch your problem-solving muscles and get comfortable with the kind of thinking that separates junior developers from more experienced ones. Take your time, work through the logic step by step, and remember that even seasoned developers don’t solve these instantly.

These problems will introduce you to concepts like recursion, backtracking, dynamic programming basics, and more complex data manipulation. Trust me, once you get comfortable with these patterns, you’ll start seeing them everywhere in real code.

General Intermediate Whiteboard Tips

  1. Break down complex problems - Look for subproblems you can solve independently
  2. Consider recursive solutions - Many intermediate problems have elegant recursive approaches
  3. Think about time/space trade-offs - Sometimes using more memory makes things much faster
  4. Don’t optimize prematurely - Get a working solution first, then improve it
  5. Use helper functions - Complex problems often benefit from breaking logic into smaller pieces
  6. Consider edge cases early - Intermediate problems often have tricky edge cases
  7. Practice explaining your approach - Being able to articulate your thinking is crucial
  8. Know when to use different data structures - Sets, maps, stacks, and queues are your friends

Question 1: Generate All Permutations of a String

Problem: Generate all possible permutations of a string.

Example: Input: “abc” → Output: [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]

Solution:

FUNCTION generate_permutations(text):
    result = empty_array()
    used = empty_array()
    current = ""
    
    CALL generate_perms_helper(text, current, used, result)
    RETURN result

FUNCTION generate_perms_helper(text, current, used, result):
    IF length(current) = length(text):
        ADD current TO result
        RETURN
    
    index = 0
    WHILE index < length(text):
        IF used[index] = false:
            used[index] = true
            current = current + text[index]
            
            CALL generate_perms_helper(text, current, used, result)
            
            // Backtrack
            current = remove_last_char(current)
            used[index] = false
        
        index = index + 1

WHY this works: This is a classic backtracking problem. We build permutations one character at a time, keeping track of which characters we’ve used. When we reach the full length, we’ve found a complete permutation. The key insight is backtracking - we undo our choice and try the next option. This pattern shows up in many complex problems.

Question 2: Longest Palindromic Substring

Problem: Find the longest palindromic substring in a given string.

Example: Input: “babad” → Output: “bab” (or “aba”)

Solution:

FUNCTION longest_palindrome(text):
    IF length(text) = 0:
        RETURN ""
    
    longest = ""
    index = 0
    
    WHILE index < length(text):
        // Check for odd-length palindromes (center is a single character)
        odd_palindrome = expand_around_center(text, index, index)
        
        // Check for even-length palindromes (center is between characters)
        even_palindrome = expand_around_center(text, index, index + 1)
        
        // Keep track of the longest palindrome found
        IF length(odd_palindrome) > length(longest):
            longest = odd_palindrome
        
        IF length(even_palindrome) > length(longest):
            longest = even_palindrome
        
        index = index + 1
    
    RETURN longest

FUNCTION expand_around_center(text, left, right):
    WHILE left >= 0 AND right < length(text) AND text[left] = text[right]:
        left = left - 1
        right = right + 1
    
    // Return the palindrome (excluding the characters that broke the condition)
    RETURN substring(text, left + 1, right - 1)

WHY this works: Instead of checking every possible substring (which would be O(n³)), we use the insight that palindromes expand around their center. For each potential center, we expand outward as long as characters match. We need to check both odd-length (single character center) and even-length (between characters) palindromes. This reduces complexity to O(n²).

Question 3: Binary Tree Level Order Traversal

Problem: Traverse a binary tree level by level (breadth-first).

Example: Given tree with root 3, left child 9, right child 20 (with children 15, 7) → Output: [[3], [9, 20], [15, 7]]

Solution:

FUNCTION level_order_traversal(root):
    IF root = null:
        RETURN empty_array()
    
    result = empty_array()
    queue = empty_array()
    ADD root TO queue
    
    WHILE length(queue) > 0:
        level_size = length(queue)
        current_level = empty_array()
        
        processed = 0
        WHILE processed < level_size:
            node = REMOVE first element FROM queue
            ADD node.value TO current_level
            
            IF node.left != null:
                ADD node.left TO queue
            
            IF node.right != null:
                ADD node.right TO queue
            
            processed = processed + 1
        
        ADD current_level TO result
    
    RETURN result

WHY this works: We use a queue to process nodes level by level. The key insight is tracking the current level size - this lets us know when we’ve finished processing all nodes at the current level. We process exactly that many nodes, adding their children to the queue for the next level. This is the foundation of breadth-first search and many tree algorithms.

Question 4: Validate Binary Search Tree

Problem: Determine if a binary tree is a valid binary search tree.

Example: A BST where left subtree values < root < right subtree values, recursively.

Solution:

FUNCTION is_valid_bst(root):
    RETURN validate_bst_helper(root, null, null)

FUNCTION validate_bst_helper(node, min_val, max_val):
    IF node = null:
        RETURN true
    
    IF min_val != null AND node.value <= min_val:
        RETURN false
    
    IF max_val != null AND node.value >= max_val:
        RETURN false
    
    // Recursively validate left and right subtrees with updated bounds
    left_valid = validate_bst_helper(node.left, min_val, node.value)
    right_valid = validate_bst_helper(node.right, node.value, max_val)
    
    RETURN left_valid AND right_valid

WHY this works: The naive approach of just checking if left < root < right at each node doesn’t work because it doesn’t consider the global constraints. We need to track the valid range for each node. As we go left, the maximum allowed value becomes the parent’s value. As we go right, the minimum allowed value becomes the parent’s value. This ensures the BST property holds globally.

Question 5: Course Schedule (Topological Sort)

Problem: Given courses and prerequisites, determine if it’s possible to finish all courses.

Example: Input: numCourses=2, prerequisites=[[1,0]] → Output: true (take course 0, then course 1)

Solution:

FUNCTION can_finish_courses(num_courses, prerequisites):
    // Build adjacency list and count incoming edges
    graph = empty_array_of_size(num_courses)
    in_degree = empty_array_of_size(num_courses)
    
    index = 0
    WHILE index < num_courses:
        graph[index] = empty_array()
        in_degree[index] = 0
        index = index + 1
    
    // Process prerequisites
    index = 0
    WHILE index < length(prerequisites):
        course = prerequisites[index][0]
        prereq = prerequisites[index][1]
        
        ADD course TO graph[prereq]
        in_degree[course] = in_degree[course] + 1
        
        index = index + 1
    
    // Find courses with no prerequisites
    queue = empty_array()
    index = 0
    WHILE index < num_courses:
        IF in_degree[index] = 0:
            ADD index TO queue
        index = index + 1
    
    completed = 0
    
    WHILE length(queue) > 0:
        current = REMOVE first element FROM queue
        completed = completed + 1
        
        // Process all courses that depend on current course
        neighbor_index = 0
        WHILE neighbor_index < length(graph[current]):
            neighbor = graph[current][neighbor_index]
            in_degree[neighbor] = in_degree[neighbor] - 1
            
            IF in_degree[neighbor] = 0:
                ADD neighbor TO queue
            
            neighbor_index = neighbor_index + 1
    
    RETURN completed = num_courses

WHY this works: This is a cycle detection problem in disguise. If there’s a cycle in the prerequisite graph, we can’t complete all courses. We use topological sorting with Kahn’s algorithm: start with courses that have no prerequisites, then “remove” them and their outgoing edges, revealing new courses with no remaining prerequisites. If we can process all courses this way, there’s no cycle.

Question 6: Longest Increasing Subsequence

Problem: Find the length of the longest strictly increasing subsequence.

Example: Input: [10, 9, 2, 5, 3, 7, 101, 18] → Output: 4 (subsequence: [2, 3, 7, 101])

Solution:

FUNCTION longest_increasing_subsequence(arr):
    IF length(arr) = 0:
        RETURN 0
    
    // dp[i] represents length of LIS ending at index i
    dp = empty_array()
    index = 0
    
    WHILE index < length(arr):
        dp[index] = 1  // Each element forms a subsequence of length 1
        index = index + 1
    
    index = 1
    WHILE index < length(arr):
        j = 0
        WHILE j < index:
            IF arr[j] < arr[index]:
                dp[index] = max(dp[index], dp[j] + 1)
            j = j + 1
        index = index + 1
    
    // Find the maximum length
    max_length = dp[0]
    index = 1
    WHILE index < length(arr):
        IF dp[index] > max_length:
            max_length = dp[index]
        index = index + 1
    
    RETURN max_length

WHY this works: This is a classic dynamic programming problem. For each position, we ask: “What’s the longest increasing subsequence I can form ending at this position?” We can extend any previous subsequence if the current element is larger than the last element of that subsequence. The key insight is that we build the solution incrementally, using previously computed results.

Question 7: Word Break Problem

Problem: Given a string and a dictionary of words, determine if the string can be segmented into space-separated dictionary words.

Example: Input: s=“leetcode”, wordDict=[“leet”,“code”] → Output: true

Solution:

FUNCTION word_break(text, word_dict):
    // Convert dictionary to set for O(1) lookup
    word_set = empty_set()
    index = 0
    WHILE index < length(word_dict):
        ADD word_dict[index] TO word_set
        index = index + 1
    
    // dp[i] represents whether substring from 0 to i can be segmented
    dp = empty_array()
    index = 0
    WHILE index <= length(text):
        dp[index] = false
        index = index + 1
    
    dp[0] = true  // Empty string can always be segmented
    
    index = 1
    WHILE index <= length(text):
        j = 0
        WHILE j < index:
            substring = get_substring(text, j, index - 1)
            IF dp[j] = true AND substring IN word_set:
                dp[index] = true
                BREAK
            j = j + 1
        index = index + 1
    
    RETURN dp[length(text)]

WHY this works: We use dynamic programming with the insight that if we can segment the string up to position j, and the substring from j to i is in the dictionary, then we can segment up to position i. We build this incrementally, checking all possible split points. The time complexity is O(n²) where n is the string length.

Question 8: Combination Sum

Problem: Given an array of distinct integers and a target, find all unique combinations that sum to the target.

Example: Input: candidates=[2,3,6,7], target=7 → Output: [[2,2,3],[7]]

Solution:

FUNCTION combination_sum(candidates, target):
    result = empty_array()
    current_combination = empty_array()
    
    CALL find_combinations(candidates, target, 0, current_combination, result)
    RETURN result

FUNCTION find_combinations(candidates, remaining, start_index, current, result):
    IF remaining = 0:
        ADD copy_of(current) TO result
        RETURN
    
    IF remaining < 0:
        RETURN
    
    index = start_index
    WHILE index < length(candidates):
        candidate = candidates[index]
        
        // Include current candidate
        ADD candidate TO current
        
        // Recursively find combinations (can reuse same candidate)
        CALL find_combinations(candidates, remaining - candidate, index, current, result)
        
        // Backtrack
        REMOVE last element FROM current
        
        index = index + 1

WHY this works: This is another backtracking problem. We explore all possible combinations by either including or excluding each candidate. The key insight is that we can reuse the same candidate multiple times, so we don’t increment the start_index when recursing. We backtrack by removing the last added candidate when we return from recursion. This systematically explores all valid combinations.

Question 9: Clone a Linked List with Random Pointer

Problem: Clone a linked list where each node has a next pointer and a random pointer.

Example: Each node points to next node and potentially any other node in the list.

Solution:

FUNCTION clone_linked_list(head):
    IF head = null:
        RETURN null
    
    node_map = empty_map()
    
    // First pass: create all nodes
    current = head
    WHILE current != null:
        new_node = create_node(current.val)
        node_map[current] = new_node
        current = current.next
    
    // Second pass: set up pointers
    current = head
    WHILE current != null:
        cloned_node = node_map[current]
        
        IF current.next != null:
            cloned_node.next = node_map[current.next]
        
        IF current.random != null:
            cloned_node.random = node_map[current.random]
        
        current = current.next
    
    RETURN node_map[head]

WHY this works: The challenge is that we need to clone nodes that might reference other nodes we haven’t created yet. We solve this with a two-pass approach: first create all nodes and store the mapping from original to clone, then set up all the pointers using the mapping. This ensures every node exists before we try to reference it.

Question 10: Merge K Sorted Lists

Problem: Merge k sorted linked lists into one sorted linked list.

Example: Input: [[1,4,5],[1,3,4],[2,6]] → Output: [1,1,2,3,4,4,5,6]

Solution:

FUNCTION merge_k_lists(lists):
    IF length(lists) = 0:
        RETURN null
    
    WHILE length(lists) > 1:
        merged_lists = empty_array()
        
        index = 0
        WHILE index < length(lists):
            list1 = lists[index]
            list2 = null
            
            IF index + 1 < length(lists):
                list2 = lists[index + 1]
            
            merged = merge_two_lists(list1, list2)
            ADD merged TO merged_lists
            
            index = index + 2
        
        lists = merged_lists
    
    RETURN lists[0]

FUNCTION merge_two_lists(list1, list2):
    dummy = create_node(0)
    current = dummy
    
    WHILE list1 != null AND list2 != null:
        IF list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        ELSE:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    // Add remaining nodes
    IF list1 != null:
        current.next = list1
    ELSE:
        current.next = list2
    
    RETURN dummy.next

WHY this works: We use a divide-and-conquer approach. Instead of merging all lists at once, we pair them up and merge each pair, then repeat until we have one list. This is more efficient than merging one list at a time. The time complexity is O(n log k) where n is the total number of nodes and k is the number of lists.

Question 11: Subarray Sum Equals K

Problem: Find the number of continuous subarrays whose sum equals k.

Example: Input: nums=[1,1,1], k=2 → Output: 2

Solution:

FUNCTION subarray_sum_k(nums, k):
    count = 0
    cumulative_sum = 0
    sum_count = empty_map()
    
    // Initialize with sum 0 occurring once (empty subarray)
    sum_count[0] = 1
    
    index = 0
    WHILE index < length(nums):
        cumulative_sum = cumulative_sum + nums[index]
        
        // Check if there's a prefix sum such that current_sum - prefix_sum = k
        needed_sum = cumulative_sum - k
        
        IF needed_sum IN sum_count:
            count = count + sum_count[needed_sum]
        
        // Add current cumulative sum to our map
        IF cumulative_sum IN sum_count:
            sum_count[cumulative_sum] = sum_count[cumulative_sum] + 1
        ELSE:
            sum_count[cumulative_sum] = 1
        
        index = index + 1
    
    RETURN count

WHY this works: We use the insight that if we have two prefix sums where sum₂ - sum₁ = k, then the subarray between those positions sums to k. We track cumulative sums and count how many times each sum has occurred. For each position, we check if there’s a previous prefix sum that would give us the target k when subtracted from the current sum.

Question 12: Maximum Product Subarray

Problem: Find the contiguous subarray with the largest product.

Example: Input: [2,3,-2,4] → Output: 6 (subarray [2,3])

Solution:

FUNCTION max_product_subarray(nums):
    IF length(nums) = 0:
        RETURN 0
    
    max_product = nums[0]
    current_max = nums[0]
    current_min = nums[0]  // Track minimum because negative * negative = positive
    
    index = 1
    WHILE index < length(nums):
        current_num = nums[index]
        
        // When we encounter a negative number, max and min swap roles
        IF current_num < 0:
            temp = current_max
            current_max = current_min
            current_min = temp
        
        // Update current max and min
        current_max = max(current_num, current_max * current_num)
        current_min = min(current_num, current_min * current_num)
        
        // Update global maximum
        max_product = max(max_product, current_max)
        
        index = index + 1
    
    RETURN max_product

WHY this works: This is a variation of Kadane’s algorithm adapted for products. The key insight is that we need to track both maximum and minimum products because a negative number can turn a small (negative) product into a large (positive) one. When we encounter a negative number, the roles of max and min effectively swap.

Question 13: Rotting Oranges

Problem: In a grid, fresh oranges become rotten if adjacent to rotten oranges. Find minimum time for all oranges to rot.

Example: Grid where 0=empty, 1=fresh, 2=rotten. Fresh oranges adjacent to rotten ones rot each minute.

Solution:

FUNCTION rotting_oranges(grid):
    IF length(grid) = 0:
        RETURN 0
    
    rows = length(grid)
    cols = length(grid[0])
    queue = empty_array()
    fresh_count = 0
    
    // Find all rotten oranges and count fresh ones
    row = 0
    WHILE row < rows:
        col = 0
        WHILE col < cols:
            IF grid[row][col] = 2:
                ADD [row, col] TO queue
            ELSE IF grid[row][col] = 1:
                fresh_count = fresh_count + 1
            col = col + 1
        row = row + 1
    
    IF fresh_count = 0:
        RETURN 0
    
    directions = [[0,1], [0,-1], [1,0], [-1,0]]
    minutes = 0
    
    WHILE length(queue) > 0 AND fresh_count > 0:
        size = length(queue)
        
        processed = 0
        WHILE processed < size:
            current = REMOVE first element FROM queue
            current_row = current[0]
            current_col = current[1]
            
            dir_index = 0
            WHILE dir_index < 4:
                new_row = current_row + directions[dir_index][0]
                new_col = current_col + directions[dir_index][1]
                
                IF new_row >= 0 AND new_row < rows AND new_col >= 0 AND new_col < cols:
                    IF grid[new_row][new_col] = 1:
                        grid[new_row][new_col] = 2
                        fresh_count = fresh_count - 1
                        ADD [new_row, new_col] TO queue
                
                dir_index = dir_index + 1
            
            processed = processed + 1
        
        minutes = minutes + 1
    
    RETURN fresh_count = 0 ? minutes : -1

WHY this works: This is a multi-source BFS problem. We start with all initially rotten oranges in our queue and process them level by level. Each level represents one minute passing. We rot all fresh oranges adjacent to currently rotten ones, then move to the next minute. The key insight is processing all oranges that rot at the same time together.

Question 14: Reconstruct Itinerary

Problem: Given flight tickets, reconstruct the itinerary starting from “JFK”.

Example: Input: [[“MUC”,“LHR”],[“JFK”,“MUC”],[“SFO”,“SJC”],[“LHR”,“SFO”]] → Output: [“JFK”,“MUC”,“LHR”,“SFO”,“SJC”]

Solution:

FUNCTION find_itinerary(tickets):
    graph = empty_map()
    
    // Build adjacency list
    index = 0
    WHILE index < length(tickets):
        from_city = tickets[index][0]
        to_city = tickets[index][1]
        
        IF from_city NOT IN graph:
            graph[from_city] = empty_array()
        
        ADD to_city TO graph[from_city]
        index = index + 1
    
    // Sort destinations for each city (to ensure lexicographic order)
    FOR each city IN graph:
        SORT graph[city] IN ascending order
    
    result = empty_array()
    CALL dfs("JFK", graph, result)
    
    REVERSE result
    RETURN result

FUNCTION dfs(city, graph, result):
    IF city IN graph:
        destinations = graph[city]
        
        WHILE length(destinations) > 0:
            next_city = REMOVE first element FROM destinations
            CALL dfs(next_city, graph, result)
    
    ADD city TO result

WHY this works: This is an Eulerian path problem. We need to visit every edge exactly once. We use DFS but with a twist - we remove edges as we traverse them and add cities to our result in post-order (after visiting all destinations). This ensures we don’t get stuck in dead ends and that we build the path correctly when reversed.

Question 15: Minimum Window Substring

Problem: Find the minimum window substring that contains all characters of a given string.

Example: Input: s=“ADOBECODEBANC”, t=“ABC” → Output: “BANC”

Solution:

FUNCTION min_window_substring(s, t):
    IF length(s) = 0 OR length(t) = 0:
        RETURN ""
    
    // Count characters in t
    t_count = empty_map()
    index = 0
    WHILE index < length(t):
        char = t[index]
        IF char IN t_count:
            t_count[char] = t_count[char] + 1
        ELSE:
            t_count[char] = 1
        index = index + 1
    
    required_chars = length(t_count)
    formed_chars = 0
    
    window_count = empty_map()
    left = 0
    right = 0
    
    min_len = infinity
    min_left = 0
    min_right = 0
    
    WHILE right < length(s):
        char = s[right]
        
        // Add character to window
        IF char IN window_count:
            window_count[char] = window_count[char] + 1
        ELSE:
            window_count[char] = 1
        
        // Check if current character's frequency matches required frequency
        IF char IN t_count AND window_count[char] = t_count[char]:
            formed_chars = formed_chars + 1
        
        // Try to shrink window from left
        WHILE left <= right AND formed_chars = required_chars:
            // Update minimum window if current is smaller
            IF right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left
                min_right = right
            
            // Remove leftmost character
            left_char = s[left]
            window_count[left_char] = window_count[left_char] - 1
            
            IF left_char IN t_count AND window_count[left_char] < t_count[left_char]:
                formed_chars = formed_chars - 1
            
            left = left + 1
        
        right = right + 1
    
    RETURN min_len = infinity ? "" : substring(s, min_left, min_right)

WHY this works: We use the sliding window technique with two pointers. We expand the right pointer to include more characters until we have a valid window (contains all characters of t). Then we try to shrink from the left while maintaining validity. We track character frequencies and how many unique characters have the required frequency. This gives us O(n) time complexity.

Question 16: Serialize and Deserialize Binary Tree

Problem: Design algorithms to serialize a binary tree to a string and deserialize it back.

Example: Tree → “1,2,null,null,3,4,null,null,5,null,null” → Tree

Solution:

FUNCTION serialize(root):
    result = empty_array()
    CALL serialize_helper(root, result)
    RETURN join_array(result, ",")

FUNCTION serialize_helper(node, result):
    IF node = null:
        ADD "null" TO result
        RETURN
    
    ADD string(node.val) TO result
    CALL serialize_helper(node.left, result)
    CALL serialize_helper(node.right, result)

FUNCTION deserialize(data):
    tokens = split_string(data, ",")
    index = 0
    RETURN deserialize_helper(tokens, index)

FUNCTION deserialize_helper(tokens, index):
    IF index >= length(tokens) OR tokens[index] = "null":
        index = index + 1
        RETURN null
    
    node = create_node(parse_int(tokens[index]))
    index = index + 1
    
    node.left = deserialize_helper(tokens, index)
    node.right = deserialize_helper(tokens, index)
    
    RETURN node

WHY this works: We use preorder traversal for serialization, which naturally gives us the structure we need for reconstruction. We include null nodes to preserve the tree structure. During deserialization, we use the same preorder pattern: create the node, then recursively build left and right subtrees. The key insight is that preorder traversal gives us nodes in the exact order we need to reconstruct the tree.

Question 17: Trapping Rain Water

Problem: Given elevation heights, calculate how much water can be trapped after raining.

Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] → Output: 6

Solution:

FUNCTION trap_rain_water(heights):
    IF length(heights) = 0:
        RETURN 0
    
    left = 0
    right = length(heights) - 1
    left_max = 0
    right_max = 0
    water_trapped = 0
    
    WHILE left < right:
        IF heights[left] < heights[right]:
            IF heights[left] >= left_max:
                left_max = heights[left]
            ELSE:
                water_trapped = water_trapped + (left_max - heights[left])
            left = left + 1
        ELSE:
            IF heights[right] >= right_max:
                right_max = heights[right]
            ELSE:
                water_trapped = water_trapped + (right_max - heights[right])
            right = right - 1
    
    RETURN water_trapped

WHY this works: We use two pointers moving towards each other. The key insight is that water level at any position depends on the minimum of the maximum heights to its left and right. By maintaining left_max and right_max and always processing the side with the smaller height, we ensure we’re always calculating water correctly. This avoids the need to pre-compute all left and right maximums.

Question 18: Edit Distance

Problem: Find minimum operations (insert, delete, replace) to convert one string to another.

Example: Input: word1=“horse”, word2=“ros” → Output: 3

Solution:

FUNCTION edit_distance(word1, word2):
    m = length(word1)
    n = length(word2)
    
    // Create DP table
    dp = empty_2d_array(m + 1, n + 1)
    
    // Initialize base cases
    i = 0
    WHILE i <= m:
        dp[i][0] = i  // Delete all characters from word1
        i = i + 1
    
    j = 0
    WHILE j <= n:
        dp[0][j] = j  // Insert all characters to make word2
        j = j + 1
    
    // Fill the DP table
    i = 1
    WHILE i <= m:
        j = 1
        WHILE j <= n:
            IF word1[i - 1] = word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  // No operation needed
            ELSE:
                // Take minimum of three operations
                replace = dp[i - 1][j - 1] + 1
                delete = dp[i - 1][j] + 1
                insert = dp[i][j - 1] + 1
                
                dp[i][j] = min(replace, min(delete, insert))
            j = j + 1
        i = i + 1
    
    RETURN dp[m][n]

WHY this works: This is a classic dynamic programming problem. We build a table where dp[i][j] represents the minimum operations to convert the first i characters of word1 to the first j characters of word2. If characters match, we take the diagonal value. If they don’t match, we consider three operations and take the minimum. Each operation corresponds to a specific movement in the DP table.

Question 19: Palindrome Partitioning

Problem: Partition a string such that every substring is a palindrome. Return all possible partitions.

Example: Input: “aab” → Output: [[“a”,“a”,“b”],[“aa”,“b”]]

Solution:

FUNCTION partition_palindromes(s):
    result = empty_array()
    current_partition = empty_array()
    
    CALL partition_helper(s, 0, current_partition, result)
    RETURN result

FUNCTION partition_helper(s, start, current_partition, result):
    IF start = length(s):
        ADD copy_of(current_partition) TO result
        RETURN
    
    index = start
    WHILE index < length(s):
        substring = get_substring(s, start, index)
        
        IF is_palindrome(substring):
            ADD substring TO current_partition
            CALL partition_helper(s, index + 1, current_partition, result)
            REMOVE last element FROM current_partition  // Backtrack
        
        index = index + 1

FUNCTION is_palindrome(s):
    left = 0
    right = length(s) - 1
    
    WHILE left < right:
        IF s[left] != s[right]:
            RETURN false
        left = left + 1
        right = right - 1
    
    RETURN true

WHY this works: We use backtracking to explore all possible partitions. At each position, we try all possible substrings starting from that position. If a substring is a palindrome, we add it to our current partition and recursively process the remaining string. We backtrack by removing the last added substring when we return from recursion. This systematically explores all valid partitions.

Question 20: Regular Expression Matching

Problem: Implement regular expression matching with ‘.’ and ‘*’ support.

Example: Input: s=“aa”, p=“a*” → Output: true

Solution:

FUNCTION is_match(s, p):
    return match_helper(s, 0, p, 0)

FUNCTION match_helper(s, s_index, p, p_index):
    // Base case: reached end of pattern
    IF p_index = length(p):
        RETURN s_index = length(s)
    
    // Check if current characters match
    first_match = (s_index < length(s)) AND 
                  (p[p_index] = s[s_index] OR p[p_index] = '.')
    
    // Handle '*' case
    IF p_index + 1 < length(p) AND p[p_index + 1] = '*':
        // Two choices: skip pattern (0 matches) or use pattern (1+ matches)
        skip_pattern = match_helper(s, s_index, p, p_index + 2)
        use_pattern = first_match AND match_helper(s, s_index + 1, p, p_index)
        
        RETURN skip_pattern OR use_pattern
    ELSE:
        // Regular character matching
        RETURN first_match AND match_helper(s, s_index + 1, p, p_index + 1)

WHY this works: We use recursion to handle the complex matching rules. The key insight is that ‘’ means “zero or more of the preceding character.” When we encounter a ‘’, we have two choices: skip the pattern entirely (zero matches) or use it if the current character matches (one or more matches). We recursively explore both possibilities. The ‘.’ character matches any single character, which we handle in the first_match check.

Key Intermediate Problem-Solving Patterns

  1. Backtracking - Systematic exploration with undo capability (permutations, combinations)
  2. Dynamic Programming - Breaking problems into subproblems (LIS, edit distance)
  3. Two Pointers - Efficient array/string processing (trapping water, minimum window)
  4. Graph Algorithms - BFS/DFS for complex structures (course schedule, tree traversal)
  5. Sliding Window - Efficient substring problems (minimum window)
  6. Divide and Conquer - Breaking large problems into smaller ones (merge k lists)
  7. Greedy with Proof - Making locally optimal choices (some shortest path problems)
  8. Complex Data Structure Usage - Maps, sets, queues for efficient lookups and processing

Remember, these intermediate problems are about recognizing patterns and applying the right algorithmic technique. The more you practice, the faster you’ll recognize when to use each approach. Don’t worry about getting them perfect on the first try - even experienced developers need time to work through these problems methodically!