Interview Cheat Sheet

// ── vector ──────────────────────────────────────────────────
vector<int> v;
v.push_back(x);      // O(1) amortised
v.pop_back();        // O(1)
v[i];                // O(1) random access
v.size(); v.empty(); v.back(); v.front();
sort(v.begin(), v.end());                // O(n log n)
reverse(v.begin(), v.end());             // O(n)
int idx = lower_bound(v.begin(),v.end(),x) - v.begin(); // O(log n)

// ── stack ────────────────────────────────────────────────────
stack<int> stk;
stk.push(x); stk.pop(); stk.top(); stk.empty();  // all O(1)

// ── queue ────────────────────────────────────────────────────
queue<int> q;
q.push(x); q.pop(); q.front(); q.back(); q.empty();  // all O(1)

// ── deque ────────────────────────────────────────────────────
deque<int> dq;
dq.push_back(x); dq.push_front(x);   // O(1)
dq.pop_back();   dq.pop_front();      // O(1)
dq[i];                                // O(1) random access

// ── priority_queue ──────────────────────────────────────────
priority_queue<int> maxH;              // max at top
priority_queue<int,vector<int>,greater<int>> minH;  // min at top
maxH.push(x); maxH.pop(); maxH.top(); // O(log n) except top

// ── set / multiset ────────────────────────────────────────────
set<int> s;                   // sorted, unique
s.insert(x); s.erase(x); s.count(x); s.find(x);  // O(log n)
s.lower_bound(x); s.upper_bound(x);               // O(log n)

// ── map / unordered_map ───────────────────────────────────────
unordered_map<string,int> um; // O(1) avg
map<string,int> m;            // O(log n), sorted by key
um[key] = val;  um.count(key);  um.find(key);
for (auto& [k,v] : um) { }  // structured binding C++17

// ── Numeric utilities ────────────────────────────────────────
#include <numeric>
int sum = accumulate(v.begin(), v.end(), 0);
iota(v.begin(), v.end(), 0);          // fill 0,1,2,...,n-1

// ── Min/Max ──────────────────────────────────────────────────
int mx = *max_element(v.begin(), v.end());
int mn = *min_element(v.begin(), v.end());
int res = __gcd(a, b);                // GCD, O(log min(a,b))
int res = __builtin_popcount(x);      // count set bits

// ── String ───────────────────────────────────────────────────
string s = to_string(42);
int n = stoi("42");
s.substr(start, len);                 // O(len)
s.find(sub);                          // O(n*m) naive

// ── Functional / lambda ──────────────────────────────────────
sort(v.begin(), v.end(), [](int a, int b){ return a > b; }); // descending
function<int(int)> dfs = [&](int node) -> int { return 0; }; // recursive lambda

// ── Bit operations ───────────────────────────────────────────
// x & (x-1)       → clear lowest set bit (power of 2: x&(x-1)==0)
// x | (1 << k)    → set bit k
// x & ~(1 << k)   → clear bit k
// (x >> k) & 1    → check bit k
// x ^ x = 0       → XOR self = 0 (find single number)

// ── BFS from source ──────────────────────────────────────────
vector<int> dist(n, INT_MAX);
queue<int> q;
dist[src] = 0; q.push(src);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int v : adj[u]) {
        if (dist[v] == INT_MAX) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

// ── DFS iterative ────────────────────────────────────────────
vector<bool> visited(n, false);
stack<int> stk; stk.push(src);
while (!stk.empty()) {
    int u = stk.top(); stk.pop();
    if (visited[u]) continue;
    visited[u] = true;
    for (int v : adj[u]) if (!visited[v]) stk.push(v);
}

// ── Dijkstra ─────────────────────────────────────────────────
vector<long long> dist(n, LLONG_MAX);
priority_queue<pair<long long,int>,
               vector<pair<long long,int>>,
               greater<>> pq;
dist[src] = 0; pq.push({0, src});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;  // skip stale entry
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

// MISTAKE: int overflow in sum/product
int sum = 0;
for (int x : nums) sum += x; // overflows if nums has large values

// FIX: use long long
long long sum = 0;
for (int x : nums) sum += x;

// MISTAKE: mid calculation overflow
int mid = (lo + hi) / 2;   // lo+hi can overflow if both ~2^30

// FIX:
int mid = lo + (hi - lo) / 2;

// MISTAKE: multiplying two ints before assigning to long long
long long area = height * width;   // height*width computed as int first!

// FIX:
long long area = (long long)height * width;

// Binary Search variants:
while (lo <= hi)  { hi = mid - 1; lo = mid + 1; }  // exact search
while (lo < hi)   { hi = mid;     lo = mid + 1; }  // lower bound

// Array bounds: always check before accessing
if (i >= 0 && i < n && j >= 0 && j < m) grid[i][j];

// Substring length
s.substr(start, end - start + 1); // inclusive end
s.substr(start, end - start);     // exclusive end

// MISTAKE: Forgetting to check visited before pushing to BFS queue -> infinite loop
// FIX: mark visited WHEN PUSHING, not when popping
if (!visited[v]) { visited[v] = true; q.push(v); }

// Dijkstra: forgetting to skip stale heap entries
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue; // CRITICAL: skip outdated entries

// Tree: confusing null check
if (!node) return 0;             // null node contributes 0 to depth
if (!node->left && !node->right) // leaf node check

// Missing base case: dp[0] must be set before the loop
vector<int> dp(amount+1, amount+1);
dp[0] = 0; // CRITICAL base case

// 0/1 Knapsack: iterating capacity forward (allows item reuse)
for (int cap = w[i]; cap <= W; cap++) // WRONG: unbounded knapsack
for (int cap = W; cap >= w[i]; cap--) // CORRECT: 0/1 knapsack

// 2D DP string indexing: text[i-1] not text[i] when using 1-indexed dp
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;