SDE - 1

Chess tournament is going to be organized in Ninjaland. There will be C chess players going to attend the tournament. All the players will be staying in a hotel. The hotel has N free rooms available for the players, where one player will choose one room to live in. The ith room is at position[i] in the hotel. All rooms are in distinct positions.

Focus level of a chess player is defined as the minimum distance between his room and the room of another player. The overall focus of a tournament is defined as the minimum focus level among all players. You as an organizer obviously want the overall focus as high as possible so you assign the rooms to players such that the overall focus is as high as possible.

For example,

let say we have 3 players and 5 rooms available and the rooms are at positions:  1 2 3 4 6
Here the optimal allocation is in rooms 1 3 6 and the overall focus level is 2.

You are given a string 'S' containing only digits. Your task is to find all possible IP addresses that can be obtained from string 'S' in lexicographical order.

Note:

A valid IP address consists of exactly four integers, each integer is between 0 and 255 separated by single dots, and cannot have leading zeros except in the case of zero itself.

For example:

The following are valid IP addresses:
0.1.24.255
18.5.244.1

Following are invalid IP addresses:
0.01.24.255  (as  01  contains one leading zero).
18.312.244.1 (as 312 not lies between 0 and 255).

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

For example :

If the matrix is 
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4

Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.

Design URL Shortener service (Practice)