Citadel Software Engineer Interview Experience — Optimizing a Correct C++ Function to Run Under 100 Microseconds

The assessment provided C++ source code for a root_node function. Its logic was correct, but it ran extremely slowly. The task was to refactor and optimize it so that it would finish in strictly less than 100 microseconds on large inputs.

The original code contained nested loops and operations such as std::find_if and std::advance, producing O(N²) complexity. I needed to reduce that to O(N).

It also used std::pow for squaring, complicated bit-shift operations, and mathematical functions such as std::sqrt. These needed equivalent mathematical derivations and faster replacements.

The optimized code still had to be logically identical to the original. It also needed to avoid unnecessary memory copies, for example by passing a vector as const vector<int>&.