50 Most Common

Interview Coding Problems

Solutions in Python & Go | With Explanation & Approach

Table of Contents
Array & Hash Map: Problems 1, 4, 5, 23, 24, 29, 30, 35, 39, 40
String & Sliding Window: Problems 2, 7, 27, 28
Stack & Queue: Problems 3, 31, 32
Linked List: Problems 9, 10
Tree (DFS / BFS): Problems 11, 12, 13, 14, 33, 37
Dynamic Programming: Problems 8, 15, 16, 17, 18, 47, 49, 50
Graph & Backtracking: Problems 19, 20, 21, 22, 25, 26, 43, 45
Binary Search: Problems 6, 34, 41, 42, 48
Greedy & Heap: Problems 36, 44, 46
Design: Problems 31, 32, 38
 Problem 1: Two Sum
Category: Array / Hash Map Difficulty: Easy
Problem Description
Given an array of integers and a target sum, return the indices of the two numbers that add up to the
target. Each input has exactly one solution and you may not use the same element twice.
Example
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] # nums[0] + nums[1] = 9

Approach & Strategy

Use a hash map to store each number and its index. For each element, check if (target - element)
exists in the map. O(n) time, O(n) space.
Python Solution
def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []

Go Solution
func twoSum(nums []int, target int) []int {
seen := make(map[int]int)
for i, num := range nums {
complement := target - num
if j, ok := seen[complement]; ok {
return []int{j, i}
}
seen[num] = i
}
return nil
}

Problem 2: Reverse a String

Category: String Difficulty: Easy
Problem Description
Given a string, return it reversed. You may not use built-in reverse functions.
Example
Input: 'hello'
Output: 'olleh'

Approach & Strategy

Use two pointers from both ends, swapping characters inward. O(n) time, O(1) space.
Python Solution
def reverse_string(s):
chars = list(s)
left, right = 0, len(chars) - 1
while left < right:
chars[left], chars[right] = chars[right], chars[left]
left += 1
 right -= 1
return ''.join(chars)

Go Solution
func reverseString(s string) string {
chars := []rune(s)
left, right := 0, len(chars)-1
for left < right {
chars[left], chars[right] = chars[right], chars[left]
left++
right--
}
return string(chars)
}
 Problem 3: Valid Parentheses
Category: Stack Difficulty: Easy
Problem Description
Given a string containing '(', ')', '{', '}', '[', ']', determine if the input string is valid. Brackets must close in
the correct order.
Example
Input: '({[]})'
Output: True
Input: '([)]'
Output: False

Approach & Strategy

Use a stack. Push opening brackets; when a closing bracket appears, check if it matches the top of the
stack. If stack is empty at end, it's valid.
Python Solution
def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top = [Link]() if stack else '#'
if mapping[char] != top:
return False
else:
[Link](char)
return not stack

Go Solution
func isValid(s string) bool {
stack := []rune{}
mapping := map[rune]rune{')': '(', '}': '{', ']': '['}
for _, ch := range s {
if open, ok := mapping[ch]; ok {
if len(stack) == 0 || stack[len(stack)-1] != open {
return false
}
stack = stack[:len(stack)-1]
} else {
stack = append(stack, ch)
}
}
return len(stack) == 0
}

Problem 4: Merge Two Sorted Arrays

Category: Array / Two Pointers Difficulty: Easy
Problem Description
Given two sorted arrays, merge them into one sorted array without using built-in sort.
Example
Input: [1, 3, 5], [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]
Approach & Strategy
Use two pointers, one for each array. Compare elements and append the smaller one to result. O(n+m)
time.
Python Solution
def merge_sorted(a, b):
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
[Link](a[i]); i += 1
else:
[Link](b[j]); j += 1
[Link](a[i:])
[Link](b[j:])
return result

Go Solution
func mergeSorted(a, b []int) []int {
result := []int{}
i, j := 0, 0
for i < len(a) && j < len(b) {
if a[i] <= b[j] {
result = append(result, a[i]); i++
} else {
result = append(result, b[j]); j++
}
}
result = append(result, a[i:]...)
result = append(result, b[j:]...)
return result
}
 Problem 5: Find Maximum Subarray (Kadane's Algorithm)
Category: Array / Dynamic Programming Difficulty: Medium
Problem Description
Given an integer array, find the contiguous subarray with the largest sum and return that sum.
Example
Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6 # subarray [4, -1, 2, 1]

Approach & Strategy

Track current sum and global max. At each step, either extend current subarray or start fresh. O(n)
time, O(1) space.
Python Solution
def max_subarray(nums):
max_sum = current = nums[0]
for num in nums[1:]:
current = max(num, current + num)
max_sum = max(max_sum, current)
return max_sum

Go Solution
func maxSubarray(nums []int) int {
maxSum, current := nums[0], nums[0]
for _, num := range nums[1:] {
if num > current+num {
current = num
} else {
current += num
}
if current > maxSum {
maxSum = current
}
}
return maxSum
}

Problem 6: Binary Search

Category: Array / Search Difficulty: Easy
Problem Description
Given a sorted array and a target value, return the index of the target. If not found, return -1.
Example
Input: nums = [1, 3, 5, 7, 9], target = 5
Output: 2

Approach & Strategy

Maintain left and right pointers. Check the midpoint each time and halve the search space. O(log n)
time.
Python Solution
def binary_search(nums, target):
left, right = 0, len(nums) - 1
 while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

Go Solution
func binarySearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := (left + right) / 2
if nums[mid] == target {
return mid
} else if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
 Problem 7: Palindrome Check
Category: String / Two Pointers Difficulty: Easy
Problem Description
Given a string, determine if it is a palindrome (reads the same backward as forward), ignoring non-
alphanumeric characters and case.
Example
Input: 'A man, a plan, a canal: Panama'
Output: True

Approach & Strategy

Use two pointers from both ends, skip non-alphanumeric chars, compare chars case-insensitively.
Python Solution
def is_palindrome(s):
cleaned = ''.join([Link]() for c in s if [Link]())
return cleaned == cleaned[::-1]

Go Solution
import "unicode"

func isPalindrome(s string) bool {

runes := []rune{}
for _, ch := range s {
if [Link](ch) || [Link](ch) {
runes = append(runes, [Link](ch))
}
}
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
if runes[i] != runes[j] { return false }
}
return true
}

Problem 8: Fibonacci Number

Category: Recursion / DP Difficulty: Easy
Problem Description
Return the nth Fibonacci number where F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2).
Example
Input: n = 7
Output: 13

