C++ Coding Test | "Baekjoon·Programmers" STL Usage by Algorithm Type

· 22분 읽기 · 수정 Intermediate Concept
C++ Coding Test | "Baekjoon·Programmers" STL Usage by Algorithm Type

이 글의 핵심

Practical guide for C++ coding test interviews.

Introduction: C++ Coding Test Interview, What to Prepare?

Coding test interviews (exams where you solve algorithm/data structure problems in code within a time limit) are typically conducted on a whiteboard or online IDE where you solve algorithm problems in 30-60 minutes. Difficulty varies by company, but they evaluate data structure/algorithm fundamentals and C++ STL usage skills. This article is an interview preparation guide summarizing frequently appearing problem types, essential STL functions, and practical tips.

What this article covers:

  • 7 frequently appearing algorithm types in coding test interviews
  • Essential C++ STL functions summary (vector, map, set, algorithm)
  • Time complexity analysis and optimization strategies
  • Practical tips: I/O optimization, edge cases, code readability
  • Interview day checklist

The algorithm types and preparation flow frequently appearing in coding tests are summarized below.

flowchart LR
  subgraph type["Types"]
    S[Sort·Search]
    D[DP]
    G[Graph]
    T[Tree]
  end
  subgraph prep["Preparation"]
    STL[STL Usage]
    IO[I/O Optimization]
    TC[Time Complexity]
  end
  type --> prep

Table of Contents

  1. 7 Frequently Appearing Algorithm Types
  2. Essential C++ STL Functions Summary
  3. Time Complexity Analysis and Optimization
  4. Practical Tips: I/O, Edge Cases, Readability
  5. Interview Day Checklist

1. 7 Frequently Appearing Algorithm Types

1) Sorting and Searching

Representative Problems:

  • Find specific value after sorting array (binary search)
  • Find K-th largest/smallest element
  • Intersection/union of two arrays

Key STL:

  • std::sort(v.begin(), v.end())
  • std::binary_search, std::lower_bound, std::upper_bound
  • std::nth_element (K-th element)

When to use sorting?
Sorting is an expensive operation at O(N log N), but after sorting you can use efficient algorithms like binary search (O(log N)) and two pointers (O(N)). Problems that would require brute force O(N²) can be solved in O(N log N) with sort + binary search.

lower_bound vs upper_bound:

  • lower_bound(x): First position ≥ x
  • upper_bound(x): First position > x
  • Difference: upper_bound - lower_bound = count of x

Example Code (copy-paste and run with g++ -std=c++17 -o binsearch_demo binsearch_demo.cpp && ./binsearch_demo):

// Copy-paste and run: g++ -std=c++17 -o binsearch_demo binsearch_demo.cpp && ./binsearch_demo
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5};
    std::sort(v.begin(), v.end());  // {1, 1, 3, 4, 5}
    bool found = std::binary_search(v.begin(), v.end(), 3);
    auto it = std::lower_bound(v.begin(), v.end(), 3);
    std::cout << found << " " << (it - v.begin()) << "\n";  // 1 2
    return 0;
}

Execution Result: Outputs 1 2 (found and index) on one line.

2) HashMap (Frequency, Duplicate Check)

Representative Problems:

  • Find duplicate elements in array
  • Check if two strings are anagrams
  • Count subarrays with sum K (prefix sum + hashmap)

Key STL:

  • std::unordered_map<int, int> (O(1) average access)
  • std::unordered_set<int> (duplicate check)

HashMap Core:
HashMap allows insert/delete/search in O(1) average time. Problems that would require nested loops O(N²) can often be solved in O(N).

Two Sum Problem Example:
“Find two elements that sum to K in array”

Brute Force (O(N²)):

for (int i = 0; i < n; ++i) {
    for (int j = i+1; j < n; ++j) {
        if (arr[i] + arr[j] == K) { /* Found */ }
    }
}

