---
title: "C++ Fundamentals for DSA Interviews — 2026 Edition"
description: "C++ Fundamentals for DSA Interviews — 2026 Edition. One stop syntax reference for FAANG / product based / startup interviews."
url: https://sohamdev.com/blog/c-fundamentals-for-dsa-interviews-2026-edition/
date: 2026-09-10
updated: 2026-09-10
author: "Soham Roy"
topic: "Engineering"
tags: ["C++", "DSA", "Software Engineering", "FAANG", "MANNG", "Google", "Amazon", "Algorithms", "Students", "Job Hunters", "Problem Solving"]
reading_minutes: 19
word_count: 2026
canonical: https://sohamdev.com/blog/c-fundamentals-for-dsa-interviews-2026-edition/
license: "All rights reserved. Quotation with attribution and a link is welcome."
---

# C++ Fundamentals for DSA Interviews — 2026 Edition

# 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](#1-core-basics)
2. [Functions & Parameter Passing](#2-functions--parameter-passing)
3. [Pointers & References](#3-pointers--references)
4. [Arrays, Vectors & Strings](#4-arrays-vectors--strings)
5. [Classes, Structs & OOP](#5-classes-structs--oop)
6. [STL Containers (Deep Dive)](#6-stl-containers-deep-dive)
7. [Iterators](#7-iterators)
8. [STL Algorithms](#8-stl-algorithms)
9. [Lambda Functions](#9-lambda-functions)
10. [auto, decltype & Structured Bindings](#10-auto-decltype--structured-bindings)
11. [Templates](#11-templates)
12. [Bit Manipulation](#12-bit-manipulation)
13. [DSA-Specific Idioms & Boilerplate](#13-dsa-specific-idioms--boilerplate)
14. [STL Time Complexity Cheat Sheet](#14-stl-time-complexity-cheat-sheet)
15. [Common Gotchas & Interview Traps](#15-common-gotchas--interview-traps)

---

## 1. Core Basics

### Data Types & Sizes
```cpp
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
```cpp
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
```cpp
// 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
```cpp
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)
```cpp
#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

```cpp
// 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
```cpp
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

```cpp
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
```cpp
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
```cpp
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
```cpp
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
```cpp
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
```cpp
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
```cpp
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`
```cpp
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
```cpp
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)
```cpp
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
```cpp
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)
```cpp
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
```cpp
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
```cpp
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
```cpp
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
```cpp
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
```cpp
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)
```cpp
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
```cpp
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
```cpp
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
```cpp
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
```cpp
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

```cpp
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)*

```cpp
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

```cpp
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

```cpp
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

```cpp
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

```cpp
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

```cpp
#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:
   ```cpp
   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.).*