Daily bit(e) of C++ | Sonar
Daily bit(e) of C++ #49. The common C++ interview question: Sonar
You are given access to a ping method on a sonar system.
As quickly as possible, determine the number of ships in the given area using this method. The method only returns information about presence (whether any ships are in the given area).
The area includes the borders.
Before you continue reading, try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/v4TdoqKc1.
Solution
Since we want to minimize the number of calls to the sonar, we want to eliminate areas that do not contain any ships quickly. A standard approach for such a case is using divide and conquer.
When we receive a negative response, we know that the area doesn’t contain any ships.
When we receive a positive response, we know there is at least one ship. If we subdivide the area into four quadrants, we can quickly eliminate quadrants that do not contain any ships. Doing so leads to logarithmic complexity.