HashMap Method (O(N)):

std::unordered_set<int> seen;
for (int x : arr) {
    if (seen.count(K - x)) { /* Found */ }
    seen.insert(x);
}

Example Code:

std::unordered_map<int, int> freq;
for (int x : arr) {
    freq[x]++;
}

// Most frequent element
int maxFreq = 0, result = 0;
for (auto& [num, cnt] : freq) {
    if (cnt > maxFreq) {
        maxFreq = cnt;
        result = num;
    }
}

3) Two Pointers

Representative Problems:

  • Find two elements that sum to K in sorted array
  • Maximum length of subarray with sum ≤ K
  • Palindrome check

Key Idea:

  • Move left and right pointers simultaneously to solve in O(N)

Example Code:

// Two elements that sum to target in sorted array
std::vector<int> v = {1, 2, 3, 4, 5};
int target = 7;
int left = 0, right = v.size() - 1;

while (left < right) {
    int sum = v[left] + v[right];
    if (sum == target) {
        std::cout << v[left] << ", " << v[right] << '\n';
        break;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

4) Dynamic Programming (DP)

DP (Dynamic Programming—algorithm technique that stores answers to small subproblems and reuses them to solve larger problems) representative problems are:

Representative Problems:

  • Fibonacci sequence
  • Longest Increasing Subsequence (LIS)
  • Knapsack problem
  • Shortest path (DP + graph)

Key Idea:

  • Memoization: Store calculated values in array for reuse

Why use DP?
Recursive solutions have duplicate calculations. For example, when calculating fib(5):

  • fib(5) = fib(4) + fib(3)
  • fib(4) = fib(3) + fib(2)
  • fib(3) is calculated twice.

Calculating fib(50) with pure recursion requires billions of function calls, but with DP only 50 calculations.

Top-Down vs Bottom-Up:

  • Top-Down (Memoization): Recursion + cache. Calculates only needed values.
  • Bottom-Up (Tabulation): Loop from small problems sequentially. Usually faster.

Example Code (Fibonacci):

std::vector<long long> dp(100, -1);

long long fib(int n) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];  // Already calculated
    return dp[n] = fib(n-1) + fib(n-2);
}

Bottom-Up Method (faster):

std::vector<long long> dp(100);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i < 100; ++i) {
    dp[i] = dp[i-1] + dp[i-2];
}

5) Graph Traversal (BFS, DFS)

Graph (data structure of vertices and edges. Example: cities=vertices, roads=edges on map) traversal representative problems are:

Representative Problems:

  • Maze shortest path (BFS)
  • Count connected components (DFS/BFS)
  • Cycle detection
  • Topological sort

Key STL:

  • std::queue<int> (BFS)
  • std::stack<int> or recursion (DFS)
  • std::vector<std::vector<int>> (adjacency list)

BFS Example:

std::vector<std::vector<int>> graph(n);
std::vector<bool> visited(n, false);
std::queue<int> q;

q.push(start);
visited[start] = true;

while (!q.empty()) {
    int node = q.front();
    q.pop();
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            q.push(neighbor);
        }
    }
}

6) Greedy

Representative Problems:

  • Meeting room assignment (activity selection problem)
  • Coin change (specific conditions)
  • Minimum spanning tree (Kruskal, Prim)

Key Idea:

  • Best choice at each moment leads to global optimum

Example Code (Meeting Room Assignment):

struct Meeting {
    int start, end;
};

std::vector<Meeting> meetings = {{1, 3}, {2, 4}, {3, 5}};

// Sort by end time
std::sort(meetings.begin(), meetings.end(), [](auto a, auto b) {
    return a.end < b.end;
});

int count = 0, lastEnd = 0;
for (auto& m : meetings) {
    if (m.start >= lastEnd) {
        count++;
        lastEnd = m.end;
    }
}

7) Backtracking

Representative Problems:

  • N-Queen
  • Generate permutations/combinations
  • Sudoku solver

