Interview Questions - Hard

Dec 13, 2025 · 9 min read · interview algorithms hard leetcode ·

Share on:

Hard-level algorithm interview questions with detailed approach explanations and solutions.

Problem 1: Median of Two Sorted Arrays

Problem: Find median of two sorted arrays in $O(\log(m+n))$ time.

Example:

1Input: nums1 = [1,3], nums2 = [2]
2Output: 2.0
3Explanation: merged = [1,2,3], median = 2

Approach

Key Insight: Binary search on smaller array to partition both arrays.

Goal: Partition arrays so left half ≤ right half.

Steps:

Binary search on smaller array
Calculate partition in second array
Check if valid partition (maxLeft ≤ minRight)
Adjust binary search bounds

Solution

 1func findMedianSortedArrays(nums1, nums2 []int) float64 {
 2    // Ensure nums1 is smaller
 3    if len(nums1) > len(nums2) {
 4        nums1, nums2 = nums2, nums1
 5    }
 6    
 7    m, n := len(nums1), len(nums2)
 8    left, right := 0, m
 9    
10    for left <= right {
11        partition1 := (left + right) / 2
12        partition2 := (m + n + 1) / 2 - partition1
13        
14        maxLeft1 := math.MinInt32
15        if partition1 > 0 {
16            maxLeft1 = nums1[partition1-1]
17        }
18        
19        minRight1 := math.MaxInt32
20        if partition1 < m {
21            minRight1 = nums1[partition1]
22        }
23        
24        maxLeft2 := math.MinInt32
25        if partition2 > 0 {
26            maxLeft2 = nums2[partition2-1]
27        }
28        
29        minRight2 := math.MaxInt32
30        if partition2 < n {
31            minRight2 = nums2[partition2]
32        }
33        
34        if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
35            // Found correct partition
36            if (m + n) % 2 == 0 {
37                return float64(max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0
38            }
39            return float64(max(maxLeft1, maxLeft2))
40        } else if maxLeft1 > minRight2 {
41            right = partition1 - 1
42        } else {
43            left = partition1 + 1
44        }
45    }
46    
47    return 0.0
48}

Time: $O(\log(\min(m, n)))$, Space: $O(1)$

Why binary search: We're finding the correct partition point.

Problem 2: Trapping Rain Water

Problem: Calculate how much water can be trapped after raining.

Example:

1Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
2Output: 6

Approach

Key Insight: Water at position i = min(maxLeft, maxRight) - height[i]

Pattern: Two pointers from both ends, track max heights.

Solution

 1func trap(height []int) int {
 2    if len(height) == 0 {
 3        return 0
 4    }
 5    
 6    left, right := 0, len(height)-1
 7    leftMax, rightMax := 0, 0
 8    water := 0
 9    
10    for left < right {
11        if height[left] < height[right] {
12            if height[left] >= leftMax {
13                leftMax = height[left]
14            } else {
15                water += leftMax - height[left]
16            }
17            left++
18        } else {
19            if height[right] >= rightMax {
20                rightMax = height[right]
21            } else {
22                water += rightMax - height[right]
23            }
24            right--
25        }
26    }
27    
28    return water
29}

Time: $O(n)$, Space: $O(1)$

Why this works: Process from lower side, guarantees water is trapped by higher side.

Problem 3: Regular Expression Matching

Problem: Implement regex matching with '.' and '*'.

Example:

1Input: s = "aa", p = "a*"
2Output: true
3Explanation: '*' means zero or more of preceding element

Approach

Key Insight: Dynamic programming with pattern matching logic.

DP State: $dp[i][j]$ = does s[0:i] match p[0:j]?

