← Writing

Engineering10 Sept 202619 min read

C++ Fundamentals for DSA Interviews — 2026 Edition

C++ Fundamentals for DSA Interviews — 2026 Edition. One stop syntax reference for FAANG / product based / startup interviews.

  • C++
  • DSA
  • Software Engineering
  • FAANG
  • MANNG
  • Google
  • Amazon
  • Algorithms
  • Students
  • Job Hunters
  • Problem Solving

C++ Fundamentals for DSA Interviews — 2026 Revision Sheet

One-stop syntax reference for FAANG / product-based / startup interviews. Every section has: syntax, why it's written that way, and DSA-relevant usage.

#Table of Contents

  1. Core Basics
  2. Functions & Parameter Passing
  3. Pointers & References
  4. Arrays, Vectors & Strings
  5. Classes, Structs & OOP
  6. STL Containers (Deep Dive)
  7. Iterators
  8. STL Algorithms
  9. Lambda Functions
  10. auto, decltype & Structured Bindings
  11. Templates
  12. Bit Manipulation
  13. DSA-Specific Idioms & Boilerplate
  14. STL Time Complexity Cheat Sheet
  15. Common Gotchas & Interview Traps

#1. Core Basics

#Data Types & Sizes

cpp7 lines
int a;              // 4 bytes, ~ -2.1B to 2.1B  → overflows fast, watch for this
long long b;         // 8 bytes, ~ -9.2 * 10^18   → default choice for sums/products in DSA
unsigned int c;       // 4 bytes, 0 to ~4.2B      → careful, no negative values (underflow wraps!)
float d;              // 4 bytes, ~7 decimal digits precision
double e;              // 8 bytes, ~15 decimal digits precision → default for floating math
char f;                 // 1 byte, single character
bool g;                  // 1 byte, true/false

Why long long by default in DSA: interview inputs like 1e9 * 1e9 silently overflow int (max ~2.1 * 10^9) and give wrong answers with no crash — the classic silent-bug trap.

#Constants & Type Casting

cpp6 lines
const int N = 100;              // compile-time constant, cannot be reassigned
#define MOD 1000000007          // macro constant (older style, still common in DSA)

int x = 10;
double y = (double)x / 3;       // explicit C-style cast
double z = static_cast<double>(x) / 3;  // preferred modern cast — type-checked at compile time

Why static_cast over C-style cast: the compiler validates the conversion is sane; C-style cast will silently force any conversion (even unsafe ones) and hide bugs.

#Operators

cpp9 lines
// Arithmetic: + - * / %  (% only works on integers)
// Relational: == != < > <= >=
// Logical:    && || !
// Bitwise:    & | ^ ~ << >>
// Ternary:    condition ? valueIfTrue : valueIfFalse
int max_val = (a > b) ? a : b;

// Compound assignment
a += 5; a -= 5; a *= 2; a /= 2; a %= 3;

#Control Flow

cpp18 lines
if (x > 0) { /* ... */ }
else if (x == 0) { /* ... */ }
else { /* ... */ }

switch (x) {
    case 1: /* ... */ break;
    case 2: /* ... */ break;
    default: /* ... */
}

for (int i = 0; i < n; i++) { /* ... */ }
while (condition) { /* ... */ }
do { /* ... */ } while (condition);

// Range-based for (C++11) — cleaner iteration, no index management
for (int val : vec) { /* val is a COPY */ }
for (int &val : vec) { /* val is a REFERENCE — modifies original */ }
for (const auto &val : vec) { /* read-only, no copy — best for large objects */ }

Why const auto & in loops: avoids copying each element (expensive for strings/vectors) while also preventing accidental modification — the safest and fastest default.

#Fast I/O (important for large inputs in competitive-style rounds)

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

int main() {
    ios_base::sync_with_stdio(false);  // detach C++ streams from C stdio
    cin.tie(NULL);                     // untie cin from cout auto-flush
    // now cin/cout run much faster on large inputs
}

Why this matters: by default, cin/cout sync with C's scanf/printf for mixed-code safety — this sync has overhead. Disabling it can turn a TLE (Time Limit Exceeded) into a pass.

