Data Engineer

You and your friend Ninjax are playing a game of coins. Ninjax place the 'N' number of coins in a straight line.

The rule of the game is as follows:

1. Each coin has a value associated with it.

2. It’s a two-player game played against an opponent with alternating turns. 

3. At each turn, the player picks either the first or the last coin from the line and permanently removes it.

4. The value associated with the coin picked by the player adds up to the total amount the player wins. 

Ninjax is a good friend of yours and asks you to start first.

Your task is to find the maximum amount you can definitely win at the end of this game.

Note:

'N' is always even number.

Ninjax is as smart as you, so he will play so as to maximize the amount he wins.

Example 1:

Let the values associated with four coins be: [9, 5, 21, 7] 

Let’s say that initially, you pick 9 and Ninjax picks 7.
Then, you pick 21 and Ninjax picks 5. 
So, you win a total amount of (9+21), i.e. 30.

In case you would have picked up 7 initially and Ninjax would have picked 21 (as he plays optimally). 
Then, you would pick 9 and Ninjax would choose 5. So, you win a total amount of (7+9), i.e. 16, which is not the maximum you can obtain.

Thus, the maximum amount you can win is 30.

Example 2:

Let the values associated with four coins be: [20, 50, 5, 10] 

Let’s say that initially, you pick 10 and Ninjax picks 20.
Then, you pick 50 and Ninjax picks 5. 
So, you win a total amount of (10+50), i.e. 60.

In case you would have picked up 20 initially and Ninjax would have picked 50 (as he plays optimally). 
Then, you would pick 10 and Ninjax would choose 5. So, you win a total amount of (20+10), i.e. 30, which is not the maximum you can obtain.

Thus, the maximum amount you can win is 60.

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) ?

You are given a string S which represents a number. You have to find the smallest number strictly greater than the given number which contains the same set of digits as of the original number i.e the frequency of each digit from 0 to 9 should be exactly the same as in the original number.

For example:

If the given string is 56789, then the next greater number is 56798. Note that although 56790 is also greater than the given number it contains 1 '0' which is not in the original number and also it does not contain the digit '8'.

Note:

The given string is non-empty.

If the answer does not exist, then return -1.

The given number does not contain any leading zeros.

We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help increase vaccination following safety measures. Time is running out. Can you help the nation?

You are given two positive integers: ‘n,’ ‘maxVaccines’ denoting the number of days for which this vaccination drive will go on and the total number of vaccines available for the drive, respectively. You have to find the number of vaccines administered each day. You are also given a number ‘dayNumber,’ and we are interested to know the maximum number of vaccines that can be administered on ‘dayNumber’ th day.

The rules of the vaccination drive :

1. There should be a positive number of vaccines administered each day during the vaccination drive.

2. The absolute difference between the number of vaccines in two consecutive days should not exceed 1.

3. The sum of all the elements of the vaccines array does not exceed maxVaccines, that is, you cannot administer more vaccines than what is provided to you.

4. Vaccines administered on ‘dayNumber’ th day should be maximized.