Key Idea:

  • Try all cases recursively, but backtrack immediately if condition not met

Example Code (Permutation):

void permute(std::vector<int>& nums, int start) {
    if (start == nums.size()) {
        // One permutation complete
        for (int x : nums) std::cout << x << ' ';
        std::cout << '\n';
        return;
    }
    
    for (int i = start; i < nums.size(); ++i) {
        std::swap(nums[start], nums[i]);
        permute(nums, start + 1);
        std::swap(nums[start], nums[i]);  // Backtracking
    }
}

Or using STL:

std::vector<int> v = {1, 2, 3};
std::sort(v.begin(), v.end());
do {
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
} while (std::next_permutation(v.begin(), v.end()));

2. Essential C++ STL Functions Summary

vector

std::vector<int> v = {1, 2, 3};
v.push_back(4);           // Add to end
v.pop_back();             // Remove from end
v.size();                 // Size
v.empty();                // Is empty?
v.clear();                // Clear all
v[0];                     // Index access (no range check)
v.at(0);                  // Range check (throws exception)

map (Sorted Keys)

std::map<std::string, int> m;
m["apple"] = 1;
m["banana"] = 2;

if (m.count("apple")) {   // Key exists?
    std::cout << m["apple"] << '\n';
}

for (auto& [key, val] : m) {  // Iterate in key order
    std::cout << key << ": " << val << '\n';
}

unordered_map (HashMap, O(1) Average)

std::unordered_map<int, int> freq;
for (int x : arr) {
    freq[x]++;
}

set (Unique Sorted Elements)

std::set<int> s = {3, 1, 4, 1, 5};  // {1, 3, 4, 5}
s.insert(2);
s.erase(3);
bool exists = s.count(4);  // 1 (exists) or 0 (not exists)

algorithm Header

#include <algorithm>

std::sort(v.begin(), v.end());                    // Ascending sort
std::sort(v.begin(), v.end(), std::greater<>());  // Descending

std::reverse(v.begin(), v.end());                 // Reverse

auto it = std::find(v.begin(), v.end(), 42);      // Find value
if (it != v.end()) { /* Found */ }

int maxVal = *std::max_element(v.begin(), v.end());
int minVal = *std::min_element(v.begin(), v.end());

std::next_permutation(v.begin(), v.end());        // Next permutation

3. Time Complexity Analysis and Optimization

Frequently Appearing Time Complexities

ComplexityN=100N=10,000N=1,000,000Example Algorithm
O(1)111HashMap access
O(log N)71320Binary search
O(N)10010,0001,000,000Linear search, traversal
O(N log N)700130,00020,000,000Sorting (merge sort)
O(N²)10,000100,000,0001,000,000,000,000Nested loops
O(2^N)1.3×10³⁰--Brute force (backtracking)

Time Limit and Complexity

1 second limit roughly allows:

  • O(N): N ≤ 10⁸
  • O(N log N): N ≤ 10⁶
  • O(N²): N ≤ 10⁴
  • O(N³): N ≤ 500

Why these standards?
Modern computers can perform about 10⁸~10⁹ basic operations per second. But real algorithms have overhead from function calls, memory access, branches, so we safely assume 10⁸.

Concrete Example:

  • N=10⁶, O(N²) → 10¹² operations → 1000 seconds (time exceeded)
  • N=10⁶, O(N log N) → 2×10⁷ operations → 0.2 seconds (pass)

Common interview mistake: Apply O(N²) algorithm to N=10⁶ input → time exceeded

Tip: Look at N range in problem and reverse-calculate allowed complexity.

  • N ≤ 10 → O(N!) possible (brute force)
  • N ≤ 20 → O(2^N) possible (bitmask DP)
  • N ≤ 500 → O(N³) possible (Floyd-Warshall)
  • N ≤ 10⁴ → O(N²) possible (nested loops)
  • N ≤ 10⁶ → O(N log N) needed (sorting, segment tree)
  • N ≤ 10⁸ → O(N) needed (linear algorithm)