#2. Functions & Parameter Passing

cpp22 lines
// Pass by VALUE — function gets a COPY, original untouched
int square(int x) { return x * x; }

// Pass by REFERENCE — function operates on the ORIGINAL variable, no copy made
void doubleIt(int &x) { x *= 2; }

// Pass by CONST REFERENCE — no copy (efficient for large objects) but read-only (safe)
int sumVec(const vector<int> &v) {
    int s = 0;
    for (int x : v) s += x;
    return s;
}

// Pass by POINTER — old-C style, explicit address passing
void doubleIt(int *x) { *x *= 2; }

// Default arguments
int power(int base, int exp = 2) { /* ... */ }

// Function overloading — same name, different parameter signatures
int add(int a, int b) { return a + b; }
double add(double a, double b) { return a + b; }

Why const vector<int>& is the DSA default for function params: passing a vector by value copies the entire array (O(n) time + space) every call. Passing by reference avoids the copy; adding const guarantees the function can't accidentally mutate the caller's data — you get speed and safety together. This single habit is one of the most-checked things in interviews.

#Recursion Essentials

cpp4 lines
int factorial(int n) {
    if (n <= 1) return 1;        // BASE CASE — always define first, prevents stack overflow
    return n * factorial(n - 1); // RECURSIVE CASE
}

Every recursive function needs: (1) a base case, (2) a case that moves toward the base case. Default C++ stack depth is usually ~10,000-100,000 frames — deep recursion (e.g., on 10^6 array) can cause a stack overflow; prefer iteration or increase recursion limit awareness in such cases.

#3. Pointers & References

cpp7 lines
int x = 10;
int *p = &x;      // p stores the ADDRESS of x
cout << *p;       // * dereferences — gives the VALUE at that address (10)
*p = 20;          // modifies x through the pointer → x is now 20

int &ref = x;     // ref is an ALIAS for x — not a new variable, same memory
ref = 30;         // this changes x directly, x is now 30

#Pointer vs Reference — comparison

Feature Pointer Reference
Can be NULL Yes (nullptr) No, must bind to real variable
Can be reassigned Yes (point elsewhere) No, bound forever to first variable
Needs dereference (*) Yes No, acts like the variable itself
Use case Optional/nullable data, dynamic structures Function params, avoiding copies

#Pointers to Arrays / Double Pointers

cpp5 lines
int arr[5] = {1,2,3,4,5};
int *p = arr;          // array name decays to pointer to first element
cout << *(p + 2);      // same as arr[2] — pointer arithmetic

int **pp;               // pointer to pointer — used for 2D dynamic arrays, tree-of-pointers structures

#Dynamic Memory

cpp11 lines
int *p = new int(5);        // heap-allocate a single int, initialized to 5
delete p;                    // MUST free manually or it leaks

int *arr = new int[n];       // heap-allocate array of size n
delete[] arr;                // must use [] to match array allocation

// Modern preferred way — smart pointers (auto-cleanup, rarely needed in plain DSA solving
// but good to know for system-design / production-style questions)
#include <memory>
unique_ptr<int> up = make_unique<int>(5);   // auto-deleted when it goes out of scope
shared_ptr<int> sp = make_shared<int>(5);   // reference-counted, auto-deleted when count hits 0

Why smart pointers exist: manual new/delete is a common source of memory leaks and dangling pointers. unique_ptr and shared_ptr tie the object's lifetime to scope automatically (RAII principle — Resource Acquisition Is Initialization).

#4. Arrays, Vectors & Strings

#C-style Arrays

cpp3 lines
int arr[5] = {1, 2, 3, 4, 5};   // fixed size, on the stack, size known at compile time
int arr2[5] = {0};              // all zero-initialized
int grid[3][4];                 // 2D array — fixed dimensions

Limitation: size is fixed at compile time and arrays don't know their own size — this is exactly why vector is preferred in interviews (dynamic, carries .size(), safer).

#std::vector — the DSA workhorse

