Production checklist for DSA

Production code rarely reimplements red-black trees—use STL—but algorithmic choices still matter for latency, memory, and correctness at scale before AI training jobs.

Before shipping hot paths

• Profile first—avoid optimizing cold code
• Pick right container (vector vs map vs unordered_map)
• Watch hidden O(n) inserts and string copies
• Set limits on recursion depth; prefer iterative BFS/DFS in servers
• Unit test boundary inputs and worst-case sizes
• Document time/space expectations in API comments

STL in production

Prefer std::sort, std::lower_bound, std::unordered_map over hand-rolled structures unless profiling proves need.

Sanity benchmark sketch

#include 
#include 
#include 
#include 

int main() {
    std::vector v(100000, 1);
    auto t0 = std::chrono::steady_clock::now();
    long long s = 0;
    for (int x : v) s += x;
    auto t1 = std::chrono::steady_clock::now();
    auto ms = std::chrono::duration_cast(t1 - t0).count();
    std::cout << "sum=" << s << " ms=" << ms << "\n";
    return 0;
}

Important interview questions and answers

1. Q: When hand-roll DSU?
   A: When library lacks union-find—otherwise encapsulate tested DSU class with path compression.
2. Q: vector reserve?
   A: Call reserve(n) when size known—avoids repeated reallocations.

Self-check

1. List five production DSA checklist items.
2. Why profile before replacing STL sort?

Tip: Call reserve on vectors when final size known—cheap win in hot loops.