# Posts tagged as “interactive”

(This problem is an interactive problem.)

On the sea represented by a cartesian plane, each ship is located at an integer point, and each integer point may contain at most 1 ship.

You have a function Sea.hasShips(topRight, bottomLeft) which takes two points as arguments and returns true if and only if there is at least one ship in the rectangle represented by the two points, including on the boundary.

Given two points, which are the top right and bottom left corners of a rectangle, return the number of ships present in that rectangle.  It is guaranteed that there are at most 10 ships in that rectangle.

Submissions making more than 400 calls to hasShips will be judged Wrong Answer.  Also, any solutions that attempt to circumvent the judge will result in disqualification.

Example :

Input:
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3
Explanation: From [0,0] to [4,4] we can count 3 ships within the range.


Constraints:

• On the input ships is only given to initialize the map internally. You must solve this problem “blindfolded”. In other words, you must find the answer using the given hasShips API, without knowing the ships position.
• 0 <= bottomLeft[0] <= topRight[0] <= 1000
• 0 <= bottomLeft[1] <= topRight[1] <= 1000

## Solution: Divide and Conquer

If the current rectangle contains ships, subdivide it into 4 smaller ones until
1) no ships contained
2) the current rectangle is a single point (e.g. topRight == bottomRight)

Time complexity: O(logn)
Space complexity: O(logn)

## C++

Given a function  f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

• f(x, y) < f(x + 1, y)
• f(x, y) < f(x, y + 1)

The function interface is defined like this:

interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};


For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you’ll know only two functions from the list.

You may return the solutions in any order.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y


Constraints:

• 1 <= function_id <= 9
• 1 <= z <= 100
• It’s guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
• It’s also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000

## Solution1 : Brute Force

Time complexity: O(1000*1000)
Space complexity: O(1)

## C++

Problem:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution 1: Brute Force

Time Complexity: O(n) TLE

Space Complexity: O(1)

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

Mission News Theme by Compete Themes.