Solution

 1func isMatch(s string, p string) bool {
 2    m, n := len(s), len(p)
 3    dp := make([][]bool, m+1)
 4    for i := range dp {
 5        dp[i] = make([]bool, n+1)
 6    }
 7    
 8    dp[0][0] = true
 9    
10    // Handle patterns like a*, a*b*, etc.
11    for j := 2; j <= n; j++ {
12        if p[j-1] == '*' {
13            dp[0][j] = dp[0][j-2]
14        }
15    }
16    
17    for i := 1; i <= m; i++ {
18        for j := 1; j <= n; j++ {
19            if p[j-1] == '*' {
20                // Zero occurrences or one+ occurrences
21                dp[i][j] = dp[i][j-2] || 
22                          (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'))
23            } else if p[j-1] == '.' || s[i-1] == p[j-1] {
24                dp[i][j] = dp[i-1][j-1]
25            }
26        }
27    }
28    
29    return dp[m][n]
30}

Time: $O(m \times n)$, Space: $O(m \times n)$

Critical: '*' matches zero or more of preceding element.

Problem 4: Merge K Sorted Lists

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

Example:

1Input: lists = [[1,4,5],[1,3,4],[2,6]]
2Output: [1,1,2,3,4,4,5,6]

Approach

Key Insight: Use min heap to track smallest element from each list.

Pattern: K-way merge using priority queue.

Solution

 1import "container/heap"
 2
 3type MinHeap []*ListNode
 4
 5func (h MinHeap) Len() int           { return len(h) }
 6func (h MinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
 7func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 8
 9func (h *MinHeap) Push(x interface{}) {
10    *h = append(*h, x.(*ListNode))
11}
12
13func (h *MinHeap) Pop() interface{} {
14    old := *h
15    n := len(old)
16    x := old[n-1]
17    *h = old[0 : n-1]
18    return x
19}
20
21func mergeKLists(lists []*ListNode) *ListNode {
22    h := &MinHeap{}
23    heap.Init(h)
24    
25    // Add first node from each list
26    for _, list := range lists {
27        if list != nil {
28            heap.Push(h, list)
29        }
30    }
31    
32    dummy := &ListNode{}
33    curr := dummy
34    
35    for h.Len() > 0 {
36        node := heap.Pop(h).(*ListNode)
37        curr.Next = node
38        curr = curr.Next
39        
40        if node.Next != nil {
41            heap.Push(h, node.Next)
42        }
43    }
44    
45    return dummy.Next
46}

Time: $O(N \log k)$ where N is total nodes, k is number of lists
Space: $O(k)$ for heap

Alternative: Divide and conquer (merge pairs recursively).

Problem 5: Longest Valid Parentheses

Problem: Find length of longest valid parentheses substring.

Example:

1Input: s = "(()"
2Output: 2
3Explanation: "()" is longest valid

Approach

Key Insight: Use stack to track indices, or two-pass scan.

Pattern: Stack-based matching with index tracking.

Solution (Stack)

 1func longestValidParentheses(s string) int {
 2    stack := []int{-1} // Base for valid substring
 3    maxLen := 0
 4    
 5    for i, char := range s {
 6        if char == '(' {
 7            stack = append(stack, i)
 8        } else {
 9            stack = stack[:len(stack)-1] // Pop
10            
11            if len(stack) == 0 {
12                stack = append(stack, i) // New base
13            } else {
14                maxLen = max(maxLen, i - stack[len(stack)-1])
15            }
16        }
17    }
18    
19    return maxLen
20}

Time: $O(n)$, Space: $O(n)$

Solution (Two-Pass, O(1) Space)

 1func longestValidParentheses(s string) int {
 2    left, right, maxLen := 0, 0, 0
 3    
 4    // Left to right
 5    for i := 0; i < len(s); i++ {
 6        if s[i] == '(' {
 7            left++
 8        } else {
 9            right++
10        }
11        
12        if left == right {
13            maxLen = max(maxLen, 2*right)
14        } else if right > left {
15            left, right = 0, 0
16        }
17    }
18    
19    left, right = 0, 0
20    
21    // Right to left
22    for i := len(s)-1; i >= 0; i-- {
23        if s[i] == '(' {
24            left++
25        } else {
26            right++
27        }
28        
29        if left == right {
30            maxLen = max(maxLen, 2*left)
31        } else if left > right {
32            left, right = 0, 0
33        }
34    }
35    
36    return maxLen
37}

Time: $O(n)$, Space: $O(1)$

Problem 6: Word Ladder

Problem: Find shortest transformation sequence from beginWord to endWord.

Example:

1Input: beginWord = "hit", endWord = "cog", 
2       wordList = ["hot","dot","dog","lot","log","cog"]
3Output: 5
4Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog"

Approach

Key Insight: BFS on word graph (words differ by one letter are connected).

Pattern: Shortest path in unweighted graph.

Solution

 1func ladderLength(beginWord string, endWord string, wordList []string) int {
 2    wordSet := make(map[string]bool)
 3    for _, word := range wordList {
 4        wordSet[word] = true
 5    }
 6    
 7    if !wordSet[endWord] {
 8        return 0
 9    }
10    
11    queue := []string{beginWord}
12    visited := make(map[string]bool)
13    visited[beginWord] = true
14    level := 1
15    
16    for len(queue) > 0 {
17        size := len(queue)
18        
19        for i := 0; i < size; i++ {
20            word := queue[0]
21            queue = queue[1:]
22            
23            if word == endWord {
24                return level
25            }
26            
27            // Try all possible one-letter changes
28            for j := 0; j < len(word); j++ {
29                for ch := 'a'; ch <= 'z'; ch++ {
30                    if rune(word[j]) == ch {
31                        continue
32                    }
33                    
34                    newWord := word[:j] + string(ch) + word[j+1:]
35                    
36                    if wordSet[newWord] && !visited[newWord] {
37                        queue = append(queue, newWord)
38                        visited[newWord] = true
39                    }
40                }
41            }
42        }
43        
44        level++
45    }
46    
47    return 0
48}

Time: $O(M^2 \times N)$ where M is word length, N is number of words
Space: $O(M \times N)$

Optimization: Bidirectional BFS from both ends.

Problem 7: Minimum Window Substring

Problem: Find minimum window in s containing all characters of t.

Example:

1Input: s = "ADOBECODEBANC", t = "ABC"
2Output: "BANC"

Approach

Key Insight: Sliding window with character frequency tracking.

Pattern: Expand right to include all chars, contract left to minimize.

Solution

 1func minWindow(s string, t string) string {
 2    if len(s) < len(t) {
 3        return ""
 4    }
 5    
 6    need := make(map[byte]int)
 7    for i := 0; i < len(t); i++ {
 8        need[t[i]]++
 9    }
10    
11    window := make(map[byte]int)
12    left, right := 0, 0
13    valid := 0
14    start, length := 0, len(s)+1
15    
16    for right < len(s) {
17        c := s[right]
18        right++
19        
20        if _, exists := need[c]; exists {
21            window[c]++
22            if window[c] == need[c] {
23                valid++
24            }
25        }
26        
27        for valid == len(need) {
28            if right - left < length {
29                start = left
30                length = right - left
31            }
32            
33            d := s[left]
34            left++
35            
36            if _, exists := need[d]; exists {
37                if window[d] == need[d] {
38                    valid--
39                }
40                window[d]--
41            }
42        }
43    }
44    
45    if length == len(s)+1 {
46        return ""
47    }
48    return s[start : start+length]
49}

Time: $O(m + n)$, Space: $O(m + n)$

Common Patterns in Hard Problems

Binary Search on Answer: Median of sorted arrays, capacity problems
Advanced DP: Edit distance, regex matching
Heap/Priority Queue: Merge K lists, sliding window maximum
Graph Algorithms: Word ladder, shortest path with obstacles
Sliding Window: Minimum window substring
Backtracking with Pruning: N-Queens, Sudoku solver
Divide and Conquer: Merge K lists

Approach Strategy for Hard Problems

Break down: Identify subproblems
Pattern recognition: Which technique applies?
Start simple: Solve easier version first
Optimize incrementally: Don't aim for optimal immediately
Consider multiple approaches: DP vs. greedy vs. graph

Interview Tips for Hard Problems

✅ Do:

Discuss multiple approaches
Explain trade-offs
Start with working solution, then optimize
Ask if optimization is needed

❌ Don't:

Panic if you don't see solution immediately
Code without discussing approach
Ignore hints from interviewer
Give up

Remember: Process matters more than perfect solution!

Related Snippets

Common Interview Challenges
A curated collection of the most common algorithm interview problems with …
Interview Questions - Easy
Easy-level algorithm interview questions with detailed approach explanations and …
Interview Questions - Medium
Medium-level algorithm interview questions with detailed approach explanations …