cpp19 lines
vector<int> v;                  // empty, dynamic array
vector<int> v(5);               // size 5, all zero-initialized
vector<int> v(5, 10);           // size 5, all initialized to 10
vector<int> v = {1, 2, 3};      // initializer-list construction

v.push_back(4);      // append at end — amortized O(1)
v.pop_back();         // remove last — O(1)
v.size();              // number of elements
v.empty();              // true if size == 0
v[i];                    // access — NO bounds checking (fast but unsafe)
v.at(i);                  // access WITH bounds checking (throws exception if out of range)
v.front(); v.back();       // first / last element
v.clear();                  // remove all elements
v.resize(10);                 // grow/shrink, new elements zero-init
v.insert(v.begin() + 2, 99);   // insert 99 at index 2 — O(n), shifts elements
v.erase(v.begin() + 2);         // remove element at index 2 — O(n)

// 2D vector — the standard DSA pattern for grids/DP tables
vector<vector<int>> grid(rows, vector<int>(cols, 0));

Why vector over array in interviews: dynamic resizing, bounds-checkable access via .at(), knows its own size, and integrates directly with STL algorithms (sort, begin()/end(), etc.) — arrays require manually tracking size and don't work cleanly with most STL functions.

#std::string

cpp22 lines
string s = "hello";
s.length(); s.size();          // same thing, length of string
s += " world";                  // concatenation
s.substr(1, 3);                  // substring starting at index 1, length 3 → "ell"
s.find("lo");                     // returns index of first match, or string::npos if not found
s[i];                               // character access
s.push_back('!');                    // append one char
s.pop_back();                         // remove last char
reverse(s.begin(), s.end());           // in-place reversal (needs <algorithm>)
sort(s.begin(), s.end());               // sort characters
s.compare(other);                        // 0 if equal, <0 if less, >0 if greater

// Conversions
int n = stoi("123");              // string → int
long long n2 = stoll("123456789012");  // string → long long
double d = stod("3.14");           // string → double
string s2 = to_string(456);         // number → string

// Building strings efficiently (avoids repeated concatenation cost)
stringstream ss;
ss << "x=" << 5 << " y=" << 10;
string result = ss.str();

Why s.find() == string::npos (not == -1): string::npos is defined as the maximum value of size_t (unsigned) — comparing against -1 directly can misbehave due to signed/unsigned mismatch. Always compare against string::npos.

#5. Classes, Structs & OOP

#struct vs class

cpp8 lines
struct Point {          // members PUBLIC by default
    int x, y;
};

class Point {            // members PRIVATE by default
public:
    int x, y;
};

Why this distinction exists historically: struct came from C, meant for plain data grouping (public by default). class was introduced for full OOP with encapsulation (private by default, forces deliberate use of public:). In DSA, struct is used for simple data bundles (like a graph node); class is used when you want encapsulation (e.g., a Stack implementation hiding its internal array).

#Constructors, Destructor, this

cpp15 lines
class Node {
public:
    int val;
    Node* next;

    Node() : val(0), next(nullptr) {}              // default constructor (member init list)
    Node(int v) : val(v), next(nullptr) {}           // parameterized constructor
    Node(int v, Node* n) : val(v), next(n) {}         // another overload

    ~Node() { /* cleanup, rarely needed if no manual `new` inside */ }  // destructor
};

Node n1;             // calls Node()
Node n2(5);            // calls Node(int)
Node* n3 = new Node(5); // heap allocation, must delete later

Why member initializer lists (: val(v), next(nullptr)) over assignment in the body: they directly construct members with the given value instead of default-constructing then reassigning — more efficient, and it's the only way to initialize const members or reference members.

#Access Specifiers

cpp10 lines
class Stack {
private:
    vector<int> data;          // hidden internal state — "properties"

public:
    void push(int x) { data.push_back(x); }     // public interface
    void pop() { data.pop_back(); }
    int top() { return data.back(); }
    bool empty() { return data.empty(); }
};

private = accessible only inside the class. protected = accessible in class + derived classes. public = accessible everywhere. This is encapsulation — hiding internal representation so the caller only interacts through a controlled interface.

#Operator Overloading (very commonly needed in DSA)

