Bloomberg | Phone | Ships

Position: Software Development Internship 2019
Location: Pune, India

Question:

Consider the sea to be a cartesian plane. There are ships at different places in the sea. Given two points, which are the top right and bottom left corners of a rectangle, find the number of ships present in between the two points (more specifically, ships present inside the rectangle formed by these two points).

1. You have a function hasShips(A: Point, B: Point) -> bool which takes two Points as arguments and returns a boolean. If there are ships in between the two points, it returns true, else false.
2. If you want to check whether a ship is present at a point, say A(2, 2), you can pass the same point twice into the function above as so: hasShips(A, A) which returns true if there's a ship at point A, and aliter.

The Point class looks like:

class Point():
	def __init__(self, x, y):
		self.x = x
		self.y = y

NOTE: The interviewer specifically asked to start checking from bottom to top.

Naive solution that I first came up with:

Let's say the points are bottom_left & top_right respectively.

def countShips(bottom_left: Point, top_right: Point) -> int:
	shipCount = 0
	for i in range(bottom_left.y, top_right.y+1):
		for j in range(bottom_right.x, top_right.x+1):
			pointToCheck = Point(i, j)
			if (hasShips(pointToCheck, pointToCheck):
				shipCount += 1
	return shipCount

# Print statement below was already given
print(countShips(bottom_left, top_right)

Time complexity would be O(m*n) where m & n are the dimensions of the rectangle formed by the given coordinates. In general, the code runs in O(n^2), which is a red flag!

Divide & Conquer Approach

NOTE: Not sure about if the solution is, but this is what I answered to the interviewer.

We check row and column wise and go on decreasing the checking size. If there are no ships in a row and column, we need not iterate through each element there. In the picture above, the red part is iteration 1, blue is iteration 2 and so on. If any row or column doesn't contain a ship, we would ignore it, but if it does, we iterate through each element in the row and column and count the ships.

Note to contributors: I know my solutions are either pretty slow or completely wrong. Please comment below your approach to this problem.