Interview Questions - Medium
Medium-level algorithm interview questions with detailed approach explanations and solutions.
Problem 1: Longest Substring Without Repeating Characters
Problem: Find length of longest substring without repeating characters.
Example:
1Input: s = "abcabcbb"
2Output: 3
3Explanation: "abc" is longest without repeats
Approach
Key Insight: Sliding window with hash map to track last seen position.
Pattern: Expand window when no repeat, contract when repeat found.
Steps:
- Use map to store character -> last seen index
- Expand right pointer
- If character seen and within window, move left pointer
- Track maximum length
Solution
1func lengthOfLongestSubstring(s string) int {
2 charIndex := make(map[byte]int)
3 left, maxLen := 0, 0
4
5 for right := 0; right < len(s); right++ {
6 char := s[right]
7
8 // If char seen and within current window
9 if lastIndex, exists := charIndex[char]; exists && lastIndex >= left {
10 left = lastIndex + 1
11 }
12
13 charIndex[char] = right
14 maxLen = max(maxLen, right - left + 1)
15 }
16
17 return maxLen
18}
Time: $O(n)$, Space: $O(min(n, m))$ where m is charset size
Why this works: We maintain a valid window [left, right] with no repeats.
Problem 2: 3Sum
Problem: Find all unique triplets that sum to zero.
Example:
1Input: nums = [-1,0,1,2,-1,-4]
2Output: [[-1,-1,2],[-1,0,1]]
Approach
Key Insight: Sort array, fix one number, use two pointers for remaining two.
Pattern: Reduce to 2Sum problem.
Steps:
- Sort array
- For each number, find pairs that sum to -number
- Skip duplicates
Solution
1func threeSum(nums []int) [][]int {
2 sort.Ints(nums)
3 result := [][]int{}
4
5 for i := 0; i < len(nums)-2; i++ {
6 // Skip duplicates for first number
7 if i > 0 && nums[i] == nums[i-1] {
8 continue
9 }
10
11 target := -nums[i]
12 left, right := i+1, len(nums)-1
13
14 for left < right {
15 sum := nums[left] + nums[right]
16
17 if sum == target {
18 result = append(result, []int{nums[i], nums[left], nums[right]})
19
20 // Skip duplicates
21 for left < right && nums[left] == nums[left+1] {
22 left++
23 }
24 for left < right && nums[right] == nums[right-1] {
25 right--
26 }
27
28 left++
29 right--
30 } else if sum < target {
31 left++
32 } else {
33 right--
34 }
35 }
36 }
37
38 return result
39}
Time: $O(n^2)$, Space: $O(1)$ excluding output
Critical: Must skip duplicates to avoid duplicate triplets.
Problem 3: Group Anagrams
Problem: Group strings that are anagrams of each other.
Example:
1Input: strs = ["eat","tea","tan","ate","nat","bat"]
2Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Approach
Key Insight: Anagrams have same sorted characters or same character frequency.
Pattern: Use hash map with sorted string as key.
Solution
1import "sort"
2import "strings"
3
4func groupAnagrams(strs []string) [][]string {
5 groups := make(map[string][]string)
6
7 for _, str := range strs {
8 // Sort characters to create key
9 chars := []rune(str)
10 sort.Slice(chars, func(i, j int) bool {
11 return chars[i] < chars[j]
12 })
13 key := string(chars)
14
15 groups[key] = append(groups[key], str)
16 }
17
18 result := [][]string{}
19 for _, group := range groups {
20 result = append(result, group)
21 }
22
23 return result
24}
25
26// Alternative: Use character count as key
27func groupAnagramsCount(strs []string) [][]string {
28 groups := make(map[[26]int][]string)
29
30 for _, str := range strs {
31 var count [26]int
32 for _, ch := range str {
33 count[ch-'a']++
34 }
35 groups[count] = append(groups[count], str)
36 }
37
38 result := [][]string{}
39 for _, group := range groups {
40 result = append(result, group)
41 }
42
43 return result
44}
Time: $O(n \times k \log k)$ where k is max string length
Space: $O(n \times k)$
Alternative: Character count approach is $O(n \times k)$ time.
Problem 4: Product of Array Except Self
Problem: Return array where each element is product of all others (no division).
Example:
1Input: nums = [1,2,3,4]
2Output: [24,12,8,6]
Approach
Key Insight: Product = (product of all left) × (product of all right).
Pattern: Two passes - left to right, then right to left.
Solution
1func productExceptSelf(nums []int) []int {
2 n := len(nums)
3 result := make([]int, n)
4
5 // Pass 1: Calculate left products
6 result[0] = 1
7 for i := 1; i < n; i++ {
8 result[i] = result[i-1] * nums[i-1]
9 }
10
11 // Pass 2: Multiply by right products
12 rightProduct := 1
13 for i := n-1; i >= 0; i-- {
14 result[i] *= rightProduct
15 rightProduct *= nums[i]
16 }
17
18 return result
19}
Time: $O(n)$, Space: $O(1)$ excluding output
Why this works: result[i] = (nums[0]×...×nums[i-1]) × (nums[i+1]×...×nums[n-1])
Problem 5: Coin Change
Problem: Find minimum coins needed to make amount (infinite supply of each coin).
Example:
1Input: coins = [1,2,5], amount = 11
2Output: 3
3Explanation: 11 = 5 + 5 + 1
Approach
Key Insight: Dynamic programming - build up from smaller amounts.
Recurrence: $dp[i] = \min(dp[i], dp[i - coin] + 1)$ for each coin
Solution
1func coinChange(coins []int, amount int) int {
2 dp := make([]int, amount+1)
3
4 // Initialize with "impossible" value
5 for i := 1; i <= amount; i++ {
6 dp[i] = amount + 1
7 }
8 dp[0] = 0
9
10 for i := 1; i <= amount; i++ {
11 for _, coin := range coins {
12 if coin <= i {
13 dp[i] = min(dp[i], dp[i-coin] + 1)
14 }
15 }
16 }
17
18 if dp[amount] > amount {
19 return -1 // Impossible
20 }
21 return dp[amount]
22}
Time: $O(amount \times coins)$, Space: $O(amount)$
Why DP: Optimal substructure - optimal solution uses optimal solutions to subproblems.
Problem 6: Number of Islands
Problem: Count number of islands in 2D grid ('1' = land, '0' = water).
Example:
1Input: grid = [
2 ["1","1","0","0","0"],
3 ["1","1","0","0","0"],
4 ["0","0","1","0","0"],
5 ["0","0","0","1","1"]
6]
7Output: 3
Approach
Key Insight: DFS/BFS to mark connected components.
Pattern: Graph traversal, mark visited cells.
Solution
1func numIslands(grid [][]byte) int {
2 if len(grid) == 0 {
3 return 0
4 }
5
6 count := 0
7
8 for i := 0; i < len(grid); i++ {
9 for j := 0; j < len(grid[0]); j++ {
10 if grid[i][j] == '1' {
11 dfs(grid, i, j)
12 count++
13 }
14 }
15 }
16
17 return count
18}
19
20func dfs(grid [][]byte, i, j int) {
21 // Boundary check
22 if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] != '1' {
23 return
24 }
25
26 grid[i][j] = '0' // Mark as visited
27
28 // Explore 4 directions
29 dfs(grid, i+1, j)
30 dfs(grid, i-1, j)
31 dfs(grid, i, j+1)
32 dfs(grid, i, j-1)
33}
Time: $O(m \times n)$, Space: $O(m \times n)$ for recursion stack
Alternative: BFS using queue instead of recursion.
Problem 7: Course Schedule (Cycle Detection)
Problem: Can you finish all courses given prerequisites? (Detect cycle in directed graph)
Example:
1Input: numCourses = 2, prerequisites = [[1,0]]
2Output: true
3Explanation: Take course 0, then course 1
Approach
Key Insight: Build dependency graph, detect cycles using DFS.
Pattern: Graph cycle detection with 3 states (unvisited, visiting, visited).
Solution
1func canFinish(numCourses int, prerequisites [][]int) bool {
2 // Build adjacency list
3 graph := make([][]int, numCourses)
4 for _, pre := range prerequisites {
5 graph[pre[1]] = append(graph[pre[1]], pre[0])
6 }
7
8 // 0: unvisited, 1: visiting, 2: visited
9 state := make([]int, numCourses)
10
11 var hasCycle func(int) bool
12 hasCycle = func(course int) bool {
13 if state[course] == 1 {
14 return true // Cycle detected
15 }
16 if state[course] == 2 {
17 return false // Already processed
18 }
19
20 state[course] = 1 // Mark as visiting
21
22 for _, next := range graph[course] {
23 if hasCycle(next) {
24 return true
25 }
26 }
27
28 state[course] = 2 // Mark as visited
29 return false
30 }
31
32 for i := 0; i < numCourses; i++ {
33 if hasCycle(i) {
34 return false
35 }
36 }
37
38 return true
39}
Time: $O(V + E)$, Space: $O(V + E)$
Why 3 states: Distinguish between "not yet visited" and "currently in recursion stack".
Problem 8: Lowest Common Ancestor of Binary Tree
Problem: Find lowest common ancestor of two nodes in binary tree.
Example:
1Input: root = [3,5,1,6,2,0,8], p = 5, q = 1
2Output: 3
Approach
Key Insight: If p and q are in different subtrees, current node is LCA.
Pattern: Recursive tree traversal with bottom-up information passing.
Solution
1func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
2 if root == nil || root == p || root == q {
3 return root
4 }
5
6 left := lowestCommonAncestor(root.Left, p, q)
7 right := lowestCommonAncestor(root.Right, p, q)
8
9 // If both found in different subtrees, current node is LCA
10 if left != nil && right != nil {
11 return root
12 }
13
14 // Return whichever is not nil
15 if left != nil {
16 return left
17 }
18 return right
19}
Time: $O(n)$, Space: $O(h)$ where h is height
Why this works: First node where paths to p and q diverge is the LCA.
Problem 9: Kth Largest Element (QuickSelect)
Problem: Find k-th largest element in unsorted array.
Example:
1Input: nums = [3,2,1,5,6,4], k = 2
2Output: 5
Approach
Key Insight: Use QuickSelect (like QuickSort but only recurse on one side).
Pattern: Partitioning with early termination.
Solution
1func findKthLargest(nums []int, k int) int {
2 return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
3}
4
5func quickSelect(nums []int, left, right, k int) int {
6 if left == right {
7 return nums[left]
8 }
9
10 pivotIndex := partition(nums, left, right)
11
12 if k == pivotIndex {
13 return nums[k]
14 } else if k < pivotIndex {
15 return quickSelect(nums, left, pivotIndex-1, k)
16 } else {
17 return quickSelect(nums, pivotIndex+1, right, k)
18 }
19}
20
21func partition(nums []int, left, right int) int {
22 pivot := nums[right]
23 i := left
24
25 for j := left; j < right; j++ {
26 if nums[j] <= pivot {
27 nums[i], nums[j] = nums[j], nums[i]
28 i++
29 }
30 }
31
32 nums[i], nums[right] = nums[right], nums[i]
33 return i
34}
Time: $O(n)$ average, $O(n^2)$ worst, Space: $O(1)$
Alternative: Use heap ($O(n \log k)$ time, $O(k)$ space).
Problem 10: Word Break
Problem: Determine if string can be segmented into words from dictionary.
Example:
1Input: s = "leetcode", wordDict = ["leet","code"]
2Output: true
Approach
Key Insight: Dynamic programming - can we break s[0:i]?
Recurrence: $dp[i] = \text{true if } \exists j < i: dp[j] \land s[j:i] \in dict$
Solution
1func wordBreak(s string, wordDict []string) bool {
2 wordSet := make(map[string]bool)
3 for _, word := range wordDict {
4 wordSet[word] = true
5 }
6
7 n := len(s)
8 dp := make([]bool, n+1)
9 dp[0] = true // Empty string
10
11 for i := 1; i <= n; i++ {
12 for j := 0; j < i; j++ {
13 if dp[j] && wordSet[s[j:i]] {
14 dp[i] = true
15 break
16 }
17 }
18 }
19
20 return dp[n]
21}
Time: $O(n^2 \times m)$ where m is max word length, Space: $O(n)$
Optimization: Check only valid word lengths instead of all j.
Common Patterns in Medium Problems
- Sliding Window: Longest substring, subarray problems
- Two Pointers: 3Sum, container with most water
- Hash Map: Group anagrams, subarray sum
- Dynamic Programming: Coin change, word break
- DFS/BFS: Islands, course schedule
- Binary Search: Search in rotated array
- Backtracking: Permutations, combinations
Problem-Solving Framework
- Identify pattern: Which category does this fit?
- Consider brute force: What's the naive solution?
- Optimize: Can we use hash map? Two pointers? DP?
- Edge cases: Empty input, single element, all same
- Test: Walk through example step-by-step
Time Complexity Goals
- $O(n)$: Single pass with hash map/set
- $O(n \log n)$: Sorting, heap operations
- $O(n^2)$: Nested loops (often optimizable)
- $O(2^n)$: Backtracking, subsets
Aim for better than brute force!
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 - Hard
Hard-level algorithm interview questions with detailed approach explanations and …