cpp11 lines
struct Point {
    int x, y;
    // needed so Point can be used as a key in set/map, or sorted directly
    bool operator<(const Point &other) const {
        if (x != other.x) return x < other.x;
        return y < other.y;
    }
    bool operator==(const Point &other) const {
        return x == other.x && y == other.y;
    }
};

Why you need operator< for custom types: STL containers like set, map, and sort()/priority_queue rely on < to order elements. Without defining it, the compiler has no idea how to compare your custom struct, and code won't compile.

#Static Members

cpp6 lines
class Counter {
public:
    static int count;              // shared across ALL instances, not per-object
    Counter() { count++; }
};
int Counter::count = 0;             // must define outside the class

#Inheritance & Virtual Functions (occasionally asked, mostly for LLD/OOP-design rounds)

cpp12 lines
class Animal {
public:
    virtual void speak() { cout << "..."; }   // virtual → enables runtime polymorphism
    virtual ~Animal() {}                        // virtual destructor — always add if class has virtual funcs
};
class Dog : public Animal {
public:
    void speak() override { cout << "Woof"; }    // override — clearer intent, compiler-checked
};

Animal* a = new Dog();
a->speak();   // prints "Woof" — resolved at RUNTIME because speak() is virtual (dynamic dispatch)

Why virtual matters: without it, a->speak() would call Animal::speak() (resolved at compile time based on the pointer type, not the actual object) — this is "static binding". virtual forces "dynamic binding" so the actual object's method runs. This is the mechanism behind polymorphism.

#6. STL Containers (Deep Dive)

#pair & tuple

cpp5 lines
pair<int, int> p = {1, 2};
p.first; p.second;               // access

tuple<int, string, double> t = {1, "hi", 3.14};
get<0>(t); get<1>(t); get<2>(t);  // access by index (compile-time)

Used constantly for coordinates (row, col), (value, index) pairs for sorting-with-tracking, edges (node, weight) in graphs.

#vector — dynamic array (see Section 4)

Best for: general-purpose dynamic list, DP tables, adjacency lists.

#deque — double-ended queue

cpp4 lines
deque<int> dq;
dq.push_back(1); dq.push_front(2);   // O(1) at BOTH ends (vector is O(1) only at back)
dq.pop_back(); dq.pop_front();
dq[i];                                 // random access supported, O(1)

Used for: sliding window problems (monotonic deque), BFS-like scenarios needing both-end access.

#stack — LIFO

cpp2 lines
stack<int> st;
st.push(1); st.pop(); st.top(); st.empty(); st.size();

Used for: parentheses matching, DFS (iterative), monotonic stack (next greater element), expression evaluation.

#queue — FIFO

cpp2 lines
queue<int> q;
q.push(1); q.pop(); q.front(); q.back(); q.empty(); q.size();

Used for: BFS traversal, level-order tree traversal.

#priority_queue — heap

cpp12 lines
priority_queue<int> maxHeap;                              // max-heap by DEFAULT
maxHeap.push(5); maxHeap.top(); maxHeap.pop();

priority_queue<int, vector<int>, greater<int>> minHeap;    // min-heap — flip comparator

// Custom comparator for complex types (e.g., pairs, or Dijkstra's {dist, node})
struct Compare {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        return a.first > b.first;    // smaller first = higher priority → min-heap on .first
    }
};
priority_queue<pair<int,int>, vector<pair<int,int>>, Compare> pq;

Why greater<int> flips it to a min-heap: priority_queue internally keeps the "largest" element (by whatever comparator is given) at the top. Its default comparator is less<int> which places the numerically largest at top. Swapping to greater<int> inverts the ordering logic, so the numerically smallest ends up "largest" by the comparator's logic → sits at top. Used heavily in Dijkstra's algorithm, k-way merge, top-K problems.

#set / multiset — ordered, balanced BST (Red-Black Tree internally)

cpp8 lines
set<int> s;
s.insert(5); s.erase(5);
s.find(5);                     // returns iterator, or s.end() if not found
s.count(5);                    // 0 or 1 (multiset can return >1)
auto it = s.lower_bound(5);     // first element >= 5
auto it2 = s.upper_bound(5);     // first element > 5
*s.begin();                       // smallest element
*s.rbegin();                       // largest element

