Data Engineer

You are playing a board game where you die when your hp (health points) becomes 0 or negative. Now you start with some initial hp, and start moving in the board starting from the top-left corner. You have to reach the bottom right corner of the board by only moving right and down. Whenever you arrive on a cell in the board your hp may increase or decrease by the amount written on the cell. If the cell has a positive value it means your hp increases, if it has a negative value it means your hp decreases. You need to return the minimum initial health required so that you can reach the rightmost corner.

For Example:

In the example below, if we follow the path shown in the figure, then the minimum initial hp required will be 3.

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?