Approach & Strategy

Use iterative DP with two variables to avoid redundant recursion. O(n) time, O(1) space.
Python Solution
def fib(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
Go Solution
func fib(n int) int {
if n <= 1 { return n }
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}
 Problem 9: Reverse Linked List
Category: Linked List Difficulty: Easy
Problem Description
Given the head of a singly linked list, reverse the list and return the new head.
Example
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

Approach & Strategy

Use three pointers: prev, current, next. Iteratively reverse the next pointer. O(n) time.
Python Solution
class ListNode:
def __init__(self, val=0, next=None):
[Link] = val; [Link] = next

def reverse_list(head):
prev = None
current = head
while current:
next_node = [Link]
[Link] = prev
prev = current
current = next_node
return prev

Go Solution
type ListNode struct {
Val int
Next *ListNode
}

func reverseList(head *ListNode) *ListNode {

var prev *ListNode
curr := head
for curr != nil {
next := [Link]
[Link] = prev
prev = curr
curr = next
}
return prev
}

Problem 10: Detect Cycle in Linked List

Category: Linked List / Two Pointers Difficulty: Easy
Problem Description
Given a linked list, determine if it has a cycle using Floyd's Tortoise and Hare algorithm.
Example
Input: 3 -> 2 -> 0 -> -4 (tail connects to node at index 1)
Output: True

Approach & Strategy

Use slow and fast pointers. If they meet, there's a cycle. O(n) time, O(1) space.
Python Solution
def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow == fast:
return True
return False

Go Solution
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && [Link] != nil {
slow = [Link]
fast = [Link]
if slow == fast {
return true
}
}
return false
}
 Problem 11: Maximum Depth of Binary Tree
Category: Tree / DFS Difficulty: Easy
Problem Description
Given the root of a binary tree, return its maximum depth (number of nodes along the longest path from
root to leaf).
Example
Input: [3,9,20,null,null,15,7]
Output: 3

Approach & Strategy

Recursively compute depth: 1 + max(depth(left), depth(right)). Base case: null node = 0.
Python Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
[Link] = val; [Link] = left; [Link] = right

def max_depth(root):
if not root: return 0
return 1 + max(max_depth([Link]), max_depth([Link]))

Go Solution
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func maxDepth(root *TreeNode) int {

if root == nil { return 0 }
left := maxDepth([Link])
right := maxDepth([Link])
if left > right { return left + 1 }
return right + 1
}

Problem 12: Invert Binary Tree

Category: Tree / Recursion Difficulty: Easy
Problem Description
Invert a binary tree (mirror it left-to-right).
Example
Input: [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Approach & Strategy

Recursively swap left and right children for every node. O(n) time.
Python Solution
def invert_tree(root):
if not root: return None
[Link], [Link] = invert_tree([Link]), invert_tree([Link])
return root
Go Solution
func invertTree(root *TreeNode) *TreeNode {
if root == nil { return nil }
[Link], [Link] = invertTree([Link]), invertTree([Link])
return root
}
 Problem 13: Level Order Traversal (BFS)
Category: Tree / BFS Difficulty: Medium
Problem Description
Given the root of a binary tree, return the level order traversal of its nodes' values (left to right, level by
level).
Example
Input: [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Approach & Strategy

Use a queue. Process nodes level by level, tracking the count per level.
Python Solution
from collections import deque

def level_order(root):
if not root: return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return result

Go Solution
func levelOrder(root *TreeNode) [][]int {
if root == nil { return nil }
result := [][]int{}
queue := []*TreeNode{root}
for len(queue) > 0 {
level := []int{}
size := len(queue)
for i := 0; i < size; i++ {
node := queue[0]; queue = queue[1:]
level = append(level, [Link])
if [Link] != nil { queue = append(queue, [Link]) }
if [Link] != nil { queue = append(queue, [Link]) }
}
result = append(result, level)
}
return result
}

Problem 14: Validate Binary Search Tree

Category: Tree / DFS Difficulty: Medium
Problem Description
Given the root of a binary tree, determine if it is a valid BST. Left subtree values must be less than
node, right subtree values greater.
Example
Input: [2,1,3]
Output: True
Input: [5,1,4,null,null,3,6]
Output: False

Approach & Strategy

Pass min and max bounds recursively. Each node must be within (min, max). O(n) time.
Python Solution
def is_valid_bst(root, lo=float('-inf'), hi=float('inf')):
if not root: return True
if not (lo < [Link] < hi): return False
return (is_valid_bst([Link], lo, [Link]) and
is_valid_bst([Link], [Link], hi))

Go Solution
import "math"

func isValidBST(root *TreeNode) bool {

return validate(root, math.MinInt64, math.MaxInt64)
}

func validate(node *TreeNode, lo, hi int) bool {

if node == nil { return true }
if [Link] <= lo || [Link] >= hi { return false }
return validate([Link], lo, [Link]) && validate([Link], [Link], hi)
}
 Problem 15: Climbing Stairs
Category: Dynamic Programming Difficulty: Easy
Problem Description
You can climb 1 or 2 steps at a time. Given n steps, in how many distinct ways can you climb to the
top?
Example
Input: n = 4
Output: 5 # (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)

Approach & Strategy

This is Fibonacci! ways(n) = ways(n-1) + ways(n-2). Use iterative DP.
Python Solution
def climb_stairs(n):
if n <= 2: return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b

Go Solution
func climbStairs(n int) int {
if n <= 2 { return n }
a, b := 1, 2
for i := 3; i <= n; i++ {
a, b = b, a+b
}
return b
}

Problem 16: Coin Change

Category: Dynamic Programming Difficulty: Medium
Problem Description
Given coin denominations and a target amount, return the fewest number of coins needed to make up
that amount. Return -1 if impossible.
Example
Input: coins = [1, 5, 6, 9], amount = 11
Output: 2 # (5+6)

Approach & Strategy

Bottom-up DP: dp[i] = min coins to make amount i. dp[0]=0, for each amount try all coins.
Python Solution
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

Go Solution
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := range dp { dp[i] = amount + 1 }
dp[0] = 0
for _, coin := range coins {
for i := coin; i <= amount; i++ {
if dp[i-coin]+1 < dp[i] { dp[i] = dp[i-coin] + 1 }
}
}
if dp[amount] > amount { return -1 }
return dp[amount]
}
 Problem 17: Longest Common Subsequence
