Free lesson · DSA Mastery - Interview Prep, End to End

C++ for DSA

Easy7 min readdsaprogramming-fundamentals

C++ for DSA

C++ is the language of choice for engineers who care about raw performance - competitive programmers, systems engineers, and candidates targeting roles where execution speed matters. Most FAANG interviewers accept it without question. It is also the language where the Standard Template Library (STL) gives you the most fine-grained control over data structures and algorithms.

This topic covers the C++ APIs and idioms that matter for DSA problems. It assumes you know C++ syntax basics. The focus is on the STL containers and the patterns that show up in interview code.

Why C++ for Interviews

C++ has specific advantages:

• Speed. C++ is often 5-10x faster than Java and 30-100x faster than Python at the byte level. For problems with strict time limits, this margin matters.
• STL containers. <vector>, <unordered_map>, <priority_queue>, <set>, <map> are all production-quality and exactly what you need.
• Familiar to competitive programmers. If you have a competitive-programming background, you already know C++.
• Direct memory control. When a problem needs you to think about cache locality or memory layout, C++ lets you reason about it.

The trade-offs:

• More verbose for object-oriented patterns. Classes are more boilerplate than in Python.
• Awkward priority queue defaults. C++'s priority_queue is a max-heap, opposite to Python and Java conventions.
• Manual memory management. Modern C++ uses smart pointers, but interview code often falls back to raw pointers, which is a footgun.

The Core STL Containers

The STL has every container you need for interview problems.

The non-unordered_ versions (map, set) are tree-based and keep their elements sorted. The unordered_ versions are hash-based and faster on average but unordered.

Vectors

vector<T> is C++'s dynamic array. It is the default container for most interview problems.

#include <vector>

vector<int> v = {5, 2, 8, 1, 9, 3};
v.push_back(10);          // add to end
v.pop_back();             // remove from end
v[0];                     // index, no bounds check
v.at(0);                  // index, bounds-checked (throws)
v.front();                // first element
v.back();                 // last element
v.size();                 // size
v.empty();                // is empty?
v.clear();                // remove all elements

To iterate:

for (int i = 0; i < v.size(); i++) {
    cout << v[i];
}

for (int x : v) {
    cout << x;
}

for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it;
}

The range-based for loop (for (int x : v)) is the cleanest. Use it when you do not need the index.

For 2D vectors:

vector<vector<int>> grid(3, vector<int>(4, 0));
// 3x4 grid initialized to 0

grid[1][2] = 5;

Unordered Map

unordered_map<K, V> is C++'s hash map.

#include <unordered_map>

unordered_map<string, int> counts;
counts["a"]++;             // creates entry if missing, initializes to 0
counts["a"] = 5;
counts["b"] = 10;

if (counts.count("a")) {
    int value = counts["a"];
}

// Or use find:
auto it = counts.find("a");
if (it != counts.end()) {
    int value = it->second;
}

One useful behavior: counts["a"]++ works even when "a" is not in the map. The bracket operator auto-creates missing entries with the value-type's default (0 for int). This is Python-like and very useful for counting patterns.

To iterate:

for (auto& [key, value] : counts) {
    cout << key << ": " << value;
}

The structured binding auto& [key, value] requires C++17. Older code uses it->first and it->second.

Unordered Set

Similar to unordered_map but stores only keys.

#include <unordered_set>

unordered_set<int> seen;
seen.insert(5);
if (seen.count(5)) {
    // present
}
seen.erase(5);

For sorted versions, use set<T> and map<K, V> (from <set> and <map> headers). They have the same API but with O(log n) operations and keep elements sorted.

Stack and Queue

stack<T> and queue<T> are container adapters built on top of deque<T>.

#include <stack>
#include <queue>

stack<int> s;
s.push(1);
s.push(2);
s.top();              // 2 (does NOT pop)
s.pop();              // removes top but does NOT return it
s.empty();

queue<int> q;
q.push(1);
q.push(2);
q.front();            // 1
q.back();             // 2
q.pop();              // removes front

The notable thing: pop() does not return the element. To both peek and remove, do s.top() then s.pop(). This trips up engineers coming from Java and Python.

Deque

deque<T> is a double-ended queue with O(1) operations at both ends. Use it for sliding window and monotonic queue problems.

#include <deque>

deque<int> dq;
dq.push_front(1);
dq.push_back(2);
dq.pop_front();
dq.pop_back();
dq.front();
dq.back();

deque also supports random-access indexing like a vector, which queue and stack do not.

Priority Queue

priority_queue<T> is C++'s heap. By default, it is a max-heap - opposite to Python and Java.

#include <queue>

priority_queue<int> maxHeap;
maxHeap.push(5);
maxHeap.push(2);
maxHeap.push(8);
maxHeap.top();        // 8
maxHeap.pop();        // remove top

For a min-heap, you have to be more verbose:

priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(5);
minHeap.push(2);
minHeap.push(8);
minHeap.top();        // 2

The template parameters are: element type, underlying container, comparator. greater<int> reverses the ordering.

For custom comparators with structs or pairs:

auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) {
    return a.first > b.first;   // min-heap by first element
};
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);

This is awkward but unavoidable. For interview code, a lambda passed to the constructor is the cleanest pattern.

Strings

C++ strings are mutable and have a rich API.

#include <string>

string s = "hello";
s.length();           // 5
s.size();             // 5 (same as length)
s[0];                 // 'h'
s.push_back('!');     // "hello!"
s.pop_back();         // "hello"
s.substr(1, 3);       // "ell" (start, length)
s.find("ll");         // 2 (npos if not found)
s.append(" world");   // "hello world"
s += " world";        // same
s.compare("hello");   // 0 if equal
reverse(s.begin(), s.end());

For conversions:

int n = stoi("42");
double d = stod("3.14");
string s = to_string(42);

For character checks (from <cctype>):

isdigit('5');         // true
isalpha('a');         // true
isalnum('a');         // true
tolower('A');         // 'a'
toupper('a');         // 'A'

Sorting

sort is in <algorithm> and uses Introsort (a hybrid of quicksort, heapsort, and insertion sort).

#include <algorithm>

vector<int> v = {3, 1, 4, 1, 5};
sort(v.begin(), v.end());                    // ascending
sort(v.begin(), v.end(), greater<int>());    // descending
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);                  // custom comparator
});

For 2D vectors:

vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}};
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
    return a[0] < b[0];
});

Note that sort takes iterators, not the container directly. This is true throughout <algorithm>.

Pairs and Tuples

pair<A, B> and tuple<A, B, C, ...> are useful when you need to bundle a couple of values without defining a class.

#include <utility>
#include <tuple>

pair<int, string> p = {42, "answer"};
p.first;
p.second;

auto [n, s] = p;      // structured binding (C++17)

tuple<int, double, string> t = {1, 2.5, "hello"};
get<0>(t);            // 1
get<1>(t);            // 2.5
auto [a, b, c] = t;   // structured binding

Pairs are widely used in graph problems where you need (node, distance) or in heap problems where you need (priority, value).

Common Idioms

A few patterns that recur in C++ interview code.

Counting with unordered_map

unordered_map<char, int> counts;
for (char c : s) {
    counts[c]++;
}

Iterating an unordered_map

for (auto& [key, value] : counts) {
    // ...
}

Sum with accumulate

#include <numeric>

int total = accumulate(v.begin(), v.end(), 0);

Max and min over a range

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

Binary search on a sorted range

bool found = binary_search(v.begin(), v.end(), target);
auto it = lower_bound(v.begin(), v.end(), target);  // first not less than
auto it2 = upper_bound(v.begin(), v.end(), target); // first greater than

lower_bound and upper_bound are essential for problems involving sorted arrays. They are O(log n) and return iterators.

Tree Node and List Node Classes

Standard interview classes look like:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

Most C++ interviews use raw pointers for these. Modern C++ would use unique_ptr or shared_ptr, but interview code rarely bothers.

Performance Tips for Interviews

A few things specific to competitive-style C++ code.

Disable iostream synchronization for fast I/O:

ios_base::sync_with_stdio(false);
cin.tie(NULL);

This is for problems with large I/O. Most interview problems do not need it, but if you are facing a strict time limit, it can help.

Reserve vector capacity when the size is known:

vector<int> v;
v.reserve(n);
for (int i = 0; i < n; i++) v.push_back(i);

Avoids the amortized cost of reallocation.

Use emplace_back instead of push_back for non-trivial types:

vector<pair<int, int>> v;
v.emplace_back(1, 2);    // constructs in place
v.push_back({1, 2});     // constructs then moves (one extra step)

For interview code, push_back is usually fine.

Common Mistakes to Avoid

Integer overflow. int is 32-bit. Computations involving products of integers up to 10^5 can overflow. Use long long when in doubt:

long long product = (long long)a * b;

Signed/unsigned comparison. v.size() returns size_t (unsigned). Comparing i < v.size() - 1 when v.size() is 0 wraps around to a huge value. Cast to int or use i + 1 < v.size() instead.

Reference vs copy. for (auto x : v) copies each element. For non-trivial types, use for (auto& x : v) to avoid the copy.

Iterator invalidation. Modifying a container while iterating over it can invalidate iterators. Either iterate by index, or collect changes and apply them after.

auto deduction. auto x = vec[0] gives you a copy, not a reference. Use auto& x if you want a reference.

Boilerplate to Remember

A minimal C++ interview template:

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

class Solution {
public:
    int solve(vector<int>& nums) {
        unordered_map<int, int> counts;
        for (int x : nums) counts[x]++;
        return 0;
    }
};

The <bits/stdc++.h> include is GCC-specific and pulls in the entire standard library. Most interview platforms support it. It saves you from remembering individual headers.

using namespace std; is controversial in production code but standard in interview code - it keeps the syntax readable.

The rest of this course uses Java for code examples. If C++ is your interview language, the algorithmic ideas transfer directly. Read the Java code as pseudocode and translate using the patterns covered here.

Back to DSA Mastery - Interview Prep, End to End