SDE - 1

Wong is hungry and wants to eat tuna melt. He checks his pocket and finds that he has only a buck left. He asked Dr. Strange to lend him some money, for which Strange agrees but to get the money, Wong has to beat Strange in a game of coins. The game will be played by two players. Being kind enough Strange allows Wong to play first. Now, Strange arranges N coins in a row. Each coin is associated with a value. In his turn, every player can remove only one coin from either end. Once a player removes a coin, it can not be placed back into the row. At the end when all coins are removed, the player with the maximum value of coins wins. Wong will only get money if he wins the game. Wong knows that he can not beat sorcerer supreme, so he asked for your help.

You are given an array of integers, say, ‘ARR’ of size ‘N’ containing the values associated with ‘N’ coins. Your task is to determine the maximum value of coins you can obtain by following two rules:

a) Both players play in alternate turns and they can remove only one coin in their turn.
b) Any player can remove coins only from either of the two ends of ‘ARR’.

Note:

There can be more than one set of coins with maximum value.

For example:

a) Consider 3 coins are placed with values [10, 20, 30]: Wong removes 30, then Strange removes 20, then Wong removes 10. Now all coins are taken, and Wong has coins with value 40 and he wins.

b) Consider 1 coin is placed with value [100]: Wong removes the coin and no other coin is left. So, Wong wins with value 100.

Note:

a) The game only ends when NO MORE COIN IS LEFT to play with.

b) If a game ends in a draw, Wong is declared the winner. 

You are given a sorted array A consisting of N integers. Your task is to find the magic index in the given array.

Note :

1. A magic index in an array A[0 ... N - 1] is defined to be an index i such that A[i] = i.
2. The elements in the array can be negative.
3. The elements in the array can be repeated multiple times.
4. There can be more than one magic index in an array.

The gardener wants to water the garden by opening the minimum number of taps. The garden is one-dimensional along the x-axis of length N i.e. the garden starts from point 0 and ends at point N. There are N + 1 tap located at points [0, 1, 2, …, N] in the garden.

You are given an integer N, and an array named “ranges” of size N + 1(0-indexed). The ith tap, if opened, can water the gardener from point (i - ranges[i]) to (i + ranges[i]) including both. The task is to find the minimum number of taps that should be open to water the whole garden, return -1 if the garden can not be watered.

Example :

Follow Up:

Can you solve the problem in O(N) time?

Harshit wants to save money for his first car. So, he puts money in the Ninja bank every day.

He starts by putting in ‘1’ rupee on Monday, the first day. Every day from Tuesday to Sunday, he will put in ‘1’ rupee more than the day before. On every subsequent Monday, he will put in ‘1’ rupee more than the previous Monday.

You are given an integer ‘N’, your task is to return the total amount of money he will have in the Ninja bank at the end of the ‘N’th day.

For example :

Given ‘N’ = 2 
On Day 1 = 1
On Day 2 = 2 
Total Amount = 1 + 2 = 3.
Therefore the answer is 3.

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘n’ days.

You are given an array ‘prices’ which such that ‘prices[i]’ denotes the price of the stock on the ith day.

You don't want to do more than 2 transactions. Find the maximum profit that you can earn from these transactions.

Note

1. Buying a stock and then selling it is called one transaction.

2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again. 

Example:

Input: ‘n’ = 7, ‘prices’ = [3, 3, 5, 0, 3, 1, 4].

Output: 6

Explanation: 
The maximum profit can be earned by:
Transaction 1: Buying the stock on day 4 (price 0) and then selling it on day 5 (price 3). 
Transaction 2: Buying the stock on day 6 (price 1) and then selling it on day 6 (price 4).
Total profit earned will be (3 - 0) + ( 4 - 1) = 6. 

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘n’ days.

You are given an array ‘prices’ which such that ‘prices[i]’ denotes the price of the stock on the ith day.

You don't want to do more than 2 transactions. Find the maximum profit that you can earn from these transactions.

Note

1. Buying a stock and then selling it is called one transaction.

2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again. 

Example:

Input: ‘n’ = 7, ‘prices’ = [3, 3, 5, 0, 3, 1, 4].

Output: 6

Explanation: 
The maximum profit can be earned by:
Transaction 1: Buying the stock on day 4 (price 0) and then selling it on day 5 (price 3). 
Transaction 2: Buying the stock on day 6 (price 1) and then selling it on day 6 (price 4).
Total profit earned will be (3 - 0) + ( 4 - 1) = 6. 

You are given ‘n’ carrots numbered from 1 to ‘n’. There are k rabbits. Rabbits can jump to carrots only with the multiples of Aj(Aj,2Aj,3Aj…) for all rabbits from 1 to k.

Whenever Rabbit reaches a carrot it eats a little carrot. All rabbits start from the same beginning point. You have to determine the remaining carrots(i.e., carrots which are not eaten by any rabbit) after all rabbits reach the end.