Problem Solving in Practice
Overview
Covers practical problem solving strategies and type-specific approaches for coding tests and algorithm competitions.
Table of Contents
- Problem Solving Process
- Type Recognition
- Difficulty-based Strategy
- Core Problems by Type
- Time Management Strategy
- Coding Interview Tips
1. Problem Solving Process
1.1 5-Step Approach
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β 5-Step Problem Solving β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β 1. Understand β Identify input/output/constraints β
β 2. Analyze Examplesβ Solve by hand, find patterns β
β 3. Choose Algorithmβ Identify type, verify complexity β
β 4. Implement β Write code, handle edge cases β
β 5. Verify β Test cases, debug β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
1.2 Time Complexity Calculation
Allowed complexity by input size N (1 second limit):
βββββββββββββββ¬ββββββββββββββββββββ¬ββββββββββββββββββ
β Input Size β Max Complexity β Suitable Algo β
βββββββββββββββΌββββββββββββββββββββΌββββββββββββββββββ€
β N β€ 10 β O(N!) β Brute force, backtrackingβ
β N β€ 20 β O(2^N) β Bitmask, backtrackingβ
β N β€ 500 β O(NΒ³) β Floyd-Warshall β
β N β€ 5,000 β O(NΒ²) β DP, brute force β
β N β€ 100,000 β O(N log N) β Sorting, binary searchβ
β N β€ 10^7 β O(N) β Two pointers, hashβ
β N β€ 10^18 β O(log N) β Binary search, mathβ
βββββββββββββββ΄ββββββββββββββββββββ΄ββββββββββββββββββ
1.3 Problem Reading Checklist
# Problem Analysis Template
def analyze_problem():
"""
Checklist:
[ ] Check input range (max N, M)
[ ] Check time limit (usually 1-2 seconds)
[ ] Check memory limit (usually 256MB)
[ ] Check special cases (0, 1, negative, empty input)
[ ] Check output format (decimals, newlines, spaces)
"""
pass
2. Type Recognition
2.1 Keyword-based Recognition
ββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββββ
β Keyword β Algorithm β
ββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββ€
β Shortest distance, min costβ BFS, Dijkstra, Floyd β
β Number of paths/ways β DP, combinatorics β
β Find max/min β Binary search, DP, greedy β
β Is it possible? β Binary search (parametric) β
β All cases, order β Backtracking, permutation β
β Connected, group β Union-Find, DFS/BFS β
β Range sum, cumulative β Prefix sum, segment tree β
β Consecutive subarray β Sliding window, two pointers β
β String matching β KMP, hash, trie β
ββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββ
2.2 Data Structure Selection Guide
ββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββββ
β Required Operation β Data Structure β
ββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββ€
β Fast insert/delete (front/back)β Deque β
β Fast search (key-value)β HashMap/Dictionary β
β Maintain sorted order β TreeMap, heap β
β Fast access to max/min β Heap (Priority Queue) β
β Remove duplicates β Set, hash set β
β Ordered unique values β OrderedDict, TreeSet β
β Range queries β Segment tree, Fenwick tree β
ββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββ
2.3 Problem Type Decision Tree
Problem Start
β
ββββββββββββββ΄βββββββββββββ
β Optimization problem? β
ββββββββββββββ¬βββββββββββββ
ββββββββ΄βββββββ
YES NO
β β
ββββββββββββββ΄ββββ ββββββ΄βββββ
β Greedy works? β β Search/enumerateβ
ββββββββββββββ¬ββββ ββββββ¬βββββ
βββββββββ΄ββββββββ β
YES NO β
β β β
Greedy DP ββ΄ββββββββββ
β All cases?β
ββ¬ββββββββββ
ββββββββ΄βββββββ
YES NO
β β
Backtracking Graph search
Brute force (DFS/BFS)
3. Difficulty-based Strategy
3.1 Easy (Bronze~Silver)
Key Points:
β Implement problem as described
β Use basic data structures
β Time complexity not critical
Main Types:
- Simple implementation/simulation
- Basic sorting/searching
- 1D DP
- Basic graph traversal
Example Approach:
1. Translate problem conditions directly to code
2. Verify with example cases
3. Test edge cases (0, 1, max value)
# Easy problem template - Two Sum
def two_sum_easy(nums, target):
"""
Brute force sufficient (N β€ 1000)
O(NΒ²) allowed
"""
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
3.2 Medium (Gold)
Key Points:
β Algorithm selection important
β Time complexity verification required
β Apply optimization techniques
Main Types:
- Binary search applications
- Graph algorithms (Dijkstra, MST)
- 2D DP
- Two pointers/sliding window
- Tree DP
Example Approach:
1. Identify type β Choose algorithm
2. Calculate complexity β Check feasibility
3. Implement β Optimize
# Medium problem template - Two Sum (optimized)
def two_sum_medium(nums, target):
"""
Optimize with hash map (N β€ 100,000)
O(N) needed
"""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
3.3 Hard (Platinum+)
Key Points:
β Combine multiple algorithms
β Advanced data structures needed
β Creative approach required
Main Types:
- Segment tree/Fenwick tree
- Advanced graph (SCC, 2-SAT)
- Bitmask DP
- Convex hull, geometry
- Advanced string (suffix array, Manacher)
Example Approach:
1. Decompose problem β Define subproblems
2. Check if known algorithms apply
3. Observe β Derive optimization ideas
4. Core Problems by Type
4.1 Array/String
# Type 1: Sliding window - Maximum subarray sum
def max_subarray_sum(arr, k):
"""
Maximum sum of subarray of size k
Time: O(N)
"""
n = len(arr)
if n < k:
return 0
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, n):
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
# Type 2: Two pointers - Two sum in sorted array
def two_sum_sorted(arr, target):
"""
Find two numbers that sum to target in sorted array
Time: O(N)
"""
left, right = 0, len(arr) - 1
while left < right:
current = arr[left] + arr[right]
if current == target:
return [left, right]
elif current < target:
left += 1
else:
right -= 1
return []
# Type 3: Prefix sum - Range sum queries
class PrefixSum:
def __init__(self, arr):
self.prefix = [0]
for x in arr:
self.prefix.append(self.prefix[-1] + x)
def query(self, l, r):
"""Sum of range [l, r] (0-indexed)"""
return self.prefix[r + 1] - self.prefix[l]
4.2 Graph
from collections import deque
import heapq
# Type 1: BFS - Shortest distance (unweighted)
def bfs_shortest(graph, start, end):
"""
Shortest distance in unweighted graph
Time: O(V + E)
"""
n = len(graph)
dist = [-1] * n
dist[start] = 0
queue = deque([start])
while queue:
curr = queue.popleft()
if curr == end:
return dist[end]
for next_node in graph[curr]:
if dist[next_node] == -1:
dist[next_node] = dist[curr] + 1
queue.append(next_node)
return -1
# Type 2: Dijkstra - Shortest distance (weighted)
def dijkstra(graph, start):
"""
Shortest distance in weighted graph
graph: adjacency list [(next, weight), ...]
Time: O((V + E) log V)
"""
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
pq = [(0, start)] # (distance, node)
while pq:
d, curr = heapq.heappop(pq)
if d > dist[curr]:
continue
for next_node, weight in graph[curr]:
new_dist = dist[curr] + weight
if new_dist < dist[next_node]:
dist[next_node] = new_dist
heapq.heappush(pq, (new_dist, next_node))
return dist
# Type 3: Union-Find - Connected components
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
4.3 Dynamic Programming
# Type 1: 1D DP - Climbing stairs
def climb_stairs(n):
"""
Number of ways to climb n stairs (1 or 2 steps at a time)
Time: O(N), Space: O(1)
"""
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
# Type 2: 2D DP - 0/1 Knapsack
def knapsack_01(weights, values, capacity):
"""
Maximum value within capacity constraint
Time: O(N * W), Space: O(W)
"""
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# Type 3: String DP - LCS
def lcs_length(s1, s2):
"""
Longest common subsequence length
Time: O(N * M)
"""
n, m = len(s1), len(s2)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
# Type 4: Interval DP - Matrix chain multiplication
def matrix_chain(dims):
"""
Minimum operations for matrix multiplication
dims: matrix dimensions [d0, d1, d2, ...] β (d0Γd1) Γ (d1Γd2) Γ ...
Time: O(NΒ³)
"""
n = len(dims) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n - 1]
4.4 Binary Search
# Type 1: Value search - lower_bound / upper_bound
def lower_bound(arr, target):
"""First position >= target"""
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
def upper_bound(arr, target):
"""First position > target"""
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
# Type 2: Parametric search - Cutting trees
def cut_trees(heights, target):
"""
Set cutter height to get at least target wood, find maximum height
Time: O(N log max(H))
"""
def can_get(cut_height):
total = sum(max(0, h - cut_height) for h in heights)
return total >= target
left, right = 0, max(heights)
result = 0
while left <= right:
mid = (left + right) // 2
if can_get(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return result
# Type 3: Binary search + Greedy - Router installation
def install_routers(houses, n):
"""
Install n routers to maximize minimum distance
Time: O(N log D)
"""
houses.sort()
def can_install(min_dist):
count = 1
last = houses[0]
for h in houses[1:]:
if h - last >= min_dist:
count += 1
last = h
return count >= n
left, right = 1, houses[-1] - houses[0]
result = 0
while left <= right:
mid = (left + right) // 2
if can_install(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return result
4.5 Backtracking
# Type 1: Permutation generation
def permutations(nums):
"""Generate all permutations - O(N! * N)"""
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(path[:])
return
for i, num in enumerate(nums):
if used[i]:
continue
used[i] = True
path.append(num)
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
# Type 2: Combination generation
def combinations(nums, k):
"""Generate all combinations of size k - O(C(N,K) * K)"""
result = []
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
# Type 3: N-Queens
def solve_n_queens(n):
"""Number of solutions to N-Queens"""
count = 0
cols = [False] * n
diag1 = [False] * (2 * n - 1) # row - col + n - 1
diag2 = [False] * (2 * n - 1) # row + col
def backtrack(row):
nonlocal count
if row == n:
count += 1
return
for col in range(n):
d1 = row - col + n - 1
d2 = row + col
if cols[col] or diag1[d1] or diag2[d2]:
continue
cols[col] = diag1[d1] = diag2[d2] = True
backtrack(row + 1)
cols[col] = diag1[d1] = diag2[d2] = False
backtrack(0)
return count
5. Time Management Strategy
5.1 Problem Allocation Strategy
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Coding Test Time Allocation (3 hour limit) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β [Survey] 15m Read all problems, assess difficultyβ
β β β
β [Easy] 45m Solve definitely solvable problemsβ
β β β
β [Medium] 90m Core problems, aim for partial scoreβ
β β β
β [Hard] 20m Implement ideas only β
β β β
β [Review] 10m Check runtime errors, edge cases β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5.2 Problem Priority
Priority determination criteria:
1. Score vs difficulty
- Easy problems first (secure points)
- Attempt hard problems if partial credit available
2. Type familiarity
- Practiced types first
- New types later
3. Time constraint
- Time-consuming problems later
- Be careful with heavy implementation
5.3 When Stuck
1. 5-minute rule
- No progress in 5 minutes β switch problems
2. Simplify
- Reduce input size and think
- Solve special cases first
3. Think backwards
- Work backwards from output
- "What do I need to compute this?"
4. Find patterns
- Trace examples by hand
- Discover regularities
5. Partial credit
- Solve small cases only
- Submit even brute force
6. Coding Interview Tips
6.1 Interview Process
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Coding Interview Stages β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Problem Description (5m) β
β - Interviewer presents problem β
β - Ask questions if unclear β
β β
β 2. Discuss Approach (10m) β
β - Explain thinking out loud β
β - Exchange ideas with interviewer β
β - Mention time/space complexity β
β β
β 3. Coding (20-25m) β
β - Code while explaining β
β - OK to ask for hints if stuck β
β β
β 4. Testing (5m) β
β - Hand trace with examples β
β - Discuss edge cases β
β β
β 5. Optimization/Follow-up (5m) β
β - Discuss improvement approaches β
β - Handle variant problems β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
6.2 Communication Strategy
# Good example: Share thought process
"""
Interviewer: Find two numbers in array that sum to target.
Me: Let me understand the problem.
- Given an array
- Return two indices that sum to target
- Is it sorted? β (question)
First thinking brute force, that's O(NΒ²).
Check all pairs.
More efficiently... using a hash map gets O(N).
For each number, check if target - num is already in hash.
Does this approach sound good? β (confirmation)
Then I'll write the code.
"""
6.3 Frequently Asked Question Types
1. Two Sum variants
- Sorted array β Two pointers
- Three sum β Sort + two pointers
- Closest sum β Sort + two pointers
2. Linked List
- Cycle detection β Floyd's algorithm
- Middle node β Fast/slow pointers
- Reverse β Iterative or recursive
3. Tree
- Traversal β Recursive/stack
- Max depth β DFS
- LCA β Recursion
4. Graph
- Check connectivity β DFS/BFS
- Shortest path β BFS
- Cycle β DFS + visit states
5. Dynamic Programming
- Climbing stairs β Fibonacci
- Max subarray β Kadane's
- Coin change β Unbounded knapsack
Baekjoon (BOJ)
LeetCode
Programmers
| Level |
Problem |
Type |
| Lv2 |
Target Number |
DFS/BFS |
| Lv2 |
Game Map Shortest Distance |
BFS |
| Lv3 |
Network |
Union-Find |
| Lv3 |
Way to School |
DP |
Learning Roadmap
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Skill Improvement Roadmap β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β [Month 1] Build Foundation β
β - Array, string, stack, queue β
β - Basic sorting, binary search β
β - 1 Easy problem per day β
β β
β [Month 2] Core Algorithms β
β - DFS, BFS, graph basics β
β - 1D DP β
β - 1 Easy/Medium problem per day β
β β
β [Month 3] Advanced Learning β
β - Dijkstra, Union-Find β
β - 2D DP, backtracking β
β - 1-2 Medium problems per day β
β β
β [Month 4+] Practical Practice β
β - Mock tests (with time limit) β
β - Challenge Hard problems β
β - Strengthen weak areas β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Practice Problems
Comprehensive Problems
| No. |
Problem |
Difficulty |
Hint |
| 1 |
K-th largest number in array |
ββ |
Heap or quickselect |
| 2 |
Maze shortest distance |
ββ |
BFS |
| 3 |
Maximum consecutive subarray sum |
ββ |
Kadane's Algorithm |
| 4 |
Word conversion |
βββ |
BFS |
| 5 |
Longest increasing subsequence |
βββ |
DP + binary search |
References
Checklist: Coding Test Preparation
Essential Types (Must be able to solve):
β‘ Binary search - lower_bound, parametric search
β‘ BFS - Shortest distance, level traversal
β‘ DFS - Connected components, cycles
β‘ DP - 1D, 2D basics
β‘ Greedy - Sort then select
β‘ Two pointers - Sum problems
β‘ Hash map - Frequency, duplicate check
Intermediate Types (Most tests include):
β‘ Dijkstra - Weighted shortest path
β‘ Union-Find - Grouping
β‘ Backtracking - Permutations, combinations
β‘ Sliding window - Consecutive intervals
β‘ Tree traversal - Pre/in/post-order
Advanced Types (Difficult tests):
β‘ Segment tree - Range queries
β‘ Topological sort - Dependency ordering
β‘ LCA - Common ancestor
β‘ Bitmask DP - State compression
Previous Step