FastPrepNumber of Ships in a Rectangle
Problems/Number of Ships in a Rectangle

Number of Ships in a Rectangle

Bloomberg LP logoBloomberg LP● HardNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A junior-level report on a Bloomberg role titled C++ developer lists a pair of coding tasks. One of them, named like a well-known practice problem, is about the ships inside a rectangle. It gives only that name, with no statement, limits or example. We read the name as the classic task where a lookup call tells whether a rectangle holds any ship, and the solver counts the ships with as few lookups as it can.

Everything else here is our choice. A function cannot call a lookup service, so the ships are given as a list, and you write the lookup yourself over that list. The answer also reports how many lookups were made, following one fixed splitting rule, so a solution that reads the list directly cannot match. Ships sit on whole points from 0 to 1000, no two share a point, the rectangle includes its edges, at most 10 ships are inside it, and the list has 1 to 1000 ships.

Our version is about 60% the same as the reported question.

A radar watches part of the sea. The sea is a grid of points (x, y) with whole coordinates from 0 to 1000. Each ship sits on one point. The list ships holds every ship as [x, y].

You are given a rectangle by its bottomLeft and topRight corners. The rectangle includes its edges, so a ship on an edge is inside it. Count the ships inside the rectangle.

The radar can answer one question only: hasShips(x1, y1, x2, y2) says whether at least one ship is inside the rectangle with those corners, edges included. Count the ships using only this question. You write the radar yourself as a small helper that reads ships, and you may not read ships anywhere else.

To show that you used the radar and nothing else, also return how many questions you asked. Use exactly these steps, so that every correct solution asks the same number of questions:

  1. Ask about the rectangle. This is one question. If the answer is no, the rectangle holds 0 ships. Stop.
  2. If the rectangle is a single point, it holds 1 ship. Stop.
  3. Otherwise let mx = floor((x1 + x2) / 2) and my = floor((y1 + y2) / 2). Split the rectangle into up to four parts: x from x1 to mx or from mx + 1 to x2, and y from y1 to my or from my + 1 to y2. Leave out a part whose range is empty. A part is empty when it would start after it ends, which happens when the rectangle is one column or one row wide. Repeat steps 1 to 3 for every part, and add up the ships.

Return [ships, questions]: the number of ships in the rectangle, and the total number of questions asked.

Function

countShips(ships: int[][], bottomLeft: int[], topRight: int[]) → int[]

Examples

Example 1

ships = [[1,1],[2,2],[3,3],[5,5]]bottomLeft = [0,0]topRight = [4,4]return = [3,17]

The rectangle covers the points with 0 <= x <= 4 and 0 <= y <= 4. It holds the ships at (1, 1), (2, 2) and (3, 3). The ship at (5, 5) is outside.

So the number of ships is 3. Following the splitting steps, the search asks 17 questions: the whole rectangle, then its four parts, and so on only inside parts that hold a ship.

Example 2

ships = [[7,7]]bottomLeft = [7,7]topRight = [7,7]return = [1,1]

The rectangle is one point and a ship is there. The first question about the whole rectangle is answered yes. A one-point rectangle cannot be split, so the ship is counted. Answer: 1 ship, 1 question.

Example 3

ships = [[9,9]]bottomLeft = [0,0]topRight = [3,3]return = [0,1]

The only ship is outside the rectangle. The first question answers no, so the search stops at once. Answer: 0 ships, 1 question.

Example 4

ships = [[2,1],[2,4],[3,3]]bottomLeft = [2,0]topRight = [2,5]return = [2,11]

The rectangle is a strip one point wide, with x = 2 and 0 <= y <= 5. The ships at (2, 1) and (2, 4) are inside, and the ship at (3, 3) is not.

A strip cannot be split sideways, so each split makes only two parts. The answer is 2 ships and 11 questions.

Constraints

  • 1 <= ships.length <= 1000
  • Every ships[i], bottomLeft and topRight has exactly 2 numbers: [x, y].
  • 0 <= x, y <= 1000 for every ship and for both corners.
  • bottomLeft[0] <= topRight[0] and bottomLeft[1] <= topRight[1].
  • No two ships are at the same point.
  • At most 10 ships are inside the rectangle.

More Bloomberg LP Onsite Interview questions

  • N-ary Index-Path Encoder and DecoderPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Top K Frequent WordsONSITE INTERVIEW · Seen Nov 2026
  • Trapping Rain WaterPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Word SearchOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Design Browser HistoryPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Mutable Stock Price Top KPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Add Two Numbers IIPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Decode StringPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Minimum Replacements to Make Two Strings AnagramsPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Currency Conversion RatePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026

Similar questions at other companies

  • Closest Pair of PointsCitadel · PHONE SCREENCitadel interview questions
  • Minimum Euclidean Distance Between PointsLuma AI · OALuma AI interview questions
  • Locate Vehicles with Square QueriesApplied Intuition · PHONE SCREENApplied Intuition interview questions
  • Max Points on a LineLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Dynamic Friendship ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
  • Construct a Tree from Level-Order and Inorder TraversalsSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Basic CalculatorAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Nested JSON Schema ValidatorPinterest · ONSITE INTERVIEWPinterest interview questions
  • Binary Tree Maximum Path SumGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
  • Toy Language Generic Return-Type InferenceOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions

Interview reports that mention this question

  • Bloomberg New Grad Question Bank: 161 Questions (Part 1 of 2)

Bloomberg LP interview experiences

  • Bloomberg AI-Assisted Coding Round, All Levels: 14 Experiences
  • Bloomberg SWE Intern Interview Questions: 68 Questions
  • Bloomberg Interview Questions, Level Not Reported: 65 Questions
  • Bloomberg Experienced Design & More: 126 Questions (Part 2 of 2)
  • Bloomberg Experienced SWE Interviews: 167 Questions (Part 1 of 2)
All Bloomberg LP interview questionsSee Bloomberg LP hiring insights
Saved
class Solution {
    public int[] countShips(int[][] ships, int[] bottomLeft, int[] topRight) {
        // Write your code here.
    }
}
Checking account…