Optimization Strategies

1. Remove unnecessary iterations:

// ❌ Call size() every time
for (int i = 0; i < v.size(); ++i) { }

// ✅ Calculate once
int n = v.size();
for (int i = 0; i < n; ++i) { }

2. HashMap to reduce O(N²) → O(N):

// ❌ O(N²)
for (int i = 0; i < n; ++i) {
    for (int j = i+1; j < n; ++j) {
        if (arr[i] + arr[j] == target) { /* ... */ }
    }
}

// ✅ O(N)
std::unordered_set<int> seen;
for (int x : arr) {
    if (seen.count(target - x)) {
        // Found
    }
    seen.insert(x);
}

3. Use sorting:

Sorting costs O(N log N), but enables binary search/two pointers to reduce O(N²) → O(N log N) or O(N).

2. Essential C++ STL Functions Summary

Container Selection Guide

RequirementRecommended ContainerTime Complexity
Order preservation, fast accessvectorAccess O(1), Insert/Delete O(N)
Unique set, sortedsetInsert/Delete/Search O(log N)
Unique set, unorderedunordered_setAverage O(1)
Key-value pairs, sortedmapO(log N)
Key-value pairs, unorderedunordered_mapAverage O(1)
Queue (FIFO)queueO(1)
Stack (LIFO)stackO(1)
Priority queuepriority_queueInsert/Delete O(log N)

Frequently Used algorithm Header Functions

#include <algorithm>

// Sorting
std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });  // Descending

// Searching
auto it = std::find(v.begin(), v.end(), 42);
bool found = std::binary_search(v.begin(), v.end(), 42);  // Requires sorted

// Min/Max
int maxVal = *std::max_element(v.begin(), v.end());
int minVal = *std::min_element(v.begin(), v.end());

// Remove duplicates (after sorting)
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());

// Permutation
std::next_permutation(v.begin(), v.end());

// Partial sort (K-th element)
std::nth_element(v.begin(), v.begin() + k, v.end());

string Functions

std::string s = "hello";
s.size();                     // Length
s.substr(1, 3);               // "ell" (start index, length)
s.find("ll");                 // 2 (position), or std::string::npos if not found
s.rfind("l");                 // 3 (search from back)

// String → number
int num = std::stoi("123");
long long big = std::stoll("123456789012");

// Number → string
std::string str = std::to_string(123);

4. Practical Tips: I/O, Edge Cases, Readability

I/O Optimization

In online judges like Baekjoon/Programmers, heavy I/O can cause time limit exceeded.

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

int main() {
    ios_base::sync_with_stdio(false);  // ✅ Turn off C stream sync
    cin.tie(NULL);                     // ✅ Separate cin/cout buffers
    
    int n;
    cin >> n;
    
    // Use '\n' instead of endl for output
    cout << n << '\n';  // ✅ Fast
    // cout << n << endl;  // ❌ Slow (flushes every time)
    
    return 0;
}

Why do this?

sync_with_stdio(false):
By default, C++ streams (cin, cout) and C streams (scanf, printf) are synchronized. This ensures output order is maintained even when mixed. But this synchronization has high overhead. If not using C streams, turning off sync makes it 2-3x faster.

cin.tie(NULL):
By default, cin is tied to cout. Before reading with cin, it automatically flushes the cout buffer. This is useful for interactive programs, but in coding tests it causes unnecessary flushes and slowdown.

endl vs \n:
endl is newline + buffer flush. With 100,000 outputs, 100,000 flushes occur, extremely slow. '\n' only adds newline, buffer is automatically flushed or flushed at program end.

Practical Effect:
For problem with 100,000 input lines and 100,000 output lines:

  • Without optimization: 3-5 seconds (time exceeded)
  • With optimization: 0.3-0.5 seconds (pass)