Why set keeps elements sorted automatically: it's backed by a self-balancing binary search tree, so insert/erase/find are all O(log n), and in-order traversal is always sorted. This makes lower_bound/upper_bound (binary search) natively O(log n) — unlike a vector where you'd need to sort first.

#map / multimap — ordered key-value store

cpp8 lines
map<string, int> m;
m["apple"] = 5;              // insert or update
m.insert({"banana", 3});
m.erase("apple");
m.find("apple");                // returns iterator, m.end() if missing
m.count("apple");                 // 0 or 1

for (auto &[key, val] : m) { /* iterates in SORTED key order */ }

Why m["key"] is risky for existence checks: accessing a non-existent key with [] auto-creates it with a default value (0 for int) — this silently inserts unwanted entries. Use m.find(key) != m.end() or m.count(key) to check existence without side effects.

#unordered_set / unordered_map — hash table

cpp6 lines
unordered_set<int> us;
us.insert(5); us.count(5); us.erase(5);      // average O(1)!

unordered_map<int, int> um;
um[5] = 10;                                     // average O(1) insert/access
um.find(5) != um.end();                          // existence check

Why prefer unordered_map over map in most DSA problems: average O(1) vs O(log n) per operation — a huge speed win when order doesn't matter (e.g., frequency counting, two-sum). Use map/set only when you specifically need sorted order or guaranteed worst-case O(log n) (hash collisions can degrade unordered_* to O(n) worst case, rare but real).

#list — doubly linked list

cpp3 lines
list<int> l;
l.push_back(1); l.push_front(2);
l.insert(it, 5);       // O(1) insert if you already have the iterator (no shifting, unlike vector)

Rarely needed directly in interviews (you usually build your own linked list with struct Node), but useful to know it exists for O(1) insert/delete anywhere given an iterator.

#bitset — fixed-size bit array

cpp4 lines
bitset<32> b(13);            // 13 in binary, 32 bits wide
b.count();                    // number of set bits
b.set(2); b.reset(2); b.flip(2);
b.to_string();

Used for: bitmask DP, subset enumeration, space-efficient boolean arrays.

#7. Iterators

cpp9 lines
vector<int> v = {1, 2, 3};
vector<int>::iterator it = v.begin();    // points to first element
it++;                                       // move to next
*it;                                          // dereference — get value
v.end();                                        // one PAST the last element (not valid to dereference)

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

v.rbegin(); v.rend();       // reverse iterators — begin at the back, end before the front

Why end() points one-past-the-last: this makes loop conditions clean (it != v.end()) and empty ranges naturally valid (begin() == end()) — a design convention used consistently across all STL containers.

#8. STL Algorithms