Category: Dynamic Programming Difficulty: Medium
Problem Description
Given two strings, find the length of their longest common subsequence (LCS). Characters don't have
to be contiguous.
Example
Input: 'abcde', 'ace'
Output: 3 # 'ace'

Approach & Strategy

2D DP table: if chars match, dp[i][j] = 1 + dp[i-1][j-1]; else max(dp[i-1][j], dp[i][j-1]).
Python Solution
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]

Go Solution
func longestCommonSubsequence(t1, t2 string) int {
m, n := len(t1), len(t2)
dp := make([][]int, m+1)
for i := range dp { dp[i] = make([]int, n+1) }
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if t1[i-1] == t2[j-1] {
dp[i][j] = 1 + dp[i-1][j-1]
} else if dp[i-1][j] > dp[i][j-1] {
dp[i][j] = dp[i-1][j]
} else {
dp[i][j] = dp[i][j-1]
}
}
}
return dp[m][n]
}

Problem 18: House Robber

Category: Dynamic Programming Difficulty: Medium
Problem Description
You are a robber. You cannot rob two adjacent houses. Given amounts in each house, find the
maximum you can rob.
Example
Input: [2, 7, 9, 3, 1]
Output: 12 # (2 + 9 + 1)
Approach & Strategy
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Only keep last two values.
Python Solution
def rob(nums):
prev2 = prev1 = 0
for num in nums:
prev2, prev1 = prev1, max(prev1, prev2 + num)
return prev1

Go Solution
func rob(nums []int) int {
prev2, prev1 := 0, 0
for _, num := range nums {
prev2, prev1 = prev1, max(prev1, prev2+num)
}
return prev1
}

func max(a, b int) int {

if a > b { return a }
return b
}
 Problem 19: Number of Islands
Category: Graph / BFS / DFS Difficulty: Medium
Problem Description
Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by
water and formed by connecting adjacent lands.
Example
Input: grid = [['1','1','0'],['0','1','0'],['0','0','1']]
Output: 2

Approach & Strategy

DFS from each unvisited '1'. Mark visited cells as '0'. Count DFS calls.
Python Solution
def num_islands(grid):
count = 0
def dfs(r, c):
if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
return
if grid[r][c] != '1': return
grid[r][c] = '0'
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == '1':
count += 1; dfs(r, c)
return count

Go Solution
func numIslands(grid [][]byte) int {
count := 0
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || r >= len(grid) || c < 0 || c >= len(grid[0]) { return }
if grid[r][c] != '1' { return }
grid[r][c] = '0'
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
}
for r := range grid {
for c := range grid[r] {
if grid[r][c] == '1' { count++; dfs(r, c) }
}
}
return count
}

Problem 20: Clone Graph

Category: Graph / BFS Difficulty: Medium
Problem Description
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Example
Input: Graph with node 1 connected to 2 and 4
Output: Deep copy of same structure
Approach & Strategy
Use BFS/DFS with a hashmap mapping original nodes to their clones.
Python Solution
class Node:
def __init__(self, val, neighbors=None):
[Link] = val
[Link] = neighbors or []

def clone_graph(node):
if not node: return None
visited = {}
def dfs(n):
if n in visited: return visited[n]
clone = Node([Link])
visited[n] = clone
for neighbor in [Link]:
[Link](dfs(neighbor))
return clone
return dfs(node)

Go Solution
type GraphNode struct {
Val int
Neighbors []*GraphNode
}

func cloneGraph(node *GraphNode) *GraphNode {

if node == nil { return nil }
visited := map[*GraphNode]*GraphNode{}
var dfs func(*GraphNode) *GraphNode
dfs = func(n *GraphNode) *GraphNode {
if clone, ok := visited[n]; ok { return clone }
clone := &GraphNode{Val: [Link]}
visited[n] = clone
for _, nb := range [Link] {
[Link] = append([Link], dfs(nb))
}
return clone
}
return dfs(node)
}
 Problem 21: Course Schedule (Topological Sort)
Category: Graph / DAG Difficulty: Medium
Problem Description
There are n courses and prerequisites. Determine if it's possible to finish all courses (detect cycle in
directed graph).
Example
Input: n=2, prerequisites=[[1,0]]
Output: True # Take 0 then 1

Approach & Strategy

Build adjacency list, use DFS to detect cycles using states: unvisited(0), visiting(1), done(2).
Python Solution
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
for a, b in prerequisites:
graph[b].append(a)
state = [0] * num_courses # 0=unvisited, 1=visiting, 2=done
def dfs(node):
if state[node] == 1: return False # cycle
if state[node] == 2: return True
state[node] = 1
for neighbor in graph[node]:
if not dfs(neighbor): return False
state[node] = 2
return True
return all(dfs(i) for i in range(num_courses))

Go Solution
func canFinish(numCourses int, prerequisites [][]int) bool {
graph := make([][]int, numCourses)
for _, p := range prerequisites { graph[p[1]] = append(graph[p[1]], p[0]) }
state := make([]int, numCourses)
var dfs func(int) bool
dfs = func(node int) bool {
if state[node] == 1 { return false }
if state[node] == 2 { return true }
state[node] = 1
for _, nb := range graph[node] {
if !dfs(nb) { return false }
}
state[node] = 2
return true
}
for i := 0; i < numCourses; i++ {
if !dfs(i) { return false }
}
return true
}

Problem 22: Word Search

Category: Backtracking / DFS Difficulty: Medium
Problem Description
Given a 2D board and a word, find if the word exists using adjacent cells (horizontal/vertical). Each cell
may be used only once.
Example
Input: board=[['A','B','C'],['S','F','C'],['A','D','E']], word='ABCCED'
Output: True

Approach & Strategy

DFS backtracking from every cell. Mark visited, explore 4 directions, unmark on backtrack.
Python Solution
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, idx):
if idx == len(word): return True
if r<0 or r>=rows or c<0 or c>=cols: return False
if board[r][c] != word[idx]: return False
tmp, board[r][c] = board[r][c], '#'
found = any(dfs(r+dr, c+dc, idx+1) for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)])
board[r][c] = tmp
return found
return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))

Go Solution
func exist(board [][]byte, word string) bool {
rows, cols := len(board), len(board[0])
var dfs func(r, c, idx int) bool
dfs = func(r, c, idx int) bool {
if idx == len(word) { return true }
if r<0||r>=rows||c<0||c>=cols||board[r][c] != word[idx] { return false }
tmp := board[r][c]; board[r][c] = '#'
dirs := [][2]int{{1,0},{-1,0},{0,1},{0,-1}}
for _, d := range dirs {
if dfs(r+d[0], c+d[1], idx+1) { board[r][c] = tmp; return true }
}
board[r][c] = tmp; return false
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if dfs(r, c, 0) { return true }
}
}
return false
}
 Problem 23: Merge Intervals