Related Post: C++ Coding Test I/O Cheatsheet

Edge Case Check

What interviewers frequently check:

  • Empty input (N=0, empty array)
  • Min/max values (N=1, N=10⁶)
  • Duplicate elements (all elements same)
  • Negative/zero (did problem assume positive only?)
  • Overflow (exceeds int range → use long long)

Example:

// ❌ Crashes when N=0
int maxVal = v[0];
for (int x : v) maxVal = std::max(maxVal, x);

// ✅ Handle empty array
if (v.empty()) return -1;  // Or handle exception
int maxVal = *std::max_element(v.begin(), v.end());

Code Readability

In interviews, “readable code” is as important as correct answer.

1. Meaningful variable names:

// ❌
int a = 0, b = 0;

// ✅
int leftPointer = 0, rightPointer = n - 1;

2. Function separation:

// ✅ Separate complex logic into functions
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

3. Comments (when needed):

// Find pair with sum equal to target using two pointers
int left = 0, right = n - 1;

5. Interview Day Checklist

Problem Understanding Phase (5 minutes)

  • Check input format and range (N ≤ ?, negatives allowed?)
  • Check output format (multiple lines? space-separated?)
  • Trace example input/output by hand
  • Think about edge cases (N=0, N=1, duplicates, max value)

Algorithm Design Phase (5-10 minutes)

  • Calculate time complexity of brute force
  • Determine if possible within time limit
  • Think of optimization methods (sorting? hashmap? DP?)
  • Explain approach to interviewer (essential for whiteboard interviews)

Coding Phase (15-30 minutes)

  • Copy-paste I/O optimization template (sync_with_stdio, cin.tie)
  • Clear function/variable names
  • Check loop ranges (< vs <=, index 0 vs 1)
  • Check overflow (int vs long long)

Testing Phase (5-10 minutes)

  • Run with example input
  • Test edge cases directly (N=0, N=1, max value)
  • Recheck time complexity

Explanation Phase (to interviewer)

  • Explain algorithm approach
  • Mention time/space complexity
  • Mention optimization possibilities (if time permits)

Frequently Asked Interview Questions

1. “What is the time complexity?”

Example Answer:

“Sorting takes O(N log N), then two pointers takes O(N), so total is O(N log N).“

2. “What about space complexity?”

Example Answer:

“Besides input array, I use a hashmap, so worst case is O(N).“

3. “Can you optimize further?”

Example Answer:

“Currently O(N log N), but if input is limited to specific range, could reduce to O(N) with counting sort.”

4. “How do you handle edge cases?”

Example Answer:

“When N=0, I return empty array, and when N=1, I return first element directly with exception handling.”

Practical Preparation Roadmap

Stage 1: Review Basic Data Structures/Algorithms (1-2 weeks)

  • Data Structures: Array, linked list, stack, queue, hashmap, tree, heap
  • Algorithms: Sorting, searching, recursion, DP, graph (BFS/DFS), greedy

Recommended Resources:

  • Baekjoon step-by-step problems
  • Programmers Level 1-2

Stage 2: Problem Solving by Type (2-3 weeks)

  • Sort/Search: Baekjoon 10 problems
  • DP: Baekjoon 10 problems (Fibonacci, LIS, knapsack)
  • Graph: BFS/DFS 5 problems each
  • Greedy: 5 problems
  • Two Pointers/Sliding Window: 5 problems

Stage 3: Mock Interview (1 week)

  • Set 30-minute timer and solve problems
  • Write on whiteboard by hand (without typing)
  • Mock interview with friend/colleague (practice explaining)

Stage 4: Past Exam Problems

  • Search for coding test reviews of target companies (Baekjoon, Programmers, etc.)
  • Intensive practice on similar types

Communication Tips During Interview

1. Confirm Understanding of Problem

