Bloomberg VO Interview Problem: Count Ships in a Rectangle

You work on a project that has to implement a new ship discovering technology.

You are provided with the following 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 asks you to count how many ships lie inside a rectangle using only the provided <code>hasShips</code> API. The standard solution is recursive divide and conquer: prune any region for which <code>hasShips</code> returns false, stop when the region becomes a single point, and otherwise split the rectangle into smaller subregions and sum their results. The key ideas are efficient search, careful boundary handling, and using the API to avoid exploring empty areas.