Category: Array / Sorting Difficulty: Medium
Problem Description
Given an array of intervals, merge all overlapping intervals and return the non-overlapping result.
Example
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Approach & Strategy

Sort by start time. Merge current with previous if overlap exists.
Python Solution
def merge(intervals):
[Link](key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
[Link]([start, end])
return merged

Go Solution
import "sort"

func merge(intervals [][]int) [][]int {

[Link](intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
merged := [][]int{intervals[0]}
for _, iv := range intervals[1:] {
last := merged[len(merged)-1]
if iv[0] <= last[1] {
if iv[1] > last[1] { last[1] = iv[1] }
} else {
merged = append(merged, iv)
}
}
return merged
}

Problem 24: Product of Array Except Self

Category: Array Difficulty: Medium
Problem Description
Given an integer array, return an array where each element is the product of all other elements. No
division allowed, O(n) time.
Example
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Approach & Strategy

Use prefix and suffix product arrays. result[i] = prefix[i] * suffix[i].
Python Solution
def product_except_self(nums):
n = len(nums)
result = [1] * n
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result

Go Solution
func productExceptSelf(nums []int) []int {
n := len(nums)
result := make([]int, n)
prefix := 1
for i := 0; i < n; i++ {
result[i] = prefix
prefix *= nums[i]
}
suffix := 1
for i := n - 1; i >= 0; i-- {
result[i] *= suffix
suffix *= nums[i]
}
return result
}
 Problem 25: Find All Permutations
Category: Backtracking Difficulty: Medium
Problem Description
Given a distinct integer array, return all possible permutations.
Example
Input: [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Approach & Strategy

Backtracking: swap current element with each subsequent element, recurse, then swap back.
Python Solution
def permute(nums):
result = []
def backtrack(start):
if start == len(nums):
[Link](nums[:])
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
backtrack(0)
return result

Go Solution
func permute(nums []int) [][]int {
result := [][]int{}
var backtrack func(start int)
backtrack = func(start int) {
if start == len(nums) {
tmp := make([]int, len(nums))
copy(tmp, nums)
result = append(result, tmp)
return
}
for i := start; i < len(nums); i++ {
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
}
}
backtrack(0)
return result
}

Problem 26: Subsets (Power Set)

Category: Backtracking Difficulty: Medium
Problem Description
Given an integer array of unique elements, return all possible subsets (the power set).
Example
 Input: [1, 2, 3]
Output: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Approach & Strategy

Backtracking: at each index, choose to include or exclude the element.
Python Solution
def subsets(nums):
result = []
def backtrack(start, current):
[Link](current[:])
for i in range(start, len(nums)):
[Link](nums[i])
backtrack(i + 1, current)
[Link]()
backtrack(0, [])
return result

Go Solution
func subsets(nums []int) [][]int {
result := [][]int{}
var backtrack func(start int, curr []int)
backtrack = func(start int, curr []int) {
tmp := make([]int, len(curr))
copy(tmp, curr)
result = append(result, tmp)
for i := start; i < len(nums); i++ {
curr = append(curr, nums[i])
backtrack(i+1, curr)
curr = curr[:len(curr)-1]
}
}
backtrack(0, []int{})
return result
}
 Problem 27: Longest Palindromic Substring
Category: String / DP Difficulty: Medium
Problem Description
Given a string, return the longest palindromic substring.
Example
Input: 'babad'
Output: 'bab' or 'aba'

Approach & Strategy

Expand around center for each character (and gap between characters). O(n^2) time.
Python Solution
def longest_palindrome(s):
res = ''
def expand(l, r):
nonlocal res
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1; r += 1
for i in range(len(s)):
expand(i, i) # odd length
expand(i, i+1) # even length
return res

Go Solution
func longestPalindrome(s string) string {
res := ""
expand := func(l, r int) {
for l >= 0 && r < len(s) && s[l] == s[r] {
if r-l+1 > len(res) { res = s[l : r+1] }
l--; r++
}
}
for i := range s {
expand(i, i)
expand(i, i+1)
}
return res
}

Problem 28: Longest Substring Without Repeating Characters

Category: String / Sliding Window Difficulty: Medium
Problem Description
Given a string, find the length of the longest substring without repeating characters.
Example
Input: 'abcabcbb'
Output: 3 # 'abc'

Approach & Strategy

Sliding window with a set. Expand right, shrink left when duplicate found.
Python Solution
def length_of_longest_substring(s):
char_set = set()
left = max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len

Go Solution
func lengthOfLongestSubstring(s string) int {
charSet := map[byte]bool{}
left, maxLen := 0, 0
for right := 0; right < len(s); right++ {
for charSet[s[right]] {
delete(charSet, s[left]); left++
}
charSet[s[right]] = true
if right-left+1 > maxLen { maxLen = right - left + 1 }
}
return maxLen
}
 Problem 29: 3Sum
Category: Array / Two Pointers Difficulty: Medium
Problem Description
Given an integer array, find all unique triplets that sum to zero.
Example
Input: [-1, 0, 1, 2, -1, -4]
Output: [[-1,-1,2],[-1,0,1]]

Approach & Strategy

Sort array. Fix one element, use two pointers for the rest. Skip duplicates carefully.
Python Solution
def three_sum(nums):
[Link]()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
[Link]([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif total < 0: left += 1
else: right -= 1
return result

Go Solution
func threeSum(nums []int) [][]int {
[Link](nums)
result := [][]int{}
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] { continue }
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
result = append(result, []int{nums[i], nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] { left++ }
for left < right && nums[right] == nums[right-1] { right-- }
left++; right--
} else if sum < 0 { left++ } else { right-- }
}
}
return result
}

Problem 30: Trapping Rain Water

Category: Array / Two Pointers Difficulty: Hard
Problem Description
Given an elevation map (array of heights), compute how much water it can trap after raining.
Example
Input: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6

Approach & Strategy

Two pointers. Water at position i = min(maxLeft, maxRight) - height[i]. Move the shorter side inward.
Python Solution
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left: max_left = height[left]
else: water += max_left - height[left]
left += 1
else:
if height[right] >= max_right: max_right = height[right]
else: water += max_right - height[right]
right -= 1
return water

Go Solution
func trap(height []int) int {
left, right := 0, len(height)-1
maxLeft, maxRight, water := 0, 0, 0
for left < right {
if height[left] < height[right] {
if height[left] >= maxLeft { maxLeft = height[left] } else { water += maxLeft
- height[left] }
left++
} else {
if height[right] >= maxRight { maxRight = height[right] } else { water +=
maxRight - height[right] }
right--
}
}
return water
}
 Problem 31: Implement Queue Using Stacks
Category: Stack / Design Difficulty: Easy
Problem Description
Implement a queue using only two stacks. Support push, pop, peek, and empty operations.
Example
push(1), push(2), peek() -> 1, pop() -> 1, empty() -> False

Approach & Strategy

Two stacks: inbox and outbox. Push to inbox; pop/peek from outbox (refill from inbox when empty).
Python Solution
class MyQueue:
def __init__(self):
[Link] = []
[Link] = []
def push(self, x):
[Link](x)
def _transfer(self):
if not [Link]:
while [Link]:
[Link]([Link]())
def pop(self):
self._transfer(); return [Link]()
def peek(self):
self._transfer(); return [Link][-1]
def empty(self):
return not [Link] and not [Link]

Go Solution
type MyQueue struct { inbox, outbox []int }

func (q *MyQueue) Push(x int) { [Link] = append([Link], x) }

func (q *MyQueue) transfer() {

if len([Link]) == 0 {
for len([Link]) > 0 {
n := len([Link])
[Link] = append([Link], [Link][n-1])
[Link] = [Link][:n-1]
}
}
}

func (q *MyQueue) Pop() int {

[Link](); n := len([Link]); v := [Link][n-1]; [Link] = [Link][:n-1];
return v
}

func (q *MyQueue) Peek() int { [Link](); return [Link][len([Link])-1] }

func (q *MyQueue) Empty() bool { return len([Link]) == 0 && len([Link]) == 0 }

Problem 32: Min Stack

Category: Stack / Design Difficulty: Easy
Problem Description
Design a stack that supports push, pop, top, and retrieving the minimum element in O(1) time.
Example
push(-2), push(0), push(-3), getMin()->-3, pop(), top()->0, getMin()->-2

Approach & Strategy

Maintain a secondary stack that tracks the minimum at each level.
Python Solution
class MinStack:
def __init__(self):
[Link] = []
self.min_stack = []
def push(self, val):
[Link](val)
mn = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(mn)
def pop(self):
[Link](); self.min_stack.pop()
def top(self): return [Link][-1]
def get_min(self): return self.min_stack[-1]

Go Solution
type MinStack struct { stack, minStack []int }

func (s *MinStack) Push(val int) {

[Link] = append([Link], val)
mn := val
if len([Link]) > 0 && [Link][len([Link])-1] < val {
mn = [Link][len([Link])-1]
}
[Link] = append([Link], mn)
}

func (s *MinStack) Pop() {

[Link] = [Link][:len([Link])-1]
[Link] = [Link][:len([Link])-1]
}

func (s *MinStack) Top() int { return [Link][len([Link])-1] }

func (s *MinStack) GetMin() int { return [Link][len([Link])-1] }
 Problem 33: Diameter of Binary Tree
Category: Tree / DFS Difficulty: Easy
Problem Description
Given the root of a binary tree, return the length of the diameter (longest path between any two nodes,
which may or may not pass through root).
Example
Input: [1,2,3,4,5]
Output: 3 # path [4,2,1,3] or [5,2,1,3]

Approach & Strategy

DFS returning height; at each node update max diameter = left_height + right_height.
Python Solution
def diameter_of_binary_tree(root):
max_d = [0]
def dfs(node):
if not node: return 0
left = dfs([Link])
right = dfs([Link])
max_d[0] = max(max_d[0], left + right)
return 1 + max(left, right)
dfs(root)
return max_d[0]

Go Solution
func diameterOfBinaryTree(root *TreeNode) int {
maxD := 0
var dfs func(*TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil { return 0 }
left := dfs([Link])
right := dfs([Link])
if left+right > maxD { maxD = left + right }
if left > right { return left + 1 }
return right + 1
}
dfs(root)
return maxD
}

Problem 34: Search in Rotated Sorted Array

Category: Binary Search Difficulty: Medium
Problem Description
Given a rotated sorted array (no duplicates) and a target, return the index or -1.
Example
Input: nums=[4,5,6,7,0,1,2], target=0
Output: 4

Approach & Strategy

Modified binary search: check which half is sorted, then decide which half to search.
Python Solution
 def search_rotated(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target: return mid
if nums[left] <= nums[mid]: # left half sorted
if nums[left] <= target < nums[mid]: right = mid - 1
else: left = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[right]: left = mid + 1
else: right = mid - 1
return -1

Go Solution
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := (left + right) / 2
if nums[mid] == target { return mid }
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] { right = mid - 1 } else { left
= mid + 1 }
} else {
if nums[mid] < target && target <= nums[right] { left = mid + 1 } else { right
= mid - 1 }
}
}
return -1
}
 Problem 35: Top K Frequent Elements
