Binary Search Questions at Goldman Sachs: What to Expect

Binary search isn’t just about finding a number in a sorted array. At Goldman Sachs, it’s a critical tool for solving high-performance problems in finance, where data is vast and latency is low. With 30 binary search questions in their question bank, it’s clear they value candidates who can apply this O(log n) efficiency to real-world scenarios like pricing models, risk analysis, and searching through massive time-series data. Mastering it demonstrates you can optimize core operations that handle millions of data points—a daily necessity in quantitative engineering and systems roles.

What to Expect — Types of Problems

You won’t see textbook “find 5 in this array” questions. Expect applied problems that test your ability to recognize when and how to use binary search on a conceptual search space. Common patterns include:

1. Search in a Sorted but Transformed Array: Finding a target in a rotated sorted array, or in a matrix sorted row-wise and column-wise.
2. Finding Boundaries: Problems asking for the first/last occurrence, the smallest element greater than a target, or the insertion point. These test your precise loop invariant control.
3. Binary Search on Answer (or “Guessing Game”): The most frequent and tricky type. Here, the array isn’t given. You use binary search to guess the answer within a feasible range and check if it’s valid. Classic examples include: “Allocate minimum number of pages” or “Find the smallest divisor to meet a threshold.”
4. Simulating a Process: Using binary search to optimize a multi-step process, like minimizing the maximum time or cost of a repetitive operation.

How to Prepare — Study Tips with One Code Example

Focus on the underlying pattern, not memorization. Internalize the standard binary search algorithm first, then practice its variants. Always define your search space (low, high) and your condition function that tells you whether to go left or right. The hardest part is avoiding off-by-one errors; choose one loop style (e.g., while low <= high) and stick with it.

A key pattern is “Finding the First True in a Sorted Boolean Array.” This models all “find first/last” problems. Imagine a function isValid(guess) that returns True for all guesses from some point onward. Your task is to find the smallest guess where it becomes true.

def first_true(condition, low, high):
    """Finds the smallest x in [low, high] where condition(x) is True."""
    while low < high:
        mid = low + (high - low) // 2
        if condition(mid):
            high = mid  # Search left, including mid (it's a candidate)
        else:
            low = mid + 1  # Search right, mid is not valid
    return low  # low == high, the first true index

This template is directly applicable to problems like “Find the first bad version” or “Find the smallest sufficient capacity.”

Recommended Practice Order

Build competence progressively:

1. Foundation: Standard binary search and its boundary variants (first/last position).
2. Rotation & Matrices: Search in rotated sorted array, search a 2D matrix.
3. Binary Search on Answer: Start with straightforward applications (square root, guess number) before moving to complex minimization problems (split array largest sum, minimum capacity to ship packages).
4. Goldman Sachs-Specific: Finally, tackle tagged problems from their question bank to familiarize yourself with their phrasing and difficulty.

Practice Binary Search at Goldman Sachs