“I want to confirm my understanding. The input is an array of N integers, and I need to return the indices of two elements that sum to K, correct?“

2. Explain Approach First

“First I’ll sort the array, then use two pointers from both ends to narrow down and check the sum. Time complexity is O(N log N).“

3. Request Hints When Stuck

“I’m currently thinking about how to define the DP table. Could you give me a hint?“

4. Mention Trade-offs

“Using hashmap is O(N) but space complexity is O(N), while sorting is O(N log N) but space is O(1). Which would be better?”

Common Mistakes

1. No I/O Optimization

Submitting heavy I/O problems without sync_with_stdio(false), cin.tie(NULL) → time exceeded

2. int Overflow

int a = 1000000, b = 1000000;
int result = a * b;  // ❌ Exceeds int range (2×10¹²)

Solution:

long long result = (long long)a * b;  // ✅

3. Array Out of Bounds

int arr[100];
for (int i = 0; i <= 100; ++i) {  // ❌ i=100 is out of bounds
    arr[i] = 0;
}

Solution: Use i < 100 or vector’s at().

4. Binary Search Without Sorting

binary_search only works on sorted arrays.

std::vector<int> v = {3, 1, 4};
bool found = std::binary_search(v.begin(), v.end(), 3);  // ❌ Not sorted

Solution:

std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 3);  // ✅
PlatformFeaturesRecommended For
Baekjoon (BOJ)Korean, step-by-step problems, various difficultyKorean job seekers
ProgrammersKorean, company past problemsKorean company interview prep
LeetCodeEnglish, global company problems (FAANG)International jobs, high difficulty
CodeforcesEnglish, competitive programming styleAlgorithm skill improvement

Summary: For C++ coding tests, learn STL, I/O optimization, and frequently used patterns, then practice on Baekjoon/Programmers. Next, read I/O Cheatsheet or STL Algorithms.

Frequently Asked Questions (FAQ)

Q. Is C++ more advantageous than Python for coding tests?

A: Depends on the problem.

  • Advantages: Fast execution (tight time limits)
  • Disadvantages: Longer code, complex I/O setup
  • Conclusion: Use the language you’re most comfortable with.

Q. Can I always use bits/stdc++.h?

A: OK for online judges (Baekjoon, Programmers) but not in production. Slow compilation and poor portability. In interviews, explain it as “convenience header for coding tests”.

Q. Is C++ coding test impossible without STL?

A: Almost impossible. Without basic STL like vector, map, sort, implementing arrays and sorting from scratch takes too much time. Must learn at least vector, map, set, sort, find.

Q. What if I get a compile error during interview?

A: Do not panic. Read error message and fix calmly. Interviewers also evaluate debugging skills. Say “I forgot a semicolon” and fix it.

  • C++ Coding Test I/O Cheatsheet: I/O optimization template
  • C++ STL Cheatsheet: STL container/algorithm summary
  • STL Algorithms: Essential algorithms like sort, find, transform
  • C++ STL Algorithms: Usage by type

C++ coding test interviews evaluate algorithm knowledge + STL usage + time complexity analysis. Solve 10 problems each of the above 7 types and memorize the I/O optimization template to handle most problems. During interviews, explain approach first and mention edge cases to make a good impression. Even when stuck, verbalize your thought process. Interviewers want to see your problem-solving process more than the answer.

Search Keywords: C++ coding test, coding test interview prep, Baekjoon Programmers, STL algorithm types, time complexity

Posts connected to this topic.

  • C++ Coding Test I/O | “Got TLE” sync_with_stdio Copy-Paste Template
  • C++ STL Algorithms | Using sort·find·transform with Lambdas (Practical Patterns)
  • C++ Junior Developer Interview | “No Project Experience” Portfolio/Answer Strategy

Keywords

C++, Coding Test, Interview Prep, Algorithm, STL, Time Complexity, Baekjoon, Programmers - search these keywords to find this article helpful.