Category: Hash Map / Heap Difficulty: Medium
Problem Description
Given an integer array, return the k most frequent elements.
Example
Input: nums=[1,1,1,2,2,3], k=2
Output: [1, 2]

Approach & Strategy

Count frequencies with hash map, use bucket sort (index = frequency) for O(n) solution.
Python Solution
from collections import Counter

def top_k_frequent(nums, k):

count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in [Link]():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, 0, -1):
[Link](buckets[i])
if len(result) >= k: break
return result[:k]

Go Solution
func topKFrequent(nums []int, k int) []int {
count := map[int]int{}
for _, n := range nums { count[n]++ }
buckets := make([][]int, len(nums)+1)
for num, freq := range count { buckets[freq] = append(buckets[freq], num) }
result := []int{}
for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
result = append(result, buckets[i]...)
}
return result[:k]
}

Problem 36: Kth Largest Element

Category: Heap / Quickselect Difficulty: Medium
Problem Description
Find the kth largest element in an unsorted array.
Example
Input: nums=[3,2,1,5,6,4], k=2
Output: 5

Approach & Strategy

Use a min-heap of size k. After all elements, heap top is the kth largest. O(n log k).
Python Solution
import heapq
 def find_kth_largest(nums, k):
heap = []
for num in nums:
[Link](heap, num)
if len(heap) > k:
[Link](heap)
return heap[0]

