CITADEL SDE OA ( US ) - kinda different

Discussion: From Messy C++ Starter Code to Clean O(n) — My Refactor Journey

So I was taking a coding test the other day, and instead of the usual “write a function from scratch,” they gave me something different:

“Here’s a working C++ function. It’s correct but very slow. Refactor and speed it up.”

I thought, okay… sounds fun, how bad can it be?
Well… then I opened the code.

First Impressions

The function looked like spaghetti. Some highlights:

• It started with int leaf = numeric_limits<int>::max(); // Initialize to minimum value (already suspicious).

• It used std::find_if inside every loop iteration, meaning nested rescans.

• There was std::pow(x, 2) everywhere just to square an int.

• And my favorite: a random bit-hack with

  ((unsigned int)(vertex - edge)) >> numeric_limits<int>::digits

  which was basically a complicated way to check if one number is bigger than another.

• To top it off, there was this strange lambda:

  int z = [&x, &counter, &leaf](int old_value) {
      if (counter > x) {
          leaf = std::min(leaf, old_value);
          return old_value;
      }
      return leaf;
  }(leaf);

  which, after reading 3 times, I realized did absolutely nothing.

So yeah — it was passing small inputs, but anything large would crawl. Classic O(n²) vibes.

Digging for the Core Logic

I asked myself: what is this code actually doing beneath the mess?

After stripping out the noise, here’s the essence:

• For each element a[i], look at later elements a[j].
• If a[j] >= a[i], compute (a[j] - a[i])².
• Keep the largest such squared difference.
• At the end, if that result is a perfect square, return its sqrt; else return the number itself.

So the real problem was:
“Find the max squared difference between an element and any larger element to its right.”

The Aha Moment

At first, I was still stuck in brute force thinking — I even tried cleaning up find_if with an unordered_map to reduce some overhead. It helped a little but was still slow.

Then it hit me: why am I checking every single element to the right?

For each index i, the only one that matters is the largest value in the suffix [i..n-1].
Because bigger a[j] → bigger difference → bigger square.
Boom. That cuts out all the wasted comparisons.

The Refactor

I rewrote the messy nested loop into two clean passes:

1. Build a suffixMax array in one right-to-left scan:

   suffixMax[i] = max(output[i], suffixMax[i+1]);

2. Loop again left-to-right: for each i, check (suffixMax[i] - output[i])².

3. Track the largest, and finally check if it’s a perfect square.

No lambdas, no pow, no iterator circus. Just straight math.

Complexity

• Old code: O(n²) with confusing extras.
• Refactor: O(n) time, O(n) space.
• Same results, but lightning fast.

Takeaways (My Thought Process)

• At first, I almost got lost trying to “fix” the given code line by line. That was a trap.
• The better approach was: forget the noise, figure out the core intention.
• Once I realized the problem was just “find max distance with a bigger right-side element,” the suffix max trick became obvious.
• Sometimes optimization is less about micro-tweaks (pow → *) and more about a new perspective (nested loop → suffix max).

Open Question

This was one of the more interesting “refactor” problems I’ve seen in a test.
Has anyone else gotten problems where the main challenge was to untangle messy code instead of writing from scratch?

Would love to hear other people’s stories.

That’s my little journey. Hopefully it helps if you ever bump into a test with spaghetti starter code.