Google New Grad OA: Prefix-Suffix Split Count and One-Value Sign Flip

Role: Software Engineer, New Grad
Result: Passed the OA
Report time: October 2025

Question 1: valid split points

Split array A after index i into non-empty left and right parts. Sort each part independently and concatenate them. Count cuts where the result is nondecreasing.

The candidate maintained prefix maxima and suffix minima. A cut is valid when the left prefix maximum is at most the right suffix minimum.

Practice: Split and Sort

Question 2: minimize absolute array sum

You may multiply at most one element by -1. Return the smallest possible absolute value of the final sum.

If the original sum is S, flipping x changes it to S - 2x. Evaluate that value for every element and retain the best result, including no flip.

Practice: Minimum Absolute Sum

The candidate described both questions as easy and said the same problems could be found in other recent candidate reports.