Go Solution
import "container/heap"

type MinHeap []int

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} { old := *h; n := len(old); x := old[n-1]; *h =
old[:n-1]; return x }

func findKthLargest(nums []int, k int) int {

h := &MinHeap{}
for _, n := range nums {
[Link](h, n)
if [Link]() > k { [Link](h) }
}
return (*h)[0]
}
 Problem 37: Serialize and Deserialize Binary Tree
Category: Tree / BFS Difficulty: Hard
Problem Description
Design an algorithm to serialize a binary tree to a string and deserialize it back.
Example
Tree [1,2,3,null,null,4,5] -> '1,2,3,null,null,4,5' -> original tree

Approach & Strategy

BFS level-order traversal for serialize. Use a queue and index for deserialize.
Python Solution
from collections import deque

def serialize(root):
if not root: return 'null'
result, queue = [], deque([root])
while queue:
node = [Link]()
if node:
[Link](str([Link]))
[Link]([[Link], [Link]])
else:
[Link]('null')
return ','.join(result)

def deserialize(data):
vals = [Link](',')
if vals[0] == 'null': return None
root = TreeNode(int(vals[0]))
queue, i = deque([root]), 1
while queue and i < len(vals):
node = [Link]()
if vals[i] != 'null':
[Link] = TreeNode(int(vals[i])); [Link]([Link])
i += 1
if i < len(vals) and vals[i] != 'null':
[Link] = TreeNode(int(vals[i])); [Link]([Link])
i += 1
return root

Go Solution
import "strings"; import "strconv"

func serialize(root *TreeNode) string {

if root == nil { return "null" }
res := []string{}
queue := []*TreeNode{root}
for len(queue) > 0 {
node := queue[0]; queue = queue[1:]
if node == nil { res = append(res, "null") } else {
res = append(res, [Link]([Link]))
queue = append(queue, [Link], [Link])
}
}
return [Link](res, ",")
}
 Problem 38: LRU Cache
Category: Design / Hash Map Difficulty: Medium
Problem Description
Design a data structure that follows the Least Recently Used (LRU) cache. Implement get and put in
O(1) time.
Example
LRU(2): put(1,1), put(2,2), get(1)->1, put(3,3) [evicts 2], get(2)->-1

Approach & Strategy

Combine a hash map with a doubly linked list. Map gives O(1) access; linked list tracks usage order.
Python Solution
from collections import OrderedDict

class LRUCache:
def __init__(self, capacity):
[Link] = capacity
[Link] = OrderedDict()
def get(self, key):
if key not in [Link]: return -1
[Link].move_to_end(key)
return [Link][key]
def put(self, key, value):
if key in [Link]: [Link].move_to_end(key)
[Link][key] = value
if len([Link]) > [Link]:
[Link](last=False)

Go Solution
type LRUCache struct {
cap int
cache map[int]*Node
head, tail *Node
}

type Node struct { key, val int; prev, next *Node }

// Full implementation uses doubly-linked list + hashmap

// get: O(1) - look up in map, move to front
// put: O(1) - insert at front, evict tail if over capacity
 Problem 39: Spiral Matrix
Category: Array / Simulation Difficulty: Medium
Problem Description
Given an m x n matrix, return all elements in spiral order.
Example
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Approach & Strategy

Maintain four boundaries (top, bottom, left, right). Traverse each boundary and shrink.
Python Solution
def spiral_order(matrix):
result = []
top, bottom, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
while top <= bottom and left <= right:
for c in range(left, right+1): [Link](matrix[top][c])
top += 1
for r in range(top, bottom+1): [Link](matrix[r][right])
right -= 1
if top <= bottom:
for c in range(right, left-1, -1): [Link](matrix[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top-1, -1): [Link](matrix[r][left])
left += 1
return result

Go Solution
func spiralOrder(matrix [][]int) []int {
result := []int{}
top, bottom, left, right := 0, len(matrix)-1, 0, len(matrix[0])-1
for top <= bottom && left <= right {
for c := left; c <= right; c++ { result = append(result, matrix[top][c]) }
top++
for r := top; r <= bottom; r++ { result = append(result, matrix[r][right]) }
right--
if top <= bottom { for c := right; c >= left; c-- { result = append(result,
matrix[bottom][c]) }; bottom-- }
if left <= right { for r := bottom; r >= top; r-- { result = append(result,
matrix[r][left]) }; left++ }
}
return result
}

Problem 40: Rotate Image (Matrix 90 degrees)

Category: Array / Math Difficulty: Medium
Problem Description
Given an n x n matrix, rotate it 90 degrees clockwise in-place.
Example
Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Approach & Strategy
Transpose the matrix (swap rows and columns), then reverse each row.
Python Solution
def rotate(matrix):
n = len(matrix)
# Transpose
for i in range(n):
for j in range(i+1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# Reverse each row
for row in matrix:
[Link]()

Go Solution
func rotate(matrix [][]int) {
n := len(matrix)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
for _, row := range matrix {
for l, r := 0, len(row)-1; l < r; l, r = l+1, r-1 {
row[l], row[r] = row[r], row[l]
}
}
}
 Problem 41: Find Peak Element
Category: Binary Search Difficulty: Medium
Problem Description
A peak element is greater than its neighbors. Given an array, return the index of any peak element in
O(log n).
Example
Input: nums=[1,2,3,1]
Output: 2 # nums[2]=3 is a peak

Approach & Strategy

Binary search: if nums[mid] < nums[mid+1], peak is to the right; else to the left.
Python Solution
def find_peak_element(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left

Go Solution
func findPeakElement(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := (left + right) / 2
if nums[mid] < nums[mid+1] {
left = mid + 1
} else {
right = mid
}
}
return left
}

Problem 42: Find Minimum in Rotated Sorted Array

Category: Binary Search Difficulty: Medium
Problem Description
Given a rotated sorted array with unique values, find the minimum element in O(log n).
Example
Input: [3,4,5,1,2]
Output: 1

Approach & Strategy

Binary search: if nums[mid] > nums[right], min is in the right half; otherwise left half.
Python Solution
def find_min(nums):
left, right = 0, len(nums) - 1
while left < right:
 mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]

Go Solution
func findMin(nums []int) int {
left, right := 0, len(nums)-1
for left < right {
mid := (left + right) / 2
if nums[mid] > nums[right] {
left = mid + 1
} else {
right = mid
}
}
return nums[left]
}
 Problem 43: Word Ladder (BFS Shortest Path)
Category: Graph / BFS Difficulty: Hard
Problem Description
Given beginWord, endWord, and a word list, find the length of the shortest transformation sequence
where each step changes one letter and the result is in the word list.
Example
Input: beginWord='hit', endWord='cog', wordList=['hot','dot','dog','lot','log','cog']
Output: 5 # hit->hot->dot->dog->cog

Approach & Strategy

BFS from beginWord. At each step, try all 1-letter variations. Track visited words.
Python Solution
from collections import deque

def ladder_length(beginWord, endWord, wordList):

wordSet = set(wordList)
queue = deque([(beginWord, 1)])
while queue:
word, length = [Link]()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == endWord: return length + 1
if new_word in wordSet:
[Link](new_word)
[Link]((new_word, length + 1))
return 0

Go Solution
func ladderLength(beginWord, endWord string, wordList []string) int {
wordSet := map[string]bool{}
for _, w := range wordList { wordSet[w] = true }
queue := [][]interface{}{{beginWord, 1}}
for len(queue) > 0 {
item := queue[0]; queue = queue[1:]
word, length := item[0].(string), item[1].(int)
for i := 0; i < len(word); i++ {
for c := 'a'; c <= 'z'; c++ {
nw := word[:i] + string(c) + word[i+1:]
if nw == endWord { return length + 1 }
if wordSet[nw] { delete(wordSet, nw); queue = append(queue, []interface{}
{nw, length + 1}) }
}
}
}
return 0
}

Problem 44: Meeting Rooms II (Min Meeting Rooms)

Category: Greedy / Heap Difficulty: Medium
Problem Description
Given a list of meeting time intervals, find the minimum number of meeting rooms required.
Example
Input: [[0,30],[5,10],[15,20]]
Output: 2

Approach & Strategy

Sort by start time. Use a min-heap of end times. If earliest end <= current start, reuse the room.
Python Solution
import heapq

def min_meeting_rooms(intervals):
[Link](key=lambda x: x[0])
heap = [] # end times
for start, end in intervals:
if heap and heap[0] <= start:
[Link](heap)
[Link](heap, end)
return len(heap)

Go Solution
import "sort"; import "container/heap"

type IntHeap []int

func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} { old := *h; n := len(old); x := old[n-1]; *h =
old[:n-1]; return x }