(all require #include <algorithm>, most work on any container via iterators)

cpp31 lines
sort(v.begin(), v.end());                          // ascending, O(n log n)
sort(v.begin(), v.end(), greater<int>());            // descending
sort(v.begin(), v.end(), [](int a, int b){            // custom comparator via lambda
    return a > b;
});

reverse(v.begin(), v.end());                             // in-place reverse

int mx = *max_element(v.begin(), v.end());                 // largest value
int mn = *min_element(v.begin(), v.end());                   // smallest value

int total = accumulate(v.begin(), v.end(), 0);                 // sum, starting from 0

// binary search — REQUIRES sorted range
bool found = binary_search(v.begin(), v.end(), 5);
auto it = lower_bound(v.begin(), v.end(), 5);   // first element >= 5
auto it2 = upper_bound(v.begin(), v.end(), 5);   // first element > 5

auto newEnd = unique(v.begin(), v.end());          // removes CONSECUTIVE duplicates (sort first!)
v.erase(newEnd, v.end());                            // actually shrink the vector

next_permutation(v.begin(), v.end());                  // rearranges to next lexicographic permutation
prev_permutation(v.begin(), v.end());

int c = count(v.begin(), v.end(), 5);                    // count occurrences of 5
auto it3 = find(v.begin(), v.end(), 5);                    // find first occurrence, v.end() if absent

swap(a, b);                                                 // swap two variables/containers

__builtin_popcount(x);        // count set bits in int (GCC-specific, very handy for bit DP)
__builtin_clz(x);              // count leading zeros

Why lower_bound/upper_bound need a sorted range: they perform binary search internally (O(log n)) — on unsorted data the result is undefined/meaningless. This is the most common silent bug when using them.

#9. Lambda Functions

cpp14 lines
auto add = [](int a, int b) { return a + b; };
cout << add(2, 3);          // 5

// Capture clause controls what outer-scope variables the lambda can access
int threshold = 10;
auto isAbove = [threshold](int x) { return x > threshold; };     // capture by VALUE (copy)
auto isAboveRef = [&threshold](int x) { return x > threshold; };   // capture by REFERENCE
auto captureAll = [=](int x) { return x > threshold; };              // capture ALL by value
auto captureAllRef = [&](int x) { return x > threshold; };             // capture ALL by reference

// Most common DSA use: inline custom comparator
sort(v.begin(), v.end(), [](const pair<int,int> &a, const pair<int,int> &b) {
    return a.second < b.second;     // sort pairs by second element
});

Why lambdas are preferred over separate comparator functions in interviews: they're defined inline exactly where used, keeping related logic together and avoiding cluttering the file with tiny named functions used only once — cleaner and faster to write under interview time pressure.

#10. auto, decltype & Structured Bindings

cpp11 lines
auto x = 5;                  // compiler infers int
auto v = vector<int>{1,2,3};   // compiler infers vector<int>
auto it = v.begin();             // compiler infers the (long) iterator type — huge readability win

// Structured bindings (C++17) — unpack pairs/tuples directly into named variables
pair<int, int> p = {1, 2};
auto [a, b] = p;                  // a = 1, b = 2

for (auto &[key, val] : myMap) {    // very common idiom for iterating maps cleanly
    cout << key << " " << val;
}

Why auto matters for STL-heavy code: iterator types like unordered_map<string, vector<int>>::iterator are long and error-prone to type manually — auto lets the compiler deduce it exactly, eliminating a whole class of typos.

#11. Templates

cpp6 lines
template <typename T>
T maxOf(T a, T b) {
    return (a > b) ? a : b;
}
maxOf<int>(3, 5);        // works for int
maxOf<double>(3.1, 5.2);  // and double, and any type supporting >

Why templates matter conceptually: this is how the STL itself is built — vector<int>, vector<string> etc. are all instantiations of one generic template. Rarely need to write your own templates in interviews, but understanding this explains why STL containers work with any type.

#12. Bit Manipulation

cpp14 lines
a & b     // AND — 1 only if both bits are 1
a | b     // OR — 1 if either bit is 1
a ^ b     // XOR — 1 if bits differ (self-inverse: a^a=0, a^0=a)
~a        // NOT — flips all bits
a << k    // left shift — multiply by 2^k
a >> k    // right shift — divide by 2^k (integer division)

// Common patterns
bool isSet   = (n >> i) & 1;         // check if bit i is set
int  setBit  = n | (1 << i);           // set bit i to 1
int  clearBit= n & ~(1 << i);            // clear bit i to 0
int  toggle  = n ^ (1 << i);               // flip bit i
bool isPow2  = n > 0 && (n & (n - 1)) == 0;  // power-of-2 check — n&(n-1) clears lowest set bit
int  countSetBits = __builtin_popcount(n);      // number of 1s

Why n & (n-1) clears the lowest set bit: subtracting 1 flips all bits after (and including) the lowest set bit; ANDing with the original cancels that bit out while leaving higher bits unchanged. This single trick powers power-of-2 checks, Brian Kernighan's bit-counting algorithm, and several bitmask-DP optimizations.

#13. DSA-Specific Idioms & Boilerplate

cpp30 lines
#include <bits/stdc++.h>     // pulls in ALL standard headers — standard practice in DSA/competitive
using namespace std;           // avoids typing std:: everywhere (fine for interviews, avoided in production)

// Common limits
INT_MAX; INT_MIN;               // <climits> — int bounds
LLONG_MAX; LLONG_MIN;             // long long bounds
const int MOD = 1e9 + 7;            // common modulus for "return answer % 1e9+7" problems

// memset for quick array fill (only safe for 0, -1, or byte-repeating patterns!)
int arr[100];
memset(arr, 0, sizeof(arr));         // zero-fill — fast, common for visited[] arrays
memset(arr, -1, sizeof(arr));          // fill with -1 — WORKS because -1 is all 1-bits in every byte
// memset(arr, 5, sizeof(arr));  <-- DO NOT use for arbitrary values, it fills byte-by-byte, not int-by-int

// 2D DP table initialization
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

// visited array for graph traversal
vector<bool> visited(n, false);

// adjacency list for graphs
vector<vector<int>> adj(n);
adj[u].push_back(v);
adj[v].push_back(u);   // if undirected

// custom sort with multiple keys
sort(v.begin(), v.end(), [](const auto &a, const auto &b) {
    if (a.first != b.first) return a.first < b.first;
    return a.second < b.second;
});

Why #include <bits/stdc++.h> is fine in interviews but not production: it's a GCC-specific umbrella header pulling in the entire standard library — convenient for speed under interview time pressure, but slows compilation and isn't portable to all compilers (e.g., MSVC/Clang don't guarantee it), so real codebases include only what's needed.

#14. STL Time Complexity Cheat Sheet

Container / Op Access Search Insert Delete
vector (end) O(1) O(n) O(1) amortized O(1)
vector (middle) O(1) O(n) O(n) O(n)
deque (both ends) O(1) O(n) O(1) O(1)
stack / queue O(1) top/front — O(1) O(1)
set / map — O(log n) O(log n) O(log n)
unordered_set/map — O(1) avg, O(n) worst O(1) avg O(1) avg
priority_queue O(1) top — O(log n) O(log n)
list O(n) O(n) O(1)* O(1)*

*with iterator already in hand; finding the position is still O(n).

Algorithm Complexity
sort() O(n log n)
binary_search/lower_bound/upper_bound O(log n) — sorted input required
find() (linear scan) O(n)
max_element/min_element/accumulate O(n)
next_permutation O(n) per call

#15. Common Gotchas & Interview Traps

  1. Integer overflow — int * int can overflow even if the result fits in long long. Cast one operand: (long long)a * b.
  2. vector out-of-bounds via [] — undefined behavior, not always a crash (may silently read garbage). Use .at() while debugging, [] for speed once verified correct.
  3. Modifying a container while iterating it — invalidates iterators (especially vector, map/set erase). Use the iterator returned by erase() to continue safely:
    cpp4 lines
    for (auto it = v.begin(); it != v.end(); ) {
    if (shouldRemove(*it)) it = v.erase(it);   // erase returns next valid iterator
    else ++it;
}
  4. map[key] auto-inserts — checking existence with [] silently creates a default entry. Use .find() or .count().
  5. Negative modulo — in C++, -7 % 3 == -1 (not 2 like in Python). For DSA problems expecting a non-negative result: ((a % m) + m) % m.
  6. Comparing signed and unsigned — s.find() == -1 never true because find() returns unsigned size_t; always compare to string::npos.
  7. Passing large containers by value — silently copies the whole structure every call; default to const & unless you intend to copy.
  8. Uninitialized local variables — C-style arrays and primitive locals are not zero-initialized by default; garbage values cause nondeterministic bugs. Always initialize explicitly (int x = 0;, vector<int> v(n, 0);).
  9. Recursion depth — deep recursion (e.g., DFS on a skewed tree of 10^5 nodes) can stack overflow; consider converting to iterative with an explicit stack for very large inputs.
  10. Floating-point equality — never use == on doubles; compare with a small epsilon: abs(a - b) < 1e-9.

Keep this file open alongside your LeetCode 150 tracker — most patterns above map directly onto the problem categories in your study plan (hash maps → HashMap section, heaps → priority_queue, graphs → adjacency lists + BFS/DFS boilerplate, etc.).

Share X LinkedIn

More on Engineering