Number of Ships in a Rectangle
Updated
Problem statement
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:
- Ask about the rectangle. This is one question. If the answer is no, the rectangle holds 0 ships. Stop.
- If the rectangle is a single point, it holds 1 ship. Stop.
- Otherwise let
mx = floor((x1 + x2) / 2)andmy = floor((y1 + y2) / 2). Split the rectangle into up to four parts: x fromx1tomxor frommx + 1tox2, and y fromy1tomyor frommy + 1toy2. 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],bottomLeftandtopRighthas exactly 2 numbers:[x, y]. 0 <= x, y <= 1000for every ship and for both corners.bottomLeft[0] <= topRight[0]andbottomLeft[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 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)