Bloomberg VO Interview Question: Implement Ship Counting with hasShips

You are working on a project that has to implement a new ship-discovering technology.

You are provided with the function:

struct Point {
    const int x;
    const int y;
    Point(int x, int y) : x_(x), y_(y) {}};

bool hasShips(const Point& bottom_left, const Point& top_right);
// Returns true if there are 1 or more ships within the area with corners bottom_left and top_right.
// Returns false if there are no ships within the area.

Using the hasShips function, implement the function:

int countShips(const Point& bottom_left, const Point& top_right);
// Returns the number of ships there are within the area with corners bottom_left and top_right

Sample inputs – Expected outputs:

"X" marks the presence of a ship. A, B, and C are points defined below.

Point A (0, 0)
Point B (0, 3)
Point C (2, 3)

hasShips(A, C) == true;
hasShips(B, C) == false;
hasShips(C, C) == false;

countShips(A, C) == 2;
countShips(B, C) == 0;
countShips(C, C) == 0;

This problem is a classic divide-and-conquer search over a 2D region. Since you can only query whether a sub-rectangle contains at least one ship through hasShips, the key is to recursively split the area into smaller rectangles, prune any region where hasShips returns false, and count only the parts that may contain ships. The main challenges are handling rectangle boundaries correctly, stopping at single-point regions, and minimizing the number of API calls.