func minMeetingRooms(intervals [][]int) int {

[Link](intervals, func(i, j int) bool { return intervals[i][0] < intervals[j]
[0] })
h := &IntHeap{}
for _, iv := range intervals {
if [Link]() > 0 && (*h)[0] <= iv[0] { [Link](h) }
[Link](h, iv[1])
}
return [Link]()
}
 Problem 45: Alien Dictionary (Topological Sort)
Category: Graph / Topology Difficulty: Hard
Problem Description
Given a sorted list of words in an alien language, derive the order of characters in that alphabet.
Example
Input: ['wrt','wrf','er','ett','rftt']
Output: 'wertf'

Approach & Strategy

Compare adjacent words to build a directed edge graph, then topological sort (DFS or BFS/Kahn's).
Python Solution
from collections import defaultdict, deque

def alien_order(words):
adj = defaultdict(set)
in_degree = {c: 0 for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]: return ''
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in adj[w1[j]]:
adj[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
queue = deque([c for c in in_degree if in_degree[c] == 0])
result = []
while queue:
c = [Link](); [Link](c)
for neighbor in adj[c]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0: [Link](neighbor)
return ''.join(result) if len(result) == len(in_degree) else ''

Go Solution
// Build edge graph from adjacent word comparisons
// Run Kahn's algorithm (BFS topological sort)
// Return empty string if cycle detected (invalid input)

Problem 46: Jump Game

Category: Greedy Difficulty: Medium
Problem Description
Given an array of non-negative integers where each element is the max jump length, determine if you
can reach the last index.
Example
Input: [2, 3, 1, 1, 4]
Output: True
Input: [3, 2, 1, 0, 4]
Output: False
Approach & Strategy
Track the farthest reachable index. If current index > farthest, return False.
Python Solution
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest: return False
farthest = max(farthest, i + jump)
return True

Go Solution
func canJump(nums []int) bool {
farthest := 0
for i, jump := range nums {
if i > farthest { return false }
if i+jump > farthest { farthest = i + jump }
}
return true
}
 Problem 47: Decode Ways
Category: Dynamic Programming Difficulty: Medium
Problem Description
A message is encoded as 'A'=1, 'B'=2, ..., 'Z'=26. Given a digit string, count the number of ways to
decode it.
Example
Input: '226'
Output: 3 # 2-2-6, 22-6, 2-26

Approach & Strategy

DP: dp[i] = ways to decode s[:i]. Single digit valid if !=0; two-digit valid if 10-26.
Python Solution
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1]
if 10 <= two <= 26: dp[i] += dp[i-2]
return dp[n]

Go Solution
func numDecodings(s string) int {
n := len(s)
if n == 0 || s[0] == '0' { return 0 }
dp := make([]int, n+1)
dp[0], dp[1] = 1, 1
for i := 2; i <= n; i++ {
one := s[i-1] - '0'
two := (s[i-2]-'0')*10 + (s[i-1] - '0')
if one != 0 { dp[i] += dp[i-1] }
if two >= 10 && two <= 26 { dp[i] += dp[i-2] }
}
return dp[n]
}

Problem 48: Median of Two Sorted Arrays

Category: Binary Search Difficulty: Hard
Problem Description
Given two sorted arrays, find the median of the combined array in O(log(m+n)) time.
Example
Input: nums1=[1,3], nums2=[2]
Output: 2.0
Input: nums1=[1,2], nums2=[3,4]
Output: 2.5

Approach & Strategy

Binary search on the smaller array. Find a partition where left side max <= right side min.
Python Solution
def find_median_sorted_arrays(nums1, nums2):
A, B = nums1, nums2
if len(A) > len(B): A, B = B, A
m, n = len(A), len(B)
lo, hi = 0, m
while lo <= hi:
partA = (lo + hi) // 2
partB = (m + n + 1) // 2 - partA
maxA = A[partA-1] if partA > 0 else float('-inf')
minA = A[partA] if partA < m else float('inf')
maxB = B[partB-1] if partB > 0 else float('-inf')
minB = B[partB] if partB < n else float('inf')
if maxA <= minB and maxB <= minA:
if (m + n) % 2 == 1: return max(maxA, maxB)
return (max(maxA, maxB) + min(minA, minB)) / 2.0
elif maxA > minB: hi = partA - 1
else: lo = partA + 1

Go Solution
import "math"

func findMedianSortedArrays(nums1, nums2 []int) float64 {

A, B := nums1, nums2
if len(A) > len(B) { A, B = B, A }
m, n := len(A), len(B)
lo, hi := 0, m
for lo <= hi {
partA := (lo + hi) / 2
partB := (m+n+1)/2 - partA
maxA, minA := math.MinInt64, math.MaxInt64
if partA > 0 { maxA = A[partA-1] }
if partA < m { minA = A[partA] }
maxB, minB := math.MinInt64, math.MaxInt64
if partB > 0 { maxB = B[partB-1] }
if partB < n { minB = B[partB] }
if maxA <= minB && maxB <= minA {
if (m+n)%2 == 1 { return float64(max2(maxA, maxB)) }
return float64(max2(maxA, maxB)+min2(minA, minB)) / 2.0
} else if maxA > minB { hi = partA - 1 } else { lo = partA + 1 }
}
return 0
}
 Problem 49: Regular Expression Matching
Category: Dynamic Programming Difficulty: Hard
Problem Description
Implement regular expression matching with '.' (any single char) and '*' (zero or more of preceding
element).
Example
Input: s='aab', p='c*a*b'
Output: True

Approach & Strategy

2D DP: dp[i][j] = True if s[:i] matches p[:j]. Handle '.' and '*' cases carefully.
Python Solution
def is_match(s, p):
m, n = len(s), len(p)
dp = [[False]*(n+1) for _ in range(m+1)]
dp[0][0] = True
for j in range(1, n+1):
if p[j-1] == '*': dp[0][j] = dp[0][j-2]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == '*':
dp[i][j] = dp[i][j-2] # use 0 times
if p[j-2] == '.' or p[j-2] == s[i-1]:
dp[i][j] |= dp[i-1][j] # use 1+ times
elif p[j-1] == '.' or p[j-1] == s[i-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]

Go Solution
func isMatch(s, p string) bool {
m, n := len(s), len(p)
dp := make([][]bool, m+1)
for i := range dp { dp[i] = make([]bool, n+1) }
dp[0][0] = true
for j := 1; j <= n; j++ {
if p[j-1] == '*' { dp[0][j] = dp[0][j-2] }
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
dp[i][j] = dp[i][j-2]
if p[j-2] == '.' || p[j-2] == s[i-1] { dp[i][j] = dp[i][j] || dp[i-1][j] }
} else if p[j-1] == '.' || p[j-1] == s[i-1] {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[m][n]
}

Problem 50: Unique Paths

Category: Dynamic Programming Difficulty: Medium
Problem Description
A robot is on an m x n grid. It can only move right or down. Count unique paths from top-left to bottom-
right.
Example
Input: m=3, n=7
Output: 28

Approach & Strategy

dp[i][j] = dp[i-1][j] + dp[i][j-1]. First row and column are all 1. O(m*n) time, can optimize to O(n).
Python Solution
def unique_paths(m, n):
dp = [1] * n
for _ in range(1, m):
for j in range(1, n):
dp[j] += dp[j-1]
return dp[-1]

Go Solution
func uniquePaths(m, n int) int {
dp := make([]int, n)
for j := range dp { dp[j] = 1 }
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] += dp[j-1]
}
}
return dp[n-1]
}
Quick Reference: Complexity Cheatsheet
Below is a summary of time and space complexity for all 50 problems:

