C++ Algorithm Problem Solving | 10 Essential Coding Test Problems

1. Two Sum

Problem: Find indices of two numbers that sum to target in array.

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;
    
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        
        if (seen.find(complement) != seen.end()) {
            return {seen[complement], i};
        }
        
        seen[nums[i]] = i;
    }
    
    return {};
}

// Time complexity: O(n)
// Space complexity: O(n)

Key Points:

• Use hashmap to store seen numbers
• Check complement before adding current number
• Return immediately when found

2. Binary Search

Problem: Find target in sorted array.

int binarySearch(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// Time complexity: O(log n)

Key Points:

• Use left + (right - left) / 2 to avoid overflow
• left <= right condition (not left < right)
• Update left = mid + 1 or right = mid - 1

3. Maximum Subarray

Problem: Find maximum sum of contiguous subarray.

int maxSubArray(vector<int>& nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
    
    return maxSum;
}

// Kadane's Algorithm
// Time complexity: O(n)

Key Points:

• Kadane’s algorithm: Decide whether to extend or start new at each position
• Track both current sum and max sum
• Handle all negative numbers case

4. Coin Change

Problem: Find minimum number of coins to make amount.

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

// Dynamic Programming
// Time complexity: O(amount * coins.size())

Key Points:

• Initialize dp with large value (amount + 1)
• Base case: dp[0] = 0
• Check if solution exists (dp[amount] > amount means impossible)

5. Number of Islands

Problem: Count number of islands in 2D grid.

class Solution {
private:
    void dfs(vector<vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || 
            j < 0 || j >= grid[0].size() || 
            grid[i][j] == '0') {
            return;
        }
        
        grid[i][j] = '0';  // Mark visited
        
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
    
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return count;
    }
};

// DFS
// Time complexity: O(m * n)

Key Points:

• Mark visited cells to avoid revisiting
• Check boundaries before recursion
• Count each connected component once

6. Valid Parentheses

Problem: Check if parentheses string is valid.

bool isValid(string s) {
    stack<char> st;
    unordered_map<char, char> pairs = {
        {')', '('},
        {'}', '{'},
        {']', '['}
    };
    
    for (char c : s) {
        if (pairs.find(c) == pairs.end()) {
            // Opening bracket
            st.push(c);
        } else {
            // Closing bracket
            if (st.empty() || st.top() != pairs[c]) {
                return false;
            }
            st.pop();
        }
    }
    
    return st.empty();
}

// Time complexity: O(n)

Key Points:

• Use stack for matching pairs
• Check stack not empty before accessing top
• Stack must be empty at end

7. Longest Increasing Subsequence (LIS)

Problem: Find length of longest increasing subsequence.

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    int maxLen = 1;
    
    for (int i = 1; i < nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// Dynamic Programming
// Time complexity: O(n²)

// Optimized version (binary search)
int lengthOfLIS_optimized(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

// Time complexity: O(n log n)

Key Points:

• DP solution: For each position, check all previous smaller elements
• Optimized: Use binary search with tails array
• lower_bound finds first element >= num

8. 0/1 Knapsack

Problem: Find maximum value within maximum weight W.

int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(
                    dp[i-1][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                );
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    
    return dp[n][W];
}

// Time complexity: O(n * W)

Key Points:

• 2D DP: dp[i][w] = max value using first i items with weight limit w
• Choice: Take item or skip
• Can optimize to 1D DP

9. Shortest Path (Dijkstra)

Problem: Find shortest distances from start node to all nodes.

vector<int> dijkstra(vector<vector<pair<int,int>>>& graph, int start) {
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, weight] : graph[u]) {
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    
    return dist;
}

// Time complexity: O((V + E) log V)

Key Points:

• Use min heap (priority queue)
• Skip if already found shorter path
• Works only for non-negative weights

10. Permutation/Combination Generation

Problem: Generate all permutations.

void permute(vector<int>& nums, int start, vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    
    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        permute(nums, start + 1, result);
        swap(nums[start], nums[i]);  // Backtracking
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    permute(nums, 0, result);
    return result;
}

// Time complexity: O(n!)

// Combination
void combine(int n, int k, int start, vector<int>& current, 
             vector<vector<int>>& result) {
    if (current.size() == k) {
        result.push_back(current);
        return;
    }
    
    for (int i = start; i <= n; i++) {
        current.push_back(i);
        combine(n, k, i + 1, current, result);
        current.pop_back();
    }
}

Key Points:

• Backtracking: Swap, recurse, swap back
• Combination: Track start position to avoid duplicates
• Time explodes for large n

Coding Test Tips

1. I/O Optimization

// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

// File I/O
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

2. Frequently Used Template

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Code...
    
    return 0;
}

3. Debugging Macro

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl
#else
#define debug(x)
#endif

int main() {
    int x = 10;
    debug(x);  // Output only locally
}

Common Mistakes

Mistake 1: Integer Overflow

// ❌ Overflow
int sum = a * b;

// ✅ Use long long
long long sum = (long long)a * b;

Mistake 2: Array Out of Bounds

// ❌ No range check
if (grid[i+1][j] == 1) { ... }

// ✅ Range check
if (i+1 < n && grid[i+1][j] == 1) { ... }

Mistake 3: Time Limit Exceeded

// ❌ O(n³)
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)

// ✅ Improve to O(n²) or O(n log n)

FAQ

Q1: Which algorithms should I learn first?

A:

1. Sorting, searching
2. Greedy, DP
3. Graph (BFS, DFS)
4. Advanced (segment tree, etc.)

Q2: Cannot solve problem!

A:

1. Start with small example
2. Think brute force first
3. Find patterns
4. Find similar problems

Q3: How to calculate time complexity?

A:

• Single loop: O(n)
• Nested loops: O(n²)
• Binary search: O(log n)
• Sorting: O(n log n)

Q4: Recommended problem sites?

A:

• LeetCode (English)
• HackerRank (English)
• Codeforces (English)
• AtCoder (English/Japanese)

Q5: How long to prepare for coding tests?

A:

• Basics: 1-2 months
• Intermediate: 3-6 months
• Advanced: 6+ months

Q6: Must I know STL?

A: Yes, vector, map, set, algorithm functions are essential.

---

Related Posts

• Array and List | Essential Data Structures for Coding Tests
• Sorting Problems | Coding Test Sorting Patterns
• DP Practice Problems | Coding Test DP Problem Solving Strategy
• C++ Coding Test Tips
• C++ Coding Test Prep
• C++ Algorithm Guide

---

Practical Tips

Tips you can apply immediately in practice.

Debugging Tips

• Check compiler warnings first when problems occur
• Reproduce problem with simple test cases
• Use print debugging to trace execution

Performance Tips

• Choose correct algorithm class for input size
• Optimize I/O only after algorithm is correct
• Profile before optimizing

Code Review Tips

• Pre-check frequently pointed out parts
• Follow team coding conventions
• Write clear variable names

---

Practical Checklist

Before Solving

• Understand problem constraints (n range, time limit)
• Identify edge cases (empty, size 1, max size)
• Estimate required time complexity

While Solving

• Handle all edge cases?
• Check for overflow?
• Verify boundary conditions?

After Solving

• Test with example inputs?
• Test edge cases?
• Check output format?

---

Keywords

C++, Algorithm, Coding Test, Problem Solving, PS, Two Sum, Binary Search, Dynamic Programming, BFS, DFS, Dijkstra, STL