Problem Time Space

Two Sum O(n) O(n)
Reverse String O(n) O(n)
Valid Parentheses O(n) O(n)
Merge Sorted Arrays O(n+m) O(n+m)
Max Subarray (Kadane) O(n) O(1)
Binary Search O(log n) O(1)
Palindrome Check O(n) O(n)
Fibonacci O(n) O(1)
Reverse Linked List O(n) O(1)
Detect Cycle (Floyd) O(n) O(1)
Max Depth Binary Tree O(n) O(h)
Invert Binary Tree O(n) O(h)
Level Order (BFS) O(n) O(n)
Validate BST O(n) O(h)
Climbing Stairs O(n) O(1)
Coin Change O(n*k) O(n)
LCS O(m*n) O(m*n)
House Robber O(n) O(1)
Number of Islands O(m*n) O(m*n)
Clone Graph O(V+E) O(V)
Course Schedule O(V+E) O(V+E)
Word Search O(m*n*4^L) O(L)
Merge Intervals O(n log n) O(n)
Product Except Self O(n) O(1)
Permutations O(n!) O(n)
Subsets O(2^n) O(n)
Longest Palindrome O(n^2) O(1)
Longest Substring O(n) O(k)
3Sum O(n^2) O(n)
Trapping Rain Water O(n) O(1)
Queue Using Stacks O(1) amort. O(n)
Min Stack O(1) O(n)
Diameter of Tree O(n) O(h)
Search Rotated Array O(log n) O(1)
Top K Frequent O(n) O(n)
Kth Largest O(n log k) O(k)
Serialize/Deserialize O(n) O(n)
LRU Cache O(1) O(n)
Spiral Matrix O(m*n) O(1)
Rotate Image O(n^2) O(1)
Find Peak Element O(log n) O(1)
Min in Rotated Array O(log n) O(1)
Word Ladder O(n*L*26) O(n*L)
Meeting Rooms II O(n log n) O(n)
Alien Dictionary O(n*L) O(1)
Jump Game O(n) O(1)
Decode Ways O(n) O(1)
Median Two Arrays O(log min(m,n)) O(1)
Regex Matching O(m*n) O(m*n)
Unique Paths O(m*n) O(n)
Tips for Interview Success
1. Always clarify the problem before coding. Ask about edge cases, input constraints, and expected
output format.
2. Think out loud. Interviewers want to understand your thought process, not just see working code.
3. Start with a brute force approach, then optimize. This shows structured problem-solving.
4. Write clean, readable code with meaningful variable names even under pressure.
5. Test your solution with edge cases: empty input, single element, duplicates, negative numbers.
6. Know your complexity trade-offs: time vs space. Be ready to discuss both.
7. Practice these patterns: Sliding Window, Two Pointers, Fast/Slow Pointers, BFS/DFS, Backtracking,
and DP.
8. For Go: understand goroutines, channels, and interfaces. For Python: generators